11.1. приклади ігор

11.1.1. Двоє грають в таку гру: на столі лежить сірників; грають по черзі можуть взяти від до сірників; хто не може зробити ходу (сірників не залишилося) - програє. Хто виграє при правильній грі?

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

11.1.2. Хто виграє - перший або другий - якщо сірників НЕ , а ?

Рішення. Перший: якщо він візьме три сірники, то стане другим в уже розібраної грі і тому зможе виграти.

Аналогічно виходить відповідь і для довільного числа сірників ( ): Якщо кратно п'яти, то виграє другий, а якщо немає, то перший.

11.1.3. Змінимо умови гри: нехай взяв останній сірник програє. Хто тепер виграє при правильній грі?

11.1.4. Нехай тепер гравцям дозволено брати , або сірники, а хто не може зробити хід, програє. Хто виграє при правильній грі, якщо спочатку було сірників?

Рішення. Тут вже не так просто відразу вказати виграшну стратегію для першого або другого. Почнемо з невеликого числа сірників, зобразивши дозволені ходи у вигляді стрілок ( Мал. 11.1. ): Гравець, який опинився в позиції , Програє (такі правила), тому відповідний гурток пометим буквою П. Гравець, який опинився в позиціях , або , Виграє, оскільки він може забрати все сірники і перевести супротивника по стрілці в позицію . Тому ми помітимо ці позиції буквою В. Тепер ясно, що позиція є програшною: з неї можна піти тільки в і , І тоді противник (як ми вже знаємо) виграє. Помітимо її буквою П. Далі помічаємо, що позиції , і будуть виграшними (оскільки з них можна потрапити в програшну для противника позицію ; зауважимо, що з позиції можна виграти і швидше, пішовши в ). Тепер видно, що позиція програшна (всі стрілки з неї ведуть в виграшні для противника позиції), - виграшна, - програшна і так далі з періодом .

Мал.11.1.

Гра з сірниками

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

11.1.5. Як він для цього повинен грати?

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

11.1.6. На столі лежать дві купки сірників: в одній , в інший . За один хід дозволяється взяти будь-який (нульове) число сірників, але тільки з однієї купки (можна взяти все сірники в ній); хто не може зробити хід, програє. Хто виграє при правильній грі?

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

11.1.7. На шахівниці стоїть тура, яку гравці по черзі рухають, при цьому дозволено зрушувати її вліво і вниз (залишати на місці не можна); хто не може зробити хід, програє. Хто виграє при правильній грі?

Вказівка. Як ця гра пов'язана з попередньою?

11.1.8. є купок з сірників; за один хід можна взяти будь-який (нульове) число сірників, але тільки з однієї купи (можна взяти все сірники в ній); хто не може зробити хід, програє. Хто виграє при правильній грі?

Рішення. запишемо числа в двійковій системі числення один під одним, як якщо б ми збиралися їх складати. Якщо в кожному розряді при цьому виявилося парне число одиниць, то виграє другий, в інших випадках - перший. Справді, якщо у всіх розрядах парне число одиниць, то після зменшення одного з чисел якийсь із його розрядів зміниться і в цьому розряді вийде парне число одиниць. (Це відповідає тому, що з програшній позиції будь-який хід веде в виграшну.) Якщо ж в деяких ( "поганих") розрядах непарне число одиниць, візьмемо старший поганий розряд і то з чисел, яке містить в цьому розряді одиницю. Тоді, змінивши в цьому числі всі погані розряди, отримаємо менше число, яке поставить противника в програшну позицію. (Див. Правила для виграшних і програшних позицій в наступному розділі.)

11.1.9. В ряд лежать ящиків, в кожному з них по монеті. За один хід гравець може взяти будь-яку монету або будь-які дві монети з сусідніх ящиків; хто не може зробити хід, програє. Хто виграє при правильній грі?

Рішення. Перший: він повинен взяти одну або дві монети в центрі, а потім симетрично повторювати ходи другого.