Олимпиадная задача: Куча камней и разрешённые числа с не более 20 простых делителей
Задача
Назовём натуральное число разрешённым, если оно имеет не более 20 различных простых делителей. В начальный момент имеется куча из 2004! камней. Два игрока по очереди забирают из кучи некоторое разрешённое количество камней (возможно, каждый раз новое). Побеждает тот, кто заберёт последние камни. Кто выигрывает при правильной игре?
Решение
Пусть l – произведение первых 21 простых чисел. Заметим, что l – наименьшее неразрешенное число. Нетрудно проверить, что 21-е простое число – это 71 < 2004. Значит, 2004! делится на l.
Рассмотрим число m, полученное после первого хода первого игрока. Так как число камней, взятое за один ход, не может делиться на l, число m не делится на l. Рассмотрим остаток r от деления числа m на l. Этот остаток меньше l, поэтому он не может делиться больше чем на 20 простых чисел. Второй игрок сможет взять r камней и снова получить число, кратное l, и т. д.
Итак, если второй будет каждый раз брать остаток от деления числа камней на l, то после каждого хода первого игрока число камней в кучке не делится на l, а после хода второго игрока – делится. Значит, первый игрок не сможет взять последние камни, так что выиграет второй игрок.
Ответ
Второй игрок.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь