З досвіду роботи. Стратегія гри

СТРАТЕГІЯ ГРИ

Ігрові математичні задачі – це той клас задач, яким захоплюються люди не байдужі до математики.

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

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

Ігрові задачі представляють собою цікавий об’єкт для математичних досліджень. Звичайно ж, результат у деякій мірі залежить від випадковостей. Але, в той же час, багато що визначається майстерністю суперників. Успішна гра потребує точних математичних розрахунків. У таких задачах цікавість представляє побудова чіткого алгоритму дій, що гарантує досягнення бажаного результату.

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

Розглянемо ігрові задачі на конкретних прикладах.

2.1. Задачі на відповідність

Приклад 1. Двоє грають – ламають шоколадку, що складається з 64=24 дольок. При тому за один  хід можна зробити лише один розлом по прямій вздовж заглиблення на шоколадці. Програє той, хто не матиме ходу. Хто виграє, перший, чи другий гравець? [9, с.65]

Розв’язання: У якій послідовності гравці б не ламали шоколадку, все одно наприкінці гри вони отримають парну кількість шматочків. Тому виграє той, після ходу якого буде утворюватися парна кількість шматочків шоколадки, тобто перший гравець.

Відповідь: той, хто розпочинає гру.

Приклад 2. На дошці записано чотири числа:4, 7, 11, 13. Дозволяється до довільних двох з них додати по одиниці й записати отримані суми замість двох обраних чисел. Чи можна таким чином зробити всі числа рівними? [8, с.71].

Розв’язання: Якщо чотири числа рівні, то їхня сума є парним числом. Сума даних за умовою чисел є числом непарним (бо одне з цих чисел парне, а три – непарні). Тоді додаванням певно кількості двійок (1+1) треба перейти від непарної суми чисел до парної, що неможливо. (Додавання парного числа не змінює парності числа.)

Відповідь: ні, не можна.

Приклад 3. Ромашка має 12 пелюстків. Грають двоє гравців. За один хід дозволяється відірвати або одну пелюстку, або дві, що ростуть підряд. Програє той, хто не може зробити хід. У кого з гравців є виграшна стратегія?

Розв’язання: Незалежно від ходу першого гравця другий може після першого ходу залишити два однакові за довжиною ланцюжки з пелюсток, а далі – симетрично повторювати ходи першого.

Відповідь: Виграє другий гравець.

Приклад 4. Два хлопчики по черзі пишуть k-значне число: першу цифру пише перший, другу – другий і т.д. Чи може другий хлопчик добитися того, щоб отримане число ділилося на 9, якщо перший заважає йому це зробити? [7, 72]

Розв’язання: При парному k – може, при непарному – ні.Тому, хто пише останню цифру, може цим досягти будь-якої остачі від ділення на 9.

Відповідь: Другий гравець зможе досягти результату лише при парному значенню k.

Приклад 5. Двоє гравців по черзі виймають із двох відер яблука. За один хід кожен гравець може брати з будь – якого, але тільки одного відра довільну кількість яблук. Виграє той, хто забере останнє яблуко. Як має грати перший гравець, щоб виграти, якщо у першому відрі 42 яблука, а в другому – 38?

Розв’язання: Першому гравцю потрібно взяти з першого відра 4 яблука. Після цього яблук в обох відрах стане порівну. А далі на кожен хід суперника першому гравцю слід відповідати симетричним ходом. Тобто, якщо другий бере певну кількість яблук з одного відра, то першому потрібно брати таку саму кількість яблук з другого відра і тоді останнє яблуко забере перший гравець. (Яблука слід брати не з того відра з якого брав суперник.)

Відповідь: Щоб виграти першому гравцеві потрібно взяти спочатку 4 яблука з першого відра, а далі брати стільки яблук, скільки братиме інший гравець.

Приклад 6. Миколка і Сашко виписують дванадцятицифрове число , ставлячи цифри по черзі, починаючи зі старшого розряду. Довести що, які б цифри не писав Миколка, Сашко завжди зможе домогтися, щоб отримане число ділилося на 4.

Розв’язання: За ознакою подільності числа на 4, матимемо, щоб число ділилося на 4 необхідно, щоб останні дві цифри даного числа ділилися на 4. Якщо Миколка на 11-му ходу ставить парне число, то Сашко ставить 4, а якщо Миколка пише не парне число, то Сашко ставить 2.

Відповідь: Які б цифри не писав Миколка, Сашко завжди зможе домогтися, щоб отримане число ділилося на 4, якщо буде дотримуватися ознак подільності на 4.

Приклад 7. Миколка та Сергійко грають у гру, по черзі записуючи цілі числа в клітинки таблиці розмірами 7x9 (7 рядків, 9 стовпчиків). Першим робить хід Миколка. За один хід записується одне число у вільну клітинку. Гра продовжується, поки вони не заповнять числами всю таблицю. Потім підраховуються значення S₁, S₂, ..., S₇, – суми чисел у рядках таблиці. Якщо серед чисел S₁, S₂, ..., S₇ парних більше, ніж непарних, виграє Миколка. В іншому разі – Сергійко. Хто з двох гравців може забезпечити собі виграш?

Розв’язання: Виграє Миколка. Першим своїм ходом Миколка записує число 1 у центральну клітинку таблиці. Якщо Сергійко запише в певну клітинку число а, то Миколка має записати число а+1 у клітинку, яка є центрально-симетричною до клітинки, що містить число а. Кожній клітинці першого рядка можна поставити у відповідність клітинку сьомого рядка, що буде центрально-симетричною до неї, і навпаки. Тому перший і сьомий рядки таблиці будемо називати центрально-симетричними. Клітинки цих рядків можна розбити на дев'ять центральносиметричних пар. Сума чисел у кожній парі таких клітинок буде непарною, оскільки a+(a+1)=2a+l. Тоді числом, S₁+S₂ – непарне. Отже, одна із сум S₁ або S₂ є парною. Аналогічно числа S₂+S₆, S₃+S₅ також будуть непарними, і в кожній з цих пар одна сума буде парною. Якщо Сергійко виконує хід у певну клітинку четвертого рядка, то Миколка у відповідь записує довільне число в будь-яку вільну клітинку цього ж четвертого рядка. Клітинок у рядку непарна кількість, тому останню вільну клітинку четвертого рядка буде заповнювати Миколка, тобто він у змозі забезпечити парність суми S₄. Отже, чотири із семи чисел S₁, S₂, ..., S₇ будуть парними.

Відповідь: Виграє Миколка.

Приклад 8. Два гравці записують по черзі числа 1 і –1 в одиничні клітинки таблиці розміром 1987×1987. Після того, як всі клітинки заповнені, для кожного рядка, стовпця і двох діагоналей таблиці підраховується добуток чисел, які там записані. Довести, що гравець, який робить перший хід, може грати так, щоб серед цих добутків було рівно 1990 додатних. [5, с.72]

Розв’язання: Оскільки число 1987 непарне, то існує клітинка, центром якої є центр симетрії даної таблиці. Для кожної іншої клітинки існує клітинка, симетрична з нею відносно центра таблиці. Якщо перший гравець хоче домогтись вказаного в задачі результату, то своїм першим ходом він має записати в центральну клітинку число (−1), а після кожного ходу другого гравця йому слід записувати число протилежного знаку в клітинку, симетричну відносно центра таблиці із клітинкою «суперника». Якщо, наприклад, другий гравець своїм першим ходом записує число (+1) в клітинку першого стовпця, то перший гравець записує число (−1) в симетричну з нею клітинку 1987-го стовпця. Після цього обміну ходів в кожному із заданих стовпців залишиться по 1986 клітинок, тому в першому стовпцеві буде 993+1 число (+1) і 993 числа (−1), тобто добуток чисел буде дорівнювати –1. У 1987 стовпцеві буде 994 клітинки з числами (−1) і 993 – з числами (+1). Добуток всіх чисел дорівнює (+1). Таким чином, в тому рядку чи в тій діагоналі, де перший запис робить перший гравець, добуток чисел дорівнює (+1). Сюди відносяться, перш за все, обидві діагоналі, той рядок і той стовпець, які містять центральну клітинку (всього 4). Решта рядків і стовпців буде 1986 з додатними добутками і 1986 – з від’ємними. Отже, 1986+4=1990 – кількість додатних добутків.

Відповідь: Гравець, який робить перший хід, може грати так, щоб серед цих добутків було рівно 1990 додатних.

2.2. Розв’язування задач з кінця

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

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

Відповідь: Виграє другий гравець.

Приклад 2. Гра починається із числа 1000. За хід дозволяється відняти від наявного числа будь-яке, що не перевищує його, натуральне число, що є степенем двійки (1=2⁰). Виграє той, хто одержить нуль [4].

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

Відповідь: Виграє перший.

Приклад 3. Тура стоїть на лівій кутовій клітинці шахівниці (на полі а1). За хід дозволяється пересунути її на будь-яке число клітинок вправо чи на будь-яке число клітинок угору. Виграє той, хто поставить туру на протилежну праву верхню кутову клітинку (на поле h8). Хто з двох гравців має виграшну стратегію? [5, с.22]

Розв’язання: Кожним своїм ходом другий гравець повертає туру на велику діагональ a1-h8. Тому перший гравець своїм ходом завжди виводить туру з цієї діагоналі, отже, і не може її туди поставити, а поле h8 знаходиться саме на цій діагоналі.

Відповідь: Виграє другий.

Приклад 4. На столі – 23 цукерки. Кожен з двох гравців за один хід може взяти будь – яку кількість цукерок від 1 до 4. Виграє той, хто забере останню цукерку. У кого з гравців виграшна стратегія і в чому вона полягає?

Розв’язання: Розмістимо «умовні цукерки» в ряд, попередньо занумерувавши їх, але в зворотному порядку. Тобто, першою будемо брати цукерку під номером 23, 22, 21, 20, …,4, 3, 2, 1. Для того, щоб останнім своїм ходом (нехай це n – ний хід) забрати останню цукерку і, таким чином, виграти гру, першому гравцеві потрібно, щоб суперник після n-1 ходу залишив на столі 1,2,3 або 4 цукерки. Для цього першому гравцеві потрібно після (n–2)-го ходу залишити на столі 5 цукерок. Тому « вихід» на номери кратні 5, забезпечує першому гравцеві перемогу в грі. Тому в першому ході першому гравцеві потрібно взяти 3 цукерки. А далі після кожного ходу першому гравцеві потрібно брати стільки цукерок, щоб кількість цукерок, що залишилась, була кратна числу 5.

Відповідь: Виграшна стратегія у першого гравця. Йому потрібно взяти спочатку 3 цукерки а потім брати стільки цукерок, щоб кількість тих, що залишились була кратною числу 5.

Приклад 5. Двоє по черзі знімають зі столу фішки. За один раз дозволяється зняти зі столу 1, 10 або 11 фішок. Виграє той, хто зніме останню фішку. Перед початком гри на столі було 40 фішок. Хто виграє за умови дотри­мання правил гри – той, хто починає гру, чи його суперник? [5, с.71].

Розв’язання: Будемо розв'язувати задачу з кінця. Якщо припустити, що на столі залишилася одна фішка, то ситуація є виграшною для того гравця, чия черга ходити. Він бере цю фішку й виграє. Якщо залишилось дві фішки – ситуація програшна для того, чия черга ходити. Будемо записувати числа 1, 2, 3, ... зі знаками «+» або «-» залежно від того, виграшною чи програшною є дана ситуація для гравця, який робить хід. Тоді якщо гравець певним ходом (знявши 1, 10 або 11 фішок) може створити програшну ситуацію для свого суперника (бо його черга ходити), то для нього початкова ситуація є виграшною. Тепер можна з'ясувати по черзі для всіх чисел 1, 2, 3, ... виграшною чи програшною є ситуація для даної кількості фішок на столі. Для чисел від 1 до 9 знаки «+» або «-» розставляються по черзі. Числа 10, 11, 12, 13. ..., 19 є виграшними, 20 – програшним (будь-яким ходом можна досягнути лише чисел 9, 10 і 19, які є виграшними для суперника). Оскільки знаки через 20 чисел повторюються, можемо легко продовжити розставляння знаків. Неважко переконатися, що число 40 має знак «-», тобто за правильної гри другий гравець виграє.

Відповідь: Виграє другий гравець.

Приклад 6. Маємо три купи каменів: в першій – 10, в другій – 15, в третій– 20. За хід дозволяється розділити будь-яку купу на дві менші; програє той, хто не зможе зробити хід. Хто програє у цій грі? [5, с.13].

Розв’язання: Проаналізуємо кінцевий стан у грі. Після кожного ходу кількість купок збільшується на 1. Спочатку їх було 3, в кінці – 45. Таким чином, всього буде зроблено 45-3=42 ходи. Останній 42-й хід, зробить гравець, який робить парні ходи. Отже, гравець, який розпочинає гру, програє.

Відповідь: гравець, який розпочинає гру, програє.

2.3. Задачі без стратегій або на передачу ходу

Приклад 1. В одному ящику лежать 15 синіх кульок, а в другому 12 білих. За один хід дозволяється взяти 3 синіх кульки або 2 білі. Перемагає той, хто бере останні кульки.

Розв’язання: Зрозуміло, що сині кульки можна рахувати трійками, а білі двійками. Задача зведена до наступної: У ящику лежать 15:3+12:2=11 кубиків. За один хід дозволено брати один кубик. Хто візьме останній? Зрозуміло, той, хто розпочинав гру. Отже, це гра, в якій нічого не залежить від гравців.

Відповідь: Той, хто розпочинав гру.

Приклад 2. На дошці написані 10 одиниць і 10 двійок. За хід можна витерти дві будь-які цифри і, якщо вони були однакові, написати 2, якщо різні –1. Якщо остання цифра що залишилася на дошці – 1 , то перемагає перший гравець, якщо – 2, то другий  [5, с.5].

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

Відповідь: Виграє другий гравець.

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

Розв’язання: Парність результату не залежить від розташування знаків, а від кількості непарних чисел в початковому наборі. Оскільки в даному випадку їх 10 (тобто парне число), то перемагає перший гравець.

Відповідь: Виграє перший.