РЕШУ ОЛИМП: задания, ответы, решения

Задания

Версия для печати и копирования в MS Word

Тип 21 № 10128 Добавить в вариант

Есть две кучки камней: 1703 камня в одной кучке и 2022 в другой. Саша и Оля играют в игру, делая ходы по очереди, начинает Саша. Пусть перед ходом игрока кучи содержат a и b камней, причем $a больше или равно b.$ Тогда своим ходом игроку разрешается взять из кучи с a камнями любое количество камней от 1 до b. Проигрывает тот, кто не может сделать ход. Кто выиграет при правильной игре?

Спрятать решение

Решение.

Предположим, что позиция $a больше b$ является проигрышной. Тогда все позиции $левая круглая скобка a минус k, b правая круглая скобка$ при $k=1, \ldots, b$ выигрышные. Но раз $a минус 1 больше или равно b$   — выигрышная, то из неё можно получить какую-то проигрышную, и ей может быть лишь позиция $левая круглая скобка a минус b минус 1, b правая круглая скобка .$ Такими процедурами можно получить проигрышные позиции:

$левая круглая скобка 2022,1703 правая круглая скобка arrow левая круглая скобка 1703,318 правая круглая скобка arrow левая круглая скобка 318,108 правая круглая скобка arrow левая круглая скобка 108,100 правая круглая скобка arrow левая круглая скобка 100,7 правая круглая скобка arrow левая круглая скобка 7,4 правая круглая скобка .$

Однако несложно убедиться, что эта позиция выигрышная. Следовательно, исходная позиция также выигрышная.

Ответ: выиграет Саша.

Санкт-Петербургская олимпиада школьников, 9 класс, 2 тур (заключительный), 2022 год

Классификатор: Разное. Игры и стратегии, Разное. Логические задачи

Спрятать решение · Помощь