Олимпиадная задача по теории чисел и алгоритмам для 7-9 классов — игра на делимость
Задача
На доске записаны числа 1, 2, 3, ..., 1000. Двое по очереди стирают по одному числу. Игра заканчивается, когда на доске остаются два числа. Если их сумма делится на 3, то побеждает тот, кто делал первый ход, если нет – то его партнер. Кто из них выиграет при правильной игре?
Решение
Укажем, как партнер начинающего может гарантировать себе выигрыш.
В начале партии он должен стирать числа, кратные 3, до тех пор, пока таковых не останется. Поскольку количество чисел, не превосходящих 1000 и кратных 3, равно 333, то партнеру начинающего понадобится не более 333 ходов для того, чтобы ни одно из оставшихся на доске чисел не делилось на 3 (некоторые из чисел, кратных 3, могут быть стёрты и начинающим). После этого партнер начинающего делает свои ходы произвольно вплоть до того момента, когда на доске останутся три числа. Каждое из них будет давать остаток 1 или 2 при делении на 3, поэтому среди трёх остающихся на доске чисел обязательно найдутся два, дающие одинаковые остатки. Именно их должен оставить партнер начинающего (сумма не будет делиться на 3).
Ответ
Партнер.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь