Текст завдання. Два гравці, Петя і Ваня, грають в наступну гру. Перед гравцями лежать дві купи каміння. Гравці ходять по черзі, перший хід робить Петя. За один хід гравець може додати в одну з куп (за власним вибором) один камінь або збільшити кількість каменів в купі в два рази. Наприклад, нехай в одній купі 10 каменів, а в іншій 7 каменів; таку позицію в грі будемо позначати (10, 7). Тоді за один хід можна отримати будь-яку з чотирьох позицій: (11, 7), (20, 7), (10, 8), (10, 14). Для того щоб робити ходи, у кожного гравця є необмежена кількість каменів.
Гра завершується в той момент, коли сумарна кількість каменів в купах стає не менш 73. Переможцем вважається гравець, який зробив останній хід, т. Е. Першим отримав таку позицію, що в купах за все буде 73 каменю або більше.
Будемо говорити, що гравець має виграшну стратегію. якщо він може виграти за будь-яких ходах супротивника. Описати стратегію гравця # 151; значить описати, який хід він повинен зробити в будь-якій ситуації, яка йому може зустрітися при різній грі противника. Наприклад, при початкових позиціях (6, 34), (7, 33), (9, 32) виграшна стратегія є у Петі. Щоб виграти, йому досить подвоїти кількість каменів у другій купі.
Завдання 1. Для кожної з початкових позицій (6, 33), (8, 32) вкажіть, хто з гравців має виграшну стратегію. У кожному разі опишіть виграшну стратегію; поясніть, чому ця стратегія веде до виграшу, і вкажіть, яке найбільшу кількість ходів може знадобитися переможцю для виграшу при цій стратегії.
Завдання 2. Для кожної з початкових позицій (6, 32), (7, 32), (8, 31) вкажіть, хто з гравців має виграшну стратегію. У кожному разі опишіть виграшну стратегію; поясніть, чому ця стратегія веде до виграшу, і вкажіть, яке найбільшу кількість ходів може знадобитися переможцю для виграшу при цій стратегії.
Завдання 3. Для початкової позиції (7, 31) вкажіть, хто з гравців має виграшну стратегію. Опишіть виграшну стратегію; поясніть, чому ця стратегія веде до виграшу, і вкажіть, яке найбільшу кількість ходів може знадобитися переможцю для виграшу при цій стратегії. Побудуйте дерево всіх партій, можливих при зазначеній Вами виграшної стратегії. Уявіть дерево у вигляді малюнка або таблиці.
Рішення. Дане завдання відноситься до першого типу (див. Теоретичне введення), оскільки в ній йдеться про те, що "виграє гравець. Робить хід # 133;" Значить, при побудові дерева гри будемо маркувати як такі, що суперечать умові такі результати ходів, здійснення яких призведе згодом хоча б до однієї можливості виграшу іншого гравця.
Виконаємо перше завдання.
Проаналізуємо спочатку слідства першої початкової позиції.