Задачі про ігри- вельми популярний вид олімпіадних завдань, особливо в молодших класах. Найбільш загальна проблема у початківців - зрозуміти, "що взагалі від нас хочуть", які міркування є правильним рішенням завдання, а які - ні.
Звичайно передбачається що грають двоє, роблячи ходи по черзі (пропускати свій хід не можна!), А в задачі запитують "хто виграє при правильній грі?" Стандартна помилка по суті - розуміти слова "при правильній грі" так, як ніби обидва супротивники грають оптимальним для себе чином (тим більше, що розв’язуючий задачу часто неправильно розуміє, що таке "оптимальним чином"!). Тоді придумується виграшна стратегія, яка дає відповідь тільки на оптимальний хід супротивника (зазвичай ще "оптимальним" вважається такий хід, коли супротивник слід придуманої нами ж стратегії - хоча для іншого гравця така стратегія може бути, навпаки, зовсім нікчемною!). Насправді, треба вміти придумувати відповідь на будь-який хід противника, яким би ідіотським він нам не здавався. Зазвичай правильна стратегія, на відміну від неправильної, не має випадків різної складності, а з однаковою легкістю знаходить гідну відповідь на будь-який хід!
Ігри-жарти. Найперший і простий клас ігор - ігри-жарти, в яких, насправді, немає ніякої стратегії (а нас хочуть обдурити, що вона нібито є!). Просто як би хто не ходив, або завжди виграє перший гравець (той, хто починає гру), або завжди другий. Задача - в тому, щоб математично довести таку закономірність (а помітити її можна, зігравши самому з собою рази 3-4). Для доказу зазвичай знаходиться якась величина, яка зрозуміло чому дорівнює на початку і кінці і зрозуміло як змінюється на кожному ходу - тут навіть часто число ходів до кінця однозначно порахувати можна. Або якийсь інваріант (тобто щось, що не міняють ні за якого ходу), однозначно залежить від початкової позиції (найчастіше - від парності) і визначальний вигравшого у кінці.
Задача 1. Двоє по черзі ламають шоколадку 5x8. За хід можна розламати будь-який шматок по прямій лінії між часточками. Програє той, хто не може зробити хід (І це стандартна умова, що ми її будемо мати на увазі, якщо не сказано протилежне. Питання "хто виграє при правильній грі?")
Задача 2. На дошці написані 10 нулів і 10 одиниць. За хід можна стерти дві будь-які цифри і написати замість них 0, якщо вони були однакові або 1, якщо вони були різні. Якщо на дошці залишається 1 - виграє перший. Якщо 0 - другий.
Задача 3. На дошці 10x12 можна за хід викреслити одну лінію (горизонталь або вертикаль, тобто рядок або стовпець) якщо в ній ще є одна невикреслена клітина.
Симетрія. Це потужний красивим, але дуже простий методом розв’язання ігрових завдань - симетрична стратегія. Суть його - робити щоразу хід, симетричний ходу супротивника або доповнює його до чого-небудь. Доказ правильності нашої стратегії буде користуватися тим, що після кожного нашого ходу позиція симетрична: раз так, то якщо противник зумів зробити свій хід, то і ми зможемо зробити хід, симетричний йому. Неправильно думати що симетрія - стратегія тільки для другого гравця. Якщо вихідна позиція - несиметрична, то зазвичай перший гравець може її якось зробити симетричною, а потім грати по симетрії, відповідаючи на ходи другого.
Задача 4 . Двоє по черзі кладуть п'ятаки на круглий стіл так, щоб вони не накладалися один на одного. (Програє, як звичайно, той, хто не може зробити хід.)
Задача 5. Двоє по черзі ставлять слонів в клітини шахової дошки так, щоб вони не били один одного (колір слонів значення не має).
Задача 6. Є дві купки каміння, по 17 у кожній. За хід можна взяти кілька каменів, з однієї купки.
Основні властивості позицій такі:
1.) Кожна позиція - або виграшна, або програшна (проміжних варіантів немає!);
2.) З виграшної позиції можна піти тільки на програшну;
3.) З будь-якої програшної позиції можна піти на виграшну.
Тоді, якщо початкова позиція - програшна, виграє перший, якщо виграшна - другий. Стратегія однакова: кожен раз ходити на виграшну позицію. Тоді суперник повинен буде походити на програшну позицію (властивість 2), а ми знову зможемо піти на виграшну (властивість 3).
Задача 7. "Хрома тура" може ходити по прямій вправо або вгору. Початково вона стоїть в нижньому лівому кутку дошки. Грають двоє. Виграє той, хто поставить туру у верхній правий кут.
Розв'язання
Розв'язання: Що значить, що гра закінчилася? Звичайно, що шоколадка вже вся розламані на окремі часточки. Часточок завжди буде 5x8 = 40 штук, а шоколадка на початку була одна. Зауважимо, що на кожному ходу один шматок шоколадки завжди розламується на 2, тобто кількість різних шматків шоколадки збільшується на 1. На початку ця кількість дорівнює 1, а в кінці, як ми помітили, 40. Значить, гра тривала рівно 39 ходів ("ходом" ми називаємо хід одного гравця, а не пару "хід - хід"). Тому останній (39-й) хід був обов'язково ходом першого (його ходи - перший, третій і всі з непарними номерами) - і перший виграв.
Ось такий вийшов жарт - як не ходи, перший завжди виграє.
Розв'язання
Розв'язання : Ну, оскільки число цифр з кожним ходом зменшується рівно на 1 (2 стираємо, одну пишемо), а на початку їх 20 і в кінці повинна залишитися одна, то гра буде продовжуватися рівно 19 ходів. Останнім ходом буде хід першого , тільки в цьому завданні не факт, що перший тоді виграє.
Виграш залежить від парності останнього числа, звернемо на це увагу. Такий стандартний інваріант, як парність суми всіх чисел, не змінюється при ходах. Дійсно, сума двох однакових цифр - парна і, віднімаючи її, ми додаємо парний нуль. А сума двох різних цифр - непарна (0 +1 = 1), і ми додаємо замість неї непарну одиницю. Початкова сума всіх чисел парна, тому що серед них парне число непарних – одиниць, тому і в кінці буде парна. А це означає, що останнє число, що залишилося в кінці гри, буде парне, тобто воно буде нулем - і виграє другий.
Заодно ми переконалися, що не в будь-якій грі той, хто робить останній хід, виграє: можна змусити (як воно тут і відбувається) суперника зробити хід, після якого він програє.
Ідея "ідіотських ходів":
Розв'язання
Розв’язання : (Так, програє той, хто не може зробити хід - якщо хто не зрозумів.) Давайте злегка переформулюємо задачу інакше: нехай лінія не викреслюється, а вирізається з дошки зі склеюванням країв розрізу. Тоді правило зміниться на - "можна вирізати будь-яку існуючу лінію" і гра закінчується, коли від дошки нічого не залишається.
Нехай раптом після свого ходу залишили, скажімо, дошку з одним рядком. Звичайно, своїм ходом суперник може вирізати цей рядок - і ми програємо. Тому такий хід був «ідіотським» - давайте так його і називати. Подивимося, коли не можна буде не зробити «ідіотського» ходу. Якщо дошка 1xN (або Nx1) - то такий хід уже зробив супротивник. Якщо ширина і висота дошки не менше 2, а більша з них - не менше 3 - то виріжемо лінію поперек більшої розмірності - і залишиться дошка хоча б 2x2. А от якщо перед ходом дошка - 2x2, то хід обов'язково буде «ідіотський». Ясно, що виграє той, хто залишить противнику дошку 2x2. На кожному ходу висота або ширина дошки зменшується на 1 (тобто, їх сума зменшується на 1). Початково ця сума дорівнює 10 +12 = 22, в кінці повинна стати 2 +2 = 4. Різниця 22-4 = 18 - парне число ходів, тому дошка 2x2 залишиться після ходу другого - і другий виграє (як у звичайній грі-жарті!).[42]
Строго кажучи: стратегія другого - грати як завгодно, тільки не роблячи «ідіотських» ходів. Якщо перший десь зробить «ідіотський» хід (а це формально заважає загнати його на дошку 2x2) - наступним ходом виграємо. Якщо ніхто не зробить «ідіотського» ходу - то після 18 ходів у першого буде дошка 2x2 - і тут він все одно зробить «ідіотський» хід.
Розв'язання
Розв’язання : Як би так першому гравцеві зробити свій хід, куди можна покласти п'ятак на порожньому круглому столі? А давайте його в центр покладемо! Увага: після такого ходу розташування п'ятаків на столі стало центрально симетричним Тепер давайте відповідати на кожен п'ятак другого гравця центрально симетричним йому п'ятаком. Чому ж стратегія ніколи не підводить (і ми не програємо)? Крах стратегії означає ,що другий поклав кудись п'ятак, а ми не змогли покласти п'ятак в симетричне місце (там вже щось лежить). Після нашого попереднього ходу позиція була симетричною (з симетричності не тільки зроблених ходів, а й самого столу), а місце, куди другий поклав п'ятак було вільне. Центрально симетричне йому місце, куди ми хочемо покласти свій п'ятак, теж було вільно. Але не міг же другий зайняти це місце своїм п'ятаком (це теж важливо відмітити, не у всіх задачах так буде!). Значить, не може бути так, щоб нам не було куди покласти свій п'ятак. Перший виграє.
Розв'язання
Розв’язання : Ну тут, здавалося б, без фокусів. Дошка має розмір 8x8, і ніяка клітина центром симетрії не буде. Тому другий може завжди відповідати на ходи першого симетричними ходами і виграє. АЛЕ: Нехай перший гравець поставив слона на діагональ дошки. Якщо другий гравець ставить свого слона в центрально симетричну клітку, то він опиниться на тій же діагоналі ... якраз під боєм слона, поставленого першим гравцем! Дійсно, буває так, що черговому симетричному ходу заважає хід, щойно зроблений супротивником (тому треба уважно стежити за такими ситуаціями!).
Вихід з положення - застосувати симетрію не центральну, а осьову (відносно середньої лінії дошки). Неважко переконатися, що клітку, симетричну своєї позиції щодо осі, слон ніколи не б'є. Після кожного ходу другого вся позиція симетрична, в т.ч. розташування не б'ющихся полів; хід першого теж не ставить під бій поле, симетричне тому, куди він був зроблений. Тому симетричне поле не б'ється. Другий завжди може зробити хід і виграє.
Розв'язання
Розв’язання : І це теж симетрія! Виграє другий - він бере з іншої купки стільки каменів, скільки перший взяв з однієї. При цьому після кожного ходу другого каменів в обох купках буде порівну - тому стратегію можна продовжувати.
А якби купки були нерівні, то виграв би перший. Першим ходом він взяв би з більшою купки стільки каменів, щоб зрівняти її з меншою, а далі користувався б стратегією симетрії. [24]
Насправді, нерідке явище: в залежності від вихідних даних одна і та ж стратегія приносить успіх то першому, то другому гравцеві.
Аналіз виграшних позицій.
Безперечно, самий потужний і універсальний спосіб розв’язання задачі -гри - пошук виграшних позицій. Тут називається виграшною та позицію, яку вигідно залишати після свого ходу, а програшною, відповідно, ту, яку невигідно (у згоді з однією половиною методичної літератури і на противагу іншій половині ) Тоді фінальна позиція, з якої вже не можна зробити хід - виграшна.
Розв'язання
Розв’язання : Початково тура стоїть на головній (в даному випадку) діагоналі дошки. Перший гравець своїм ходом веде її з діагоналі в бік. Тоді другий гравець може повернути туру назад на діагональ. Потім перший знову зрушить її з діагоналі (ходів з головної діагоналі на неї ж немає), а другий знову зможе повернути і т.д. Так як клітка призначення лежить на головній діагоналі, то на ній тура обов'язково виявиться після ходу другого - і другий виграє. [23]
Читаємо між рядків: "безліч виграшних позицій - це головна діагональ".
Аналіз з кінця: як же шукати виграшні позиції, якщо вгадати їх не вдалося? Можна просто послідовно розібрати всі позиції, починаючи з останньої (бажано, для зручності, щоб безліч позицій вміщувалося на двовимірної дошці або таблиці). Фінальна позиція виграшна. Тому всі, з яких на неї можна піти - програшні. Тепер повинні утворитися позиції, з яких можна піти тільки на програшні - вони будуть виграшними. Всі позиції, з яких можна піти на якусь із цих виграшних - програшні і т.д., поки не дійдемо до початкової позиції.
