Вера и Глеб играют в игру. Перед ними стоит шкатулка, в которой лежит 4 пуговицы. Игроки по очереди кладут в шкатулку 3 или 7 пуговиц. Выигрывает тот, кто своим ходом доведет…
Вера и Глеб играют в игру. Перед ними стоит шкатулка, в которой лежит 4 пуговицы. Игроки по очереди кладут в шкатулку 3 или 7 пуговиц. Выигрывает тот, кто своим ходом доведет количество пуговиц до 94. Первый ход сделала Вера и положила 7 пуговиц. У кого из игроков есть беспроигрышная стратегия? Напишите в ответе первую букву имени игрока и количество пуговиц, которое он должен положить в шкатулку в свой ближайший ход. Ответ оформите как в примере. Пример: В3 (Вера положила 3 пуговицы). Примечание: игрок имеет беспроигрышную стратегию, если он может выиграть при любых ходах противника.
Дано: шкатулка начинается с 4 пуговиц. Вера ходила первой и положила 7, значит текущий итог: 4 + 7 = 11. Остаток до 94 равен R = 94 − 11 = 83.
Обозначим R как количество оставшихся пуговиц, которые нужно добавить, чтобы достигнуть 94. За ход игрок уменьшает R на 3 или 7. Применим разбор по выигрышным и проигрышным позициям (P/N).
- Проигрышные позиции (P), т.е. такие, где ходящий проигрывает при оптимальной игре, это те R, у которых остаток по модулю 10 равен 0, 1, 2 или 6. Это можно проверить малыми значениями и подтвердить индуктивно: если R mod 10 ∈ {0,1,2,6}, то оба хода (−3 и −7) ведут в остатки mod 10 ∈ {7,8,9,3} или {3,4,5,9}, то есть в не P-позиции; и наоборот при других остатках хотя бы один ход переводит в P-позицию.
Проверим R = 83:
- 83 mod 10 = 3, значит R = 83 находится в N-позиции (есть выигрышный ход для текущего игрока).
Какие ходы переводят в P-позицию?
- 83 − 3 = 80 → 80 mod 10 = 0 (P-позиция)
- 83 − 7 = 76 → 76 mod 10 = 6 (P-позиция)
Оба хода переводят к проигрышной позиции для соперника. Значит у Глеба есть беспроигрышная стратегия, и он может выбрать любой из этих ходов. Возьмём один из вариантов.
Ответ: Г3 (Глеб положил 3 пуговицы).
