Задачі-ігри для шкільних математичних олімпіад

                     Задачі -  ігри

1.  Ігри-жарти

Перший клас ігор, про які піде мова, — ігри-жарти. Ці ігри, ре­зультат яких не належить від того, як грають суперники. Наведемо приклад такої гри-жарту.

Задача 1. Двоє по черзі розламують шоколадку 6x8.  За один хід дозволяється зробити прямолінійний розлом будь-якої частини вздовж заглиблення. Програє той, хто не зможе зробити хід.

 Розв 'язок. Головне міркування: після кожного ходу кількість частинок збільшується рівно на 1.      Спочатку був один шматок.   В кінці гри, коли не можна пробити жоден хід, шоколадка розламана на маленькі частинки. А їх-48. Таким чином, гра буде тривати рівно 47 ходів, Останній, 47-й хід (також, як і всі інші ходи з непарними номерами), зробить перший гравець. Тому він в цій грі перемагає, причому незалежно від того, як він буде грати.

Задача 2. Маємо три купи каменів: в першій - 10, в другій 15, в третій 12. За хід дозволяється розділити будь-яку купу на дві менші; програє той, хто не зможе зробити хід.

Задача 3. Числа під 1 до 20 виписані в рядок. Гравці, по черзі ро­зставляють між ними плюси і мінуси. Після того, як всі місця заповнені, підраховуємо результат. Якщо він парний, виграє перший гравець, якщо непарний   - другий.

Задача 4. Двоє по черзі ставлять тури на шахову дошку так, що тури не б'ють одна одну. Програє той, хто не може зробити хід.

Задача 5. На дошці записано 10 одиниць і 10 двійок. За хід дозво­ляється стерти дві будь-які цифри, якщо вони однакові написати двійку, а якщо різні одиницю. Якщо остання цифра, що залишилася на дошці одиниця, виграв перший гравець, якщо двійка — то другий.

Задача 6. На дошці написано числа 25 і 36. За хід дозволяється допи­сати ше одне натуральне число — різницю будь-яких двох написаних на дошці чисел, якщо вони ще не зустрічалася. Програє той, хто не може зробити хід.

Задача 7.  Маємо клітчасту дошку розмірами а) 9 х 10;    б) 10 х 12;    її) 9х11.

За хід дозволяється викреслити будь-яку горизонталь чи будь-яку вер­тикаль, якщо в ній на час ходу є хоч би одна невикреслена клітинка. Програє той, хто не може зробити хід.

Спробуємо, застосовуючи симетричну стратегію, розв'язати од­ну задачу.

Задача 1. Двоє по черзі ставлять слонів у клітинки шахової дошки таж, що слони не б'ють один одного. (Колір слонів значення не має.) Програє: той, хто не може зробити хід. Чи виграє починаючий гравець?

Спроба розв'язування. Оскільки шахова дошка симетрична відносно свого центру, то природно спробувати симетричну стратегію. Але на цей раз (першим ходом не можна поставити слона в центр дошки) симетрію може підтримувати другий гравець. Здавалося б, по анало­гії з попередньою задачею, це і є його виграшна стратегія. Проте, додержуючись її, другому гравцю не вдасться зробити навіть свій перший хід! Слон, щойно поставлений першим гравцем, може бити центрально-симетричне поле.

Цей приклад показує, що при доведенні правильності симетричної стратегії не можна забувати про наступну обставину:

черговому симетричному ходу може завадити хід, щойно зроблений супротивником.

Раніше зроблені ходи, в силу симетрії позиції, завадити не можуть. Щоб розв'язати гру за допомогою симетричної стратегії, необхідно знайти симетрію, при якій щойно зроблений супротивником хід не перешкоджає здійсненню обраного плану.

Так, розв'язання задачі 9 легко провести, застосовуючи не цен­тральну, а осьову симетрію шахової дошки. За вісь симетрії можна взяти пряму, що поділить четверту і п'яту горизонталі. Симетричні відносно неї поля мають різний колір, і, тим самим, слон, що поста­влений на одне з них, не перешкоджає ходу на інше. Таким чином, в цій грі виграє все ж таки другий гравець.

Симетрична стратегія зовсім не зобов'язана мати суто геометрич­ний зміст. Розглянемо задачу:

Задача 2. Є дві купи каменів по 7 в кожній. За хід дозволяється взяти будь-яку кількість каменів, але тільки із однієї купи. Програє той, кому нема що брати.

Розв 'язок. В цій грі другий гравець перемагає за допомогою симе­тричної стратегії: кожним своїм ходом він повинен брати стільки ж каменів, скільки попереднім ходом взяв перший гравець, але з іншої купи. Таким чином, у другого гравця завжди є хід. Симетрія в цій задачі грунтується на рівності числа каменів в купах.     □

Для викладачів. Ідея симетрії заслуговує окремої невеликої розмови. Перед нею необхідно розв'язати дві-три гри на симетрію (краще на одному занятті).

От ще декілька ігор, що ілюструють ту ж ідею.

Задача 3. Двоє по черзі ставлять коні в клітинки шахової дошки так, що коні не б'ють один одного. Програє той, хто не може зробити хід.

11.                Виграє другий.    Перший хід в центр дошки, а після цього - центральна симетрія.

Задача 4. Двоє по черзі ставлять королі у клітинки дошки 9x9 так, що королі не б'ють один одного. Програє той, хто не може зробити хід.

Відповідь: Виграє перший.   Можна використати і центральну, і осьову симетрію.

Задача 4а).

а)  Двоє по черзі ставлять слони у клітинки шахової дошки. Черговим
ходом слід побити хоча б одну небиту клітинку. (!лон б'є і клітинку,
на якій він знаходиться. Програє той, хто не може пробити хід.

б)  * Та ж гра, але з турами.

Відповідь: В обох пунктах виграє перший гравець,  а) Осьова симетрія; б)
Центральна симетрія.   Вирішальним міркуванням є те, що якщо два
симетричних поля не побиті, то поля, з яких обидва вони б'ються,
також не побиті.

Задача 5. Дано клітчасту дошку 10 х 10. За хід дозволяється по­крити будь-які 2 сусідні клітинки прямокутником 1x2 так, щоб пря­мокутники не перекривались. Програє той, хто не може зробити хід.

Відповідь.Виграє другий. Центральна симетрія.

Задача 6. В кожній клітинці дошки 11 х 11 стоїть шашка. За хід дозволяється зняти з дошки будь-яку кількість шашок, що йдуть під­ряд, або з одного вертикального, або з одного горизонтального ряду. Виграє той, хто зняв останню шашку.

Відповідь. Виграє перший.  Першим ходом він знімає центральну шашку, а
потім грає центрально-симетрично.

Задача 7. Є дві купки камінців: в одній — 30, в другій — 20. За хід дозволяється брати будь-яку кількість камінців, але тільки з одної купки. Програє той, кому нема що брати.

Відповідь. Виграє перший. Першим ходом він зрівнює кількість камшців в купках, після чого грає як в задачі 10.

Задача 8. На колі розставлено 20 точок. За хід дозволяється з'єдна­ти будь-які дві з них відрізком, що не перетинає відрізків, які проведено раніше. Програє той, хто не може зробити хід.

Відповідь. Виграє перший.  Першим ходом він проводить хорду, по обидва
боки від якої розташовано по 9 вершин.   Після цього, на кожний хід
другого він відповідає аналогічним ходом по інший бік від цієї хорди.

Задача 9. Ромашка має а) 12 пелюсток; б) 11 пелюсток. За хід дозволяється відірвати або одну пелюстку, або дві, що ростуть поруч. Програє той, хто не може зробити ходу.

Відповідь. В обох пунктах виграє другий гравець. Незалежно від ходу пер­
шого гравця, другий може після свого ходу залишити два однакових за
довжиною ланцюжки пелюсток. Далі — симетрія. а) і б) — виграє другий.  Центральна симетрія

Ми радимо Вам звернути особливу увагу на задачі ігри, які розв’язуються з кінця. Їх ілюструє наступна задача:

Задача 31. Є дві купки камінців: в першій — 7 камінців, в другій — 5. За хід дозволяється брати будь-яку кількість камінців із однієї купки або порівну камінців із обох купок. Програє той, хто не може зробити хід.

Розв 'язок. Покажемо, як переформулювати цю задачу на вже звичній для нас мові шахової дошки. Пронумеруємо вертикалі і горизонталі шахової дошки числами від 0 до 7: вертикалі — згори-вниз, а горизон­талі — справа наліво. Кожній позиції вихідної гри зіставимо клітинку, що знаходиться на перетині горизонталі з номером, що дорівнює чи­слу камінців у першій купці, і вертикалі з номером, що дорівнює числу камінців в другий купці. Тепер зауважимо, що ходу в даній грі відпо­відає хід ферзя праворуч, вгору або по діагоналі "праворуч-вгору" на шаховій дошці. Таким чином, ми ототожнили нашу гру з грою із за­дачі 30. Відмітимо, що так само можна ототожнити ігри в задачах 10 і 22.     О

Декілька задач-ігор на   аналіз із кінця:

Задача 32. Кінь стоїть на полі ці. За хід дозволяється пересувати коня або на дві клітинки праворуч і одну клітинку вгору або вниз, або на дві вгору і на одну праворуч або ліворуч. Програє той, хто по може зробити хід.

Задача 33.

а)  Є дві купки по 7 камінців.  За хід дозволяється взяти один камі­нець із будь-якої купки або по камінцю з кожної купки.   Програє
той, хто не може зробити хід.

б)  Крім ходів, допустимих в пункті а), дозволяється перекладати один
камінець із першої купки в другу. В усьому іншому правила ті ж
самі.

Задача 34. Є дві купки по 11 сірників. За хід можна взяти два сірники з однієї купки і один із другої. Програє той, хто не може зробити хід.

Задача 35. Гра починається із числа 0. За один хід дозволяється додати до наявного числа будь-яке натуральне число від 1 до 9. Виграє той, хто одержить число 100.

Задача 36. Гра починається із числа 1. За один хід дозволяється пом­ножити наявне число на будь-яке натуральне число від 2 до 9. Виграє той, хто першим одержить число, більше 1000.

Відповіді :

32.                Виграє другий гравець. Відповідна розстановка плюсів і мінусів
наведена на мал. 68.

33.       Переформулюсмо пункти а) і б) и термінах шахової дошки. Гра а)
виявляється тотожною грі із задам і 23.  Розстановка плюсів і мінусів
в пункті б) така ж, як у пункті а) (дим. малюнок 45). В обох пунктах
виграє перший гравець.

34.       Виграє перший.    Розстановка плюсів і мінусів після перефор-
мулювання в термінах клітчастої дошки показана на мал. 69.

+	+	+	+	+	+	+	+	+	+	+	+
										+	+
											+
+	+	+	+	+	+	+	+	+	-	-	+
-і	-	-	-	-	-	-	+	+	-	-	+
											+
+	+	+	+	+	+	-	-	+	-	-	+
-		-	-	+	+	-	-	+	-	-	+
-	-	-	-	-	+	-	-	+	-	-	+
+	+	+	-	-	+	-	-	+	-	-	+
-	+	+	-	_	+	-	-	+	-	-	+
	-	+	-	-	+	-	-	+	-	-	+

Мал. 68

35.                Ця задача є прикладом того, що геометричної. інтерпретація нео­бов'язкова для проведення аналізу з кінця.   Тут плюсами і мінусами зручно помічати числа.    Плюсом виявляються позначені числа, що діляться на 10. Таким чином, виграє другий гравець.

36.       Аналізуючи з кінця, знаходимо виграшні позиції. Це числа від 56
до 111 і від 4 до 6. Таким чином, виграє перший гравець (його перший
хід — в 4, 5 або 6).

37.                  Аналізуючи з кінця, знаходимо виграшні позиції: 500, 250, 125,
62, 31, 15, 7, 3. Виграє перший гравець.

38.        Аналізуючи з кінця, знаходимо виграшні позиції.  Це числа, що
діляться на 3.   Виграє перший гравець.  Першим ходом він може, на­
приклад, відняти 1, 4, 16.

Задачі-ігри.

1.Дано смужку 1x17, клітинки якої пронумеровано послідовними натуральними числами. Двоє учнів грають у гру, по черзі роблячи свої ходи. За один хід треба закреслити одну довільну клітинку в смужці або деякі дві послідовні, де перша з них парна. Програє той, хто не може зробити хід. Хто може забезпечити собі виграш - той, хто почи­нає гру, чи його суперник? Вкажіть виграшну стратегію.

2. На дошці розміром 4x4 грають двоє. Ходять по черзі, і кожний гравець своїм ходом зафарбовує одну клітинку. Кожну клітинку мож­на зафарбувати один раз. Програє той гравець, після чийого ходу утвориться квадрат 2х2, що складається із зафарбованих клітинок. Хто з гравців може забезпечити собі виграш - той, хто починає, чи його суперник? Відповідь обґрунтуйте.

3.Двоє гравців по черзі вписують у клітинки квадратної дошки п х п натуральні числа згідно з такими правилами: у клітинку, яка знаходиться на перетині n-го рядка та m-го стовпчика, перший гравець має право вписати найбільший спільний дільник чисел і тау, а другий гравець має право вписати найменше спільне кратне цих чисел. Після заповнення дошки всі числа першого стовпчика діляться на 1, усі чис­ла другого стовпчика діляться на 2, усі числа третього стовпчика ді­ляться на 3 і так далі, аж до останнього стовпчика, усі числа якого ді­ляться на n. Потім обчислюється добуток усіх отриманих чисел. Якщо результат менший як 1, то виграє перший гравець, в іншому разі ви­грає другий гравець. Хто з гравців може забезпечити собі перемогу -той, хто починає гру, чи його суперник?

4.На дошці написано числа 1, 1998, 1999. За один крок дозволя­ється витерти одне з чисел і замість нього записати різницю між його квадратом та потроєним добутком двох інших чисел. Чи можна, вико­нуючи такі дії, з початкового набору отримати трійку чисел, сума яких дорівнює нулю?