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