Теория игр: выигрышные и проигрышные позиции

1. 1. Шаг 0. Два определения, на которых держится вся теория игр. Позиция проигрышная (П), если из неё любой ход ведёт в выигрышную позицию соперника. Позиция выигрышная (В), если существует хотя бы один ход в проигрышную позицию соперника.
2. 2. Шаг 1. n = 0. Камней нет, ходить нечем, значит последний камень взял соперник — он и выиграл. Для того, чей ход, это П.
3. 3. Шаг 2. n = 1. Берём один камень, оставляем сопернику позицию 0, которая для него П. Значит наша позиция В.
4. 4. Шаг 3. n = 2. Берём два камня — снова оставляем 0, то есть П для соперника. В.
5. 5. Шаг 4. n = 3. Ходы ведут в 2 (В) и в 1 (В). Все ходы дают сопернику выигрышную позицию, значит наша П. Это первая нетривиальная проигрышная позиция.
6. 6. Шаг 5. n = 4. Ход «взять 1» ведёт в 3, а это П для соперника. Значит В. n = 5: ход «взять 2» ведёт в 3 — тоже В.
7. 7. Шаг 6. n = 6. Ходы ведут в 5 (В) и 4 (В) — все выигрышные для соперника, значит П.
8. 8. Шаг 7. Продолжаем: n = 7 — В (ход в 6), n = 8 — В (ход в 6).
9. 9. Шаг 8. Таблица целиком: 0 — П, 1 — В, 2 — В, 3 — П, 4 — В, 5 — В, 6 — П, 7 — В, 8 — В.
10. 10. Шаг 9. Закономерность видна сразу: проигрышными оказались позиции, кратные трём. Объяснение простое: сколько бы соперник ни взял (один или два), вы всегда можете дополнить его ход до трёх и снова оставить ему кратное трём. Эта стратегия «дополнения до постоянной суммы» — классика игр со взятием.
11. 11. Шаг 10. Главное, что стоит унести из разметки: она строится от конца к началу. Сначала размечаются терминальные позиции, потом те, что ведут в них, и так далее. Пытаться размечать с начала бессмысленно — значение позиции определяется тем, что будет дальше, а не тем, что было раньше.

Ответ: П на позициях 0, 3, 6; В на остальных

1. 1. Шаг 0. Введём короткое название. Позицию назовём скорой, если ходящий выигрывает первым же ходом: у него есть ход, дающий не больше 30 камней. Все остальные позиции — не скорые: за один ход из них не выиграть.
2. 2. Шаг 1. Какие позиции скорые. Ход «−3» даёт ≤ 30 при S ≤ 33; «−6» — при S ≤ 36; «деление на 3» — при S ≤ 92, потому что ⌊92/3⌋ = 30, а ⌊93/3⌋ = 31. Значит, скорые — это все S от 31 до 92, а первая позиция, откуда за один ход не выиграть, это S = 93.
3. 3. Шаг 2. Проверим 93 на первое условие. Ходы из 93: 93 − 3 = 90, 93 − 6 = 87, ⌊93/3⌋ = 31. Все три больше тридцати, значит Петя за один ход не выигрывает ✔
4. 4. Шаг 3. Теперь второе условие: из каждой из трёх позиций Ваня должен выиграть первым ходом.
5. 5. Ветвь 90: ходы 87, 84 и ⌊90/3⌋ = 30. Тридцать — это уже не больше тридцати, игра кончена, ходил Ваня ✔
6. 6. Ветвь 87: ходы 84, 81 и ⌊87/3⌋ = 29. Двадцать девять ≤ 30 ✔
7. 7. Ветвь 31: ходы 31 − 3 = 28 ✔ (а также 25 и 10 — все подходят).
8. 8. Шаг 4. Все три ветви дерева дошли до победы Вани его первым ходом. Дерево построено целиком: корень 93, три ветви, в каждой Ваня заканчивает игру ✔
9. 9. Шаг 5. Осталось убедиться, что 93 — минимальное. Все S от 31 до 92 отпадают по первому условию: там Петя выигрывает сразу делением на три. Значит, меньших кандидатов нет, и ответ 93.
10. 10. Шаг 6. Заметьте, что 94 и 95 тоже удовлетворяют обоим условиям — их ходы ведут в 91, 88, 31 и 92, 89, 31 соответственно, и Ваня отовсюду добивает. Но вопрос просит минимальное, поэтому в ответ идёт 93.
11. 11. Шаг 7. Полезный вывод про технику: сначала определите границу, где кончаются скорые позиции, и только потом стройте дерево. Перебирать все S подряд от 31 не нужно — достаточно понять, какой ход «дотягивается» до конца игры дальше всех. Здесь это деление на три, и оно даёт границу 92.

Ответ: 93

1. 1. Шаг 1. Условие требует двух вещей сразу. Первая: Петя не выигрывает сразу, то есть S не скорая, значит S ≥ 93. Вторая: у Пети есть такой первый ход, после которого при любом ответе Вани Петя добивает.
2. 2. Шаг 2. Ключевая мысль: Петя должен пойти в позицию, из которой Ваня не выигрывает, а все его ходы ведут в скорые позиции для Пети. Такая позиция у нас уже есть — это 93, разобранная в предыдущем примере: из неё ходы ведут в 90, 87 и 31, и из каждой Петя выигрывает первым ходом.
3. 3. Шаг 3. Значит, ищем такие S, из которых можно за один ход попасть в 93. Ход «−3» даёт 93 при S = 96. Ход «−6» — при S = 99. Деление на три даёт 93 при S от 279 до 281 — это далеко.
4. 4. Шаг 4. Проверяем 96. Ходы: 93, 90 и ⌊96/3⌋ = 32. Ни один не кончает игру, значит Петя сразу не выигрывает ✔ Петя выбирает ход в 93, и дальше по разобранной схеме выигрывает вторым ходом ✔
5. 5. Шаг 5. Проверяем 97. Ходы: 94, 91 и 32. Сразу не выигрывает ✔ Пойдёт ли он в 94? Ходы из 94: 91, 88 и 31 — все не кончают игру, и из каждой Петя выигрывает первым ходом (91 → 30, 88 → 29, 31 → 28) ✔ Значит, 97 тоже подходит.
6. 6. Шаг 6. Проверяем 93, 94 и 95, которые меньше. Они не подходят: из них Ваня выигрывает первым ходом при любом ходе Пети — это и было содержанием линии 19. Выигрышной стратегии у Пети там нет.
7. 7. Шаг 7. Значит, два наименьших значения — 96 и 97. В бланк они записываются подряд, без разделителей: 9697.
8. 8. Шаг 8. Обратите внимание на структуру ответа. Позиции 93, 94, 95 — проигрышные для Пети; 96, 97, 98, 99 — выигрышные, причём победа приходит вторым ходом. Такие «полосы» типичны для игр со взятием: значения группируются блоками, и найдя границу блока, остальные можно не проверять.

Ответ: 96 и 97, ответ записывается как 9697

1. 1. Шаг 1. Разберём условие на части. Первое: Петя не выигрывает первым ходом (иначе у Вани вообще нет хода). Второе: при каждом ходе Пети Ваня выигрывает — первым или вторым своим ходом. Третье: хотя бы в одной ветви Ване первого хода не хватает, иначе это была бы линия 19.
2. 2. Шаг 2. Позиции 93, 94 и 95 отпадают: там Ваня выигрывает всегда первым ходом, а третье условие требует обратного.
3. 3. Шаг 3. Позиции 96–99 отпадают по другой причине: там выигрышная стратегия у Пети, а не у Вани.
4. 4. Шаг 4. Проверяем 102. Ходы Пети: 102 − 3 = 99, 102 − 6 = 96, ⌊102/3⌋ = 34. Ни один не кончает игру, значит Петя сразу не выигрывает ✔
5. 5. Шаг 5. Ветвь 34. Ваня ходит 34 − 6 = 28, это не больше тридцати — победа первым ходом ✔
6. 6. Шаг 6. Ветвь 99. Первым ходом Ваня не выигрывает: 96, 93 и 33 — все больше тридцати. Зато он ходит в 93, и дальше знакомая картина: что бы Петя ни выбрал (90, 87 или 31), Ваня добивает вторым ходом ✔
7. 7. Шаг 7. Ветвь 96. Первым ходом тоже не выигрывает: 93, 90 и 32. Ваня снова идёт в 93 и выигрывает вторым ходом ✔
8. 8. Шаг 8. Итог: во всех трёх ветвях Ваня выигрывает, но в двух из них ему нужен второй ход. Оба условия выполнены, и 102 подходит.
9. 9. Шаг 9. Осталось убедиться в минимальности, то есть проверить 100 и 101. Из 100 Петя может пойти в 94, а это позиция из линии 19: там ходит Ваня, первым ходом он не выигрывает, а Петя добивает своим следующим ходом. Значит, при S = 100 у Вани выигрышной стратегии нет.
10. 10. Шаг 10. Из 101 Петя точно так же ходит в 95 — снова позиция линии 19, снова выигрывает Петя. Поэтому 100 и 101 отпадают, и наименьшим подходящим значением остаётся 102.
11. 11. Шаг 11. Программа из соседнего урока перебирает все S подряд и печатает 102 как наименьшее. Ручной разбор нужен, чтобы понимать структуру ответа и уметь проверить машину — но на экзамене за две минуты надёжнее запустить перебор.
12. 12. Шаг 12. Общий приём для всех трёх линий: ключевой позицией оказывается одна и та же — 93. Она проигрышная для ходящего, и вокруг неё выстраиваются ответы всех трёх заданий. Найдя такую опорную позицию, вы фактически решаете весь блок 19–21 сразу.

Ответ: 102