Решение задач на выигрышную стратегию при безошибочной игре. Часть 2.
Предмет: Математика, 5 класс
Автор: Вольфсон Георгий Игоревич

Всем привет! Итак, мы кое-что уже знаем об играх. Некоторые из них – шутки, в них надо только доказать, что выигрывает всегда определённый игрок, независимо от ходов. Некоторые решаются с помощью симметрии – один из игроков копирует ходы другого и выигрывает. Но это, разумеется, не всё. И сегодня мы поговорим о таком важном методе, как анализ выигрышных и проигрышных позиций. Сразу перейдём к примеру.

Задача 1. Ладья стоит на поле a1. За ход разрешается сдвинуть её на любое число клеток вправо или на любое число клеток вверх. Выигрывает тот, кто поставит ладью на поле h8.

Решение. Сперва нарисуем доску 8 × 8. Далее, будем расставлять в клетках этой доски плюсы и минусы в зависимости от того, является ли эта клетка выигрышной или проигрышной для того, кто будет ходить ладьёй с этой клетки. Клетку h8 можем сразу отметить крестиком, туда нам надо попасть. Тогда очевидно, что клетки с а8 по g8 – выигрышные, ведь с них мы можем попасть ладьёй на h8. Аналогично, выигрышные клетки с h1 по h7. Получаем вот что:

Далее, рассмотрим клетку G7. С неё мы можем попасть только на выигрышные поля, но выигрышные они будут уже для нашего соперника! А раз он выиграет, то мы проиграем. Значит, G7 – проигрышное. А тогда все поля с А7 по F7 и с G1 по G6 – выигрышные: с них мы можем попасть на G7, которое будет проигрышным для соперника. Да, надеюсь, вы уже уловили суть: если мы можем попасть на минус – попадаем туда и соперник проигрывает, а исходное поле было выигрышным. Если же на минус мы попасть никак не можем, только на плюсы – то проиграем уже мы, так как выиграет соперник.

Аналогично, F6 – проигрышное, и так далее. Получаем такую картинку. Кстати, H8 тоже можно отметить как проигрышную: если ладья стоит там перед нашим ходом, значит, туда попал соперник – и он выиграл.

Теперь видно, что исходная позиция проигрышная, значит, начинающий проиграет, а выиграет второй. Впрочем, это пока не стратегия, не так ли? Но и со стратегией всё просто: каждый раз после хода первого мы должны попадать на минусы. В этом и есть стратегия. По сути, мы просто возвращаем ладью на главную диагональ. А как мы до этого догадались? Помогла табличка! Перейдём к следующей задаче.

Задача 2. Есть две кучки конфет, по 7 в каждой. За ход можно съесть любое количество конфет из любой кучки (но только из одной). Проигрывает тот, кто не может сделать ход.

Решение. Эту задачу мы уже решали – здесь работает симметричная стратегия, выигрывает второй. Но можно решить задачу и анализом позиций. Сделаем такую таблицу:

По горизонтали будем отмечать количество конфет в первой кучке, а по вертикали – во второй. И если, например, кто-то съел 3 конфеты из первой кучки – сдвинем фишку (исходно она, разумеется в точке 7–7) на 3 вверх, а если из второй – вправо. Но позвольте, на что-то это похоже… Конечно, ладья! Мы ходим фишкой как ладьёй – и поле такое же, 8 × 8. Значит, таблица выигрышных и проигрышных позиций будет та же. Итак, выигрывает второй!

Вы, наверное, не застали, но в моем детстве была очень популярна передача «Форт Боярд». И там был момент, когда игроки боролись против мастеров разных игр. В частности, была такая игра:

Задача 3. Есть 20 палочек. За ход можно взять одну, две или три палочки. Проигрывает тот, кто забирает последнюю палочку.

Решение. Типичная математическая игра! Обычно игроки брали палочки наобум и проигрывали. А вот знали бы математику – выигрывали бы! И сейчас мы это докажем.

Проанализируем с конца выигрышные и проигрышные позиции. Если перед нашим ходом осталась 1 спичка – мы проиграли, её придется взять. Так что 1 – проигрышная. Далее, 2, 3 и 4 – выигрышные: из них мы можем попасть на 1. 5 – проигрышная, ведь из неё можно попасть лишь на 2, 3 и 4, то есть на выигрышные для соперника позиции. Тогда 6, 7, 8 – выигрышные. 9 – проигрышная, 10, 11, 12 – выигрышные. И так далее. Не сложно видеть, что проигрышные позиции идут ровно через 4: 1, 5, 9, 13, 17, 21, … А значит 20 – выигрышная позиция!

Опять же, не забудем о стратегии. Нам же надо предъявить стратегию выигрыша, а то мало ли, может, обсчитались где-то, например. А стратегия проста: мы должны попадать на проигрышные позиции! То есть сперва забираем три спички – останется 17. Дальше дополняем ход соперника до 4 – получаем 13. Потом 9, 5, и, наконец, 1. И победа! Напоследок – ещё задача.

Задача 4. В коробке лежит 200 спичек. За ход разрешается взять из коробка не более половины имеющихся в нём спичек. Проигрывает тот, кто не может сделать ход.

Решение. Что ж, опять будем анализировать с конца. Если осталась одна спичка – мы проиграли: нельзя брать более половины спички, а ломать спички нельзя, значит, мы не можем сделать ход. Далее, 2 – выигрышная позиция, с неё можно попасть на 1. 3 – проигрышная, можем взять только 1 спичку и попадаем на выигрышную (2). 4 – выигрышная, попадаем на 3. Точно так же выигрышными являются 5 и 6, с них тоже можно попасть на 3. А вот 7 – проигрышная, если из 7 вычесть 1, 2 или 3 – попадаем на выигрышные для соперника. Далее, от 8 до 14 – выигрышные, попадаем на 7. 15 – проигрышная. 16–30 – выигрышные, 31 – проигрышная. 32–62 – выигрышные, 63 – проигрышная. 64–126 – выигрышные, 127 – проигрышная. 128–254 – выигрышные, а значит, 200 – выигрышная! Ура! Ну а теперь стратегия. Берём 73 спички, остаётся 127. Далее, добираем до 63 (это всегда можно сделать, так как 63 – не больше половины остатка), затем до 31, 15, 7, 3 и 1. Победа за первым!

Итак, сегодня мы научились анализировать игры с конца, используя выигрышные и проигрышные позиции. Не забудьте потренировать эту идею – и до скорой встречи!

Дополнительная информация

Рекомендуемые тренажёры:

1. Король стоит на поле a1. За один ход его можно передвинуть на одно поле вправо, или на одно поле вверх, или на одно поле по диагонали «вправо-вверх». Выигрывает тот, кто поставит короля на поле h8. Кто выиграет в этой игре? Ответ: первый.

2. На доске написано число 0. За ход можно добавить к числу на доске любую цифру от 1 до 9. Выигрывает тот, кто получает число 100. Кто выиграет в этой игре? Ответ: второй.

3. Имеются две кучки конфет: в одной – 20, в другой – 21. За ход нужно съесть одну из кучек, а вторую разделить на две не обязательно равных кучки. Проигрывает тот, кто не может сделать ход. Кто выиграет в этой игре? Ответ: первый.

Рекомендуемые тесты:

1. Есть две кучки конфет, по 7 в каждой. За ход можно съесть одну конфету из любой кучки или из обеих сразу. Проигрывает тот, кто не может сделать ход. Кто выиграет в этой игре? Ответ: первый.

2. В коробке лежит 26 спичек. За ход разрешается взять из коробка не более четверти имеющихся в нём спичек. Проигрывает тот, кто не может сделать ход. Кто выиграет в этой игре? Ответ: второй.

3. Игра начинается с числа 60. За ход разрешается уменьшить имеющееся число на любой из его делителей. Проигрывает тот, кто получит ноль. Кто выиграет в этой игре? Ответ: первый.