Условие
Выписаны в ряд числа от 1 до 2002. Играют двое, делая ходы поочередно.
За один ход разрешается вычеркнуть любое из записанных чисел вместе
со всеми его делителями. Выигрывает тот, кто зачеркнёт последнее число.
Докажите, что у первого игрока есть способ играть так,
чтобы всегда выигрывать.
Подсказка
Предположите, что выигрышную стратегию имеет второй игрок;
покажите, что первый игрок может
воспользоваться этой стратегией, чтобы выиграть.
Тем самым будет получено противоречие.
Решение
По правилам игры ничьих не бывает, поэтому либо первый игрок,
либо второй имеет выигрышную стратегию. Первый игрок может
"передать ход" второму, вычеркнув первым ходом 1.
Действительно, пусть второй вычёркивает число x и все его делители.
После этого хода вычеркнуты те числа, какие были бы вычеркнуты,
если бы первый игрок первым своим ходом вычеркнул x
(и все его делители). Поэтому у второго игрока не может
быть выигрышной стратегии: первый игрок, "передав ход",
может играть, следуя любой стратегии второго игрока.
Значит, выигрышная стратегия есть у первого игрока.
Источники и прецеденты использования
