(057-41) 5-23-18

Задачі на стратегію гри ЗАВАНТАЖИТИ

Теорія

            У математичних іграх припускається, що грають двоє (інколи троє), ходи роблять по черзі (жоден із гравців не може пропустити хід), при чому гравці не роблять помилок. А тому в таких іграх на перед можна визначити кінцевий результат, тобто передбачити, який з гравців може забезпечити собі виграш. Для розв’язання задачі-гри необхідно сформулювати виграшну стратегію одного з гравців та довести, що така стратегія веде до виграшу.       Серед ігрових задач зустрічаються ігри-жарти, тобто ігри, результат яких не залежить від того, як грають суперники.                                                                         У багатьох ігрових задачах виграшна стратегія досягається за допомогою вдалого ходу-відповіді на будь-який хід суперника. Існування такого ходу може забезпечуватись симетрією, розбиттям на пари, доповненням до числа.                                                              Найбільш поширеними є симетричні й парні стратегії, а також стратегії, які будуються на основі аналізу ігрових позицій.                                                                             Симетричні стратегії – це виграшні стратегії, розроблені на основі симетрії стартової позиції гри. Аналіз розв’язування таких задач показує, що в іграх із симетричною стартовою позицією здебільшого виграє той, хто не порушує її симетрії, а порушену суперником симетрію стартової чи ігрової позиції може поновити. Цей простий висновок часто допомагає здобути перемогу в ігрових задачах з симетричною стартовою позицією.     Виграшні позиції що характеризується такими властивостями:      

                   а) за один хід з однієї виграшної позиції не можна перейти до іншої виграшної                   позиції;                                                                                                    б) з будь-якої невиграшної позиції за один хід можна перейти до деякої виграшної (відмінної від попередньої виграшної) позиції.                                                  Знаходження такого класу виграшних позицій для гри рівносильна її розв’язанню. До перемоги веде стратегія – перехід до виграшних позицій. При цьому, якщо початкова позиція виграшна, то виграє другий гравець, а в протилежному випадку виграє той, що починає. Пошук виграшних позицій в більшості випадків доцільно проводити за допомогою аналізу кінцівки гри, іноді до таких позицій можна дійти інтуїтивно.      

Симетрія ігрових позицій забезпечує існування множини пар «прообраз – образ». У розглянутих задачах такими є пари клітинок таблиць, пари пелюсток ромашки, пари чисел виразу тощо. Гравець, дбаючи про симетрію ігрової позиції, зберігав пари «прообраз-образ». Він давав можливість супернику під час виконання ходу використовувати «прообраз» із цим самим гарантував можливість виконання свого наступного ходу, використовуючи симетричний «образ».       

Іноді пари, подібні симетричним парам, можна використовувати і в задачах,  стартова позиція яких не є симетричною. Виграшну стратегію, яка передбачає використання пар, називають парною стратегією. Зазначимо, що конкретних порад щодо вибору «пар» не існує. Кожного разу виділення «пар» здійснюється, виходячи з умови конкретної задачі.       Розглянемо спосіб побудови стратегії успіху, який базується на аналізі ігрових позицій. Ігрову позицію називають виграшною, якщо існує такий хід гравця, який забезпечує йому виграш. Ігрову позицію називають програшною, якщо з неї не можна виграти. Якість ігрової позиції визначається перед ходом гравця і не залежить від того, який хід виконуватиме гравець. Після виконання ходу виграшна позиція перетворюється у програшну, а програшна – у виграшну. Аналіз ігрових позицій здебільшого варто починати з фінальної частини гри. Аналізом ігрових позицій треба визначити, чи є стартова позиція виграшною, чи вона програшна. Гравець, який починає гру з виграшної позиції за правильної гри завжди виграє, а гравець, який починає гру з програшної позиції – програє за правильної гри свого суперника.

Приклади розв’язування задач.

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

 Розв'язання. Наприкінці гри, коли не можна зробити хід, маємо 45 куп по одному каменю. За будь-який хід кількість куп збільшується на одиницю, тому вся гра має тривати точно 45 - 3 = 42 ходи.

Отже, другий гравець з'авжди виграє.

Задача2. Двоє гравців по черзі виймають із двох ящиків кулі. За один хід кожен гравець може брати з будь-якого (тільки одно­го) ящика довільну кількість куль. Виграє той, хто бере останнім. Як має грати той гравець, що починає, щоб виграти, якщо в першому ящику 73 кулі, а в другому - 118 куль?

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

Задача 3. Оксана й Оленка обривають на ромашці пелюстки. За один раз можна зірвати будь-яку одну пелюстку або дві, які розташовані поруч. Виграє та дівчина, яка зірве останню пелюстку. Гру починає Оксанка. Хто виграє, якщо на ромашці: а) 24 пелюстки? б) 25 пелюсток.

         Розв’язання. а) Виграє Оленка, якщо, будуючи свою стратегію гри, використає центральну симетрію стартової позиції.

         б) У цьому випадку стартова позиція гри має осьові симетрії. Їх усього 25 – стільки, скільки ромашка має пелюсток. Оксанка своїм першим ходом не порушить симетрії відносно однієї з цих осей. Але своїм першим ходом й Оленка може не порушити симетрії. Для цього їй треба так зірвати одну або дві пелюстки, щоб між зірваними пелюстками їх залишилось по 11. Другим ходом Оксана вже змушена порушити симетрію. Відповідаючи за кожний хід Оксанки, Оленка щоразу може поновлювати симетрію ігрових позицій, що врешті-решт забезпечить їй перемогу у грі.

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

Розв’язання. Для розв'язання задачі розглянемо прямокутну клітчату таблицю розміром 24х 33 клітинки. Клітинки пронумеруємо так, як показано на рисунку З.З. Тоді номери клітинок по горизонталі відпові­датимуть кількості цукерок у другій коробці, а по вертикалі – у першій. Поставимо на клітинку, що міститься в лівому нижньому кутку таблиці, тобто клітинку (23; 32), фішку. Таке положення фішки відповідатиме стартовій позиції гри. Якщо з першої коробки дівчинка бере одну цукерку, то фішка зміщується на одну клітинку по горизонталі праворуч, якщо одну цукерку взяти з другої коробки - фішка зміщу­ється на одну клітинку по вертикалі вгору, якщо ж взяти по одній цукерці з обох коробок, то фішка зміститься по діагоналі праворуч і вгору. Переміщення фішки по клітинках таблиці відповідає переміщенню короля по клітинках шахівниці (див. задачу 3.12). Гра завершиться, коли обидві коробки будуть порожні - фішка стоятиме на верхній правій  клітинці таблиці. Використовуючи результати аналізу ігрових позицій, проведеного в попередній задачі, доходимо висновку, що програшним позиціям гри відповідатимуть клітинки .таблиці з парними номерами. Отже, стартова позиція гри – виграшна позиція, а тому виграє дівчинка, яка починає гру. Для того щоб виграти, їй треба залишати після свого ходу в обох коробках парну кількість цукерок.

Рис. 3.3

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

Задача 5. У коробці знаходиться 60 сірників. За один хід можна взяти будь-яку кількість від 1 до 5 сірників. Програє той, хто не може зробити хід. Хто з гравців       (перший чи другий) може забезпечити собі виграш?

Розв'язання. Проаналізуємо кінцівку такої гри. Якщо кількість сірників менша за 5, то той гравець, чия черга ходити, закінчує гру. Якщо кількість сірників більша за 6, то гра закінчиться через два або більше ходи. Якщо ж кількість сірників дорівнює 6, то гравець, чий хід передував цій позиції, точно наступним своїм ходом закінчує гру (для цього він на хід суперника в k сірників бере 6 - k сірників). Тобто  така позиція є виграшною для цього гравця. Очевидно, що позиції 12, 18, 24 (і т. д.) сірників для нього також є виграшними, бо таким самим способом він від позиції "24 сірники" переходить до позиції" 18 cipників", від" 18 " до "12".

Oтже, початкова позиція виграшна для другого гравця, а його виграшною стратегією є доповнення ним ходів першого гравця до 6 cipників.

Задачі для самостійного розв’язування.

Задача 1 . На столі лежать 1978 сірників. Два хлопчики по черзі можуть брати один чи два сірники. Який хлопчик виграє і як він має грати для цього?

 Відповідь: Перший гравець. Перший хід – 1 сірник, виграшна стратегія –доповнення до 3.

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

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

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

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

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

Відповідь: Перший гравець; перший хід він робить у центральну клітинку, потім робить симетричні ходи – відповіді.

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

 Відповідь: Виграшні позиції: 500, 250,125,62,31,15,7,3. Перший гравець.

Рекомендована література:

1. Вороний О.М. Готуємось до олімпіад з математики. – Х.:вид. група «Основа»,2008. – 255, [1] с.
2. Сарана О.А. Математичні олімпіади: просте і складне поруч: навч. посібн. – К.: Видавництво А.С.К., 2004.-344с.

3. ЗАДАЧІ НА СТРАТЕГІЮ ГРИ

    

   1. Двоє гравців по черзі кладуть п'ятикопійчані монети на круглий
   стіл. Монети повинні повністю вміщуватися на столі і не торкатися одна
   одної. Той, кому нікуди покласти монету, програє. Хто за умови дотримання правил гри виграє — той, хто ходить першим, чи той, хто ходить другим?

   Розв'язання

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

    

   2. Дано шахівницю 8x8 і прямокутне доміно 1x2. За один хід дозво­ляється накрити дві сусідні клітинки шахівниці так, щоб плитки доміно не перекривались. Програє той, хто не зможе зробити наступного ходу. У котрого з двох гравців є виграшна стратегія?

   Розв'язання

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

    

   3. Двоє гравців по черзі виймають із ящиків кулі. За один хід кожен
   гравець може брати з будь-якого (тільки одного) ящика довільну кількість
   куль. Виграє той, хто візьме останнім. Як повинен грати перший гравець,
   щоб виграти, якщо в першому ящику 73 кулі, а в другому — 118 куль?

   Розв'язання

   Першим ходом він має взяти 45 куль із другого ящика, тоді куль в ящи­ках стане порівну. А далі відповідати симетрично на ходи другого гравця.

    

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

   Розв'язання

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

    

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

   Розв'язання

   Другий гравець виграє без будь-якої стратегії. Після кожного ходу кількість купок збільшується на 1. У кінці гри їх має стати 45, буде зробле­но 42 ходи. Отже, останній хід зробить другий гравець.

    

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

   Розв'язання

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

    

   7. У коробці знаходиться 60 сірників. За один хід можна взяти від 1
   до 5 сірників. Програє той, хто не може зробити хід. Хто з двох гравців
   може забезпечити собі виграш?

   Розв'язання

   Проаналізуємо кінцівку такої гри. Якщо кількість сірників менша ніж 5, то той гравець, чия черга ходити, закінчує гру. Якщо кількість сірників більша за 6, то гра закінчується через два або більше ходів. Якщо ж кількість сірників дорівнює 6, то гравець, чий хід передував цій позиції, точно наступним своїм ходом закінчує гру (для цього на хід суперника в к сірників бере 6-k сірників) Тобто, така позиція є виграшною для цього гравця. Очевидно, що позиції 12, 18, 24 тощо сірників для нього також є виграшними. Отже, початкова позиція виграшна для другого гравця, а його виграшною стратегією є доповнення ним ходів першого гравця до 6 сірників.

    

   8. Двоє грають у подвійні шахи, тобто всі фігури ходять як і в звичай­них шахах, але кожен із шахістів робить по два ходи підряд. Доведіть, що шахіст, який грає білими фігурами, може грати так, щоб не програти (тобто другий не має виграшної стратегії).

   Розв'язання

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

    

   9. На дошці написано вираз *п⁸ *п⁷ *п⁶ *п⁵ *n⁴ *п³ *п² *. Петрик і Оксана ведуть у таку гру. Вони роблять ходи по черзі, замінюючи одну зірочку «*» на знак «+» або «-». Оксана прагне, щоб здобутий після восьми ходів вираз ділився на 6 для кожного натурального п. Петрик ходить першим. Доведіть, що Оксана може забезпечити собі перемогу незалежно від того, як ходитиме Петрик.

   Розв'язання

   Зауважимо, що число n⁵ – п = п(п - 1)(п + 1)(п² + 1) ділиться на 6. Тому Оксані достатньо грати так, щоб числа п⁸і n⁴, п⁷і n³, п⁶і п², n⁵і n були з різними знаками.

    

   10. Двоє гравців у запису

   a₁ sin x + a₂cos 2x + a₃ sin 3x + a₄ cos 4x +... + a₂₀₀₄ cos 2004x + a₂₀₀₅ sin2005x = 0

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

   з двох гравців може забезпечити собі перемогу в цій грі?

   Розв'язання

   Виграє перший гравець. Першим ходом він довільно замінює коефі­цієнт а₁, а потім, користуючись тим, що серед решти коефіцієнтів їх кількість з парними і непарними номерами є число парне, забезпечує собі можливість зробити останнім заміну серед коефіцієнтів а₂, a₄, ...,а₂₀₀₄. Тому перший гравець може зробити так, щоб f(0) = 0, оскільки f(0) = а₂ + а₄ + ... + а₂₀₀₄.

    

   11. Миколка та Сергійко грають у гру, по черзі записуючи цілі числа в клітинки таблиці розмірами 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₇будуть парними.

    

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

   Розв'язання

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

    

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

   Розв'язання

   Нехай гравці роблять розпили, після яких дошка не розпадається. Кожний новий розпил, очевидно, повинен досягати ще одного з (n – 1)²внутрішніх «вузлів» дошки (вершини квадратиків). З іншого боку, якщо до якогось з таких вузлів розпили не дійшли, то можна зробити ще один розпил так, щоб дошка не розпалася: провести від такого вільного вузла лінію до якогось розпилу по сторонах квадратиків і продовжити згаданий розпил на одиницю по цій лінії. З цих міркувань випливає, що за пра­вильної гри всього до розпадання дошки можна зробити рівно (n – 1)² роз­пилів незалежно від того, в якому порядку вони виконувались. Тому ((n – 1)² + 1) хід буде програшний. Отже, при парному п виграє перший гра­вець, а при непарному— другий.

    

   14. Двоє гравців по черзі ставлять на клітинки шахової дошки 25  25 фішки, один — білого, а другий — чорного кольорів. Кожна нова фішка ставиться на вільну клітинку, забороняється лише ставити фішку на таку клітинку, де на всіх сусідніх із нею клітинках уже стоять фішки цього кольору (сусідніми вважають клітинки, які мають спільну сторону). Про­ грає той, хто не може зробити свій черговий хід. Хто виграє за умови правильної гри — перший чи другий?

   Розв'язання

    

4. Виграє перший гравець. Справді, виділи­мо одну із клітинок, а решту розіб'ємо на частини 1  2. Розглядаємо такий випадок: правий верхній кут дошки покрито квадра­том розмірами 1x1, а решту дошки — прямо­кутниками розмірами 1  2. Перший гравець першу фішку ставить у виділену клітинку, а кожну наступну — у вільну клітинку тієї частини розміром 1  2, в яку попереднім хо­дом поставив свою фішку другий гравець. Очевидно, що все це завжди можна зробити.

    

   15. На столі стоять п'ять коробок, позначених номерами 0, 1, 2, 3, 4.
   У коробках з номерами 1, 2, 3, 4 знаходяться відповідно p₁, р₂, р₃, р₄сірни­ків. По черзі кожний із двох гравців бере кілька сірників з якоїсь коробки з додатним номером та перекладає їх у коробку, номер якої на одиницю менший. Виграє той гравець, після ходу якого всі сірники будуть у нульовій коробці. Хто виграє за умови правильної гри — той, хто починає гру, чи його суперник?

   Розв'язання

   Доведемо, що у випадку р₁ = р₂Другий гравець завжди може виграти. Його відповідь на можливі ходи першого гравця видно з наступної схеми:

   (р₀ + k, p₁ – k, p₂, p₄) → (p₀ + k, р₁ - k, р₂ + k, р₃ - k, р₄)

   (р₀, p₁ + k, р₂ – k, р₄) → (р₀ + k, р₁, р₂ – k, р₃, р₄)

   (р₀, p₁, р₂ + k, р₃ – k, р₄) → (р₀ + k, р₁ – k, р₂ + k, р₃ – k, р₄)

   (р₀, p₁, р₂, р₃ + k, р₄ – k) → (р₀, р₁, р₂ + k, р₃, р₄ – k)

   Таким чином, перший гравець своїм ходом обов'язково порушує рівність сірників у першій та третій коробках, а другий завжди має мож­ливість своїм наступним ходом цю рівність відновити. Оскільки в за­ключній позиції кількість сірників у першій і третій коробках однакова (дорівнює 0), то другий гравець за такої стратегії завжди виграє. Якщо р₁ ≠ р₂, то перший гравець своїм першим ходом завжди може вирівняти кількість сірників у першій та третій коробках, і ми отримаємо про­аналізовану вище ситуацію зі зміною номерів гравців. Отже, у випадку р₁ = р₃виграє другий гравець, в усіх інших випадках – перший.

    

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

   Розв'язання

   Доведемо, що другий гравець може забезпечити собі перемогу. Якщо число я парне, то він має на кожний хід першого гравця відповідати ходом у симетричну відносно головної діагоналі клітинку (на хід у клітинку, яка розташована на головній діагоналі, потрібно відповідати довільним ходом також на цю діагональ). Якщо число я є непарним, то другий гравець у ви­падку, коли можна зробити відповідні ходи, має діяти так само, як описано вище, а коли потрібний хід не виявляється можливим, потрібно просто зро­бити будь-який хід. Оскільки, як відомо, для будь-яких натуральних чисел а і b має місце рівність HCД(a;b)∙НCK(a;b)=ab, то добуток всіх чисел у таб­лиці дорівнюватиме(п!)ⁿ. Очевидно, що після ділення дістанемо в добутку число 1, що й означає перемогу другого гравця.