Скрыть решение
Решение
Пусть
l -- произведение первых 21 простых чисел. Заметим, что
l --
наименьшее неразрешенное число. Нетрудно проверить, что 21-е простое число
-- это 71 < 2004. Значит, 2004! делится на
l.
Рассмотрим число m, полученное после первого хода первого игрока. Так как
число камней, взятое за один ход, не может делиться на l, число m не
делится на l. Рассмотрим остаток r от деления числа
m на l. Этот остаток меньше, чем l, поэтому он не может делиться больше
чем на 20 простых чисел. Второй игрок сможет взять r камней и снова
получить число, делящееся на l, и т. д.
Итак, если второй будет каждый раз брать остаток от деления числа камней на l,
то после каждого хода первого игрока число камней в кучке не делится на
l, а после хода второго игрока -- делится. Значит, первый игрок не сможет
взять последние камни, так что выиграет второй игрок.