Разделы 
Дополнительно
Задача по математике - 3415
2019-06-03 
Назовем натуральное число разрешенным, если оно имеет не более 20 различных простых делителей. В начальный момент имеется куча из $2004!$ (т. е. $1 \cdot 2 \cdot \cdots \cdot 2004$) камней. Два игрока по очереди забирают из кучи некоторое разрешенное количество камней (возможно, каждый раз новое). Побеждает тот, кто заберет последние камни. Кто выигрывает при правильной игре?
Решение:
Пусть $l$ - произведение первых 21 простых чисел. Заметим, что $l$ - наименьшее неразрешенное число. Нетрудно проверить, что 21-е простое число - это $71 < 2004$. Значит, $2004!$ делится на $l$.
Рассмотрим число $m$, полученное после первого хода первого игрока. Так как число камней, взятое за один ход, не может делиться на $l$, число $m$ не делится на $l$. Рассмотрим остаток $r$ от деления числа $m$ на $l$. Этот остаток меньше, чем $l$, поэтому он не может делиться больше чем на 20 простых чисел. Второй игрок сможет взять $r$ камней и снова получить число, делящееся на $l$, и т. д.
Итак, если второй будет каждый раз брать остаток от деления числа камней на $l$, то после каждого хода первого игрока число камней в кучке не делится на $l$, а после хода второго игрока - делится. Значит, первый игрок не сможет взять последние камни, так что выиграет второй игрок.
Ответ: При правильной игре выигрывает второй игрок.
Назовем натуральное число разрешенным, если оно имеет не более 20 различных простых делителей. В начальный момент имеется куча из $2004!$ (т. е. $1 \cdot 2 \cdot \cdots \cdot 2004$) камней. Два игрока по очереди забирают из кучи некоторое разрешенное количество камней (возможно, каждый раз новое). Побеждает тот, кто заберет последние камни. Кто выигрывает при правильной игре?
Решение:
Пусть $l$ - произведение первых 21 простых чисел. Заметим, что $l$ - наименьшее неразрешенное число. Нетрудно проверить, что 21-е простое число - это $71 < 2004$. Значит, $2004!$ делится на $l$.
Рассмотрим число $m$, полученное после первого хода первого игрока. Так как число камней, взятое за один ход, не может делиться на $l$, число $m$ не делится на $l$. Рассмотрим остаток $r$ от деления числа $m$ на $l$. Этот остаток меньше, чем $l$, поэтому он не может делиться больше чем на 20 простых чисел. Второй игрок сможет взять $r$ камней и снова получить число, делящееся на $l$, и т. д.
Итак, если второй будет каждый раз брать остаток от деления числа камней на $l$, то после каждого хода первого игрока число камней в кучке не делится на $l$, а после хода второго игрока - делится. Значит, первый игрок не сможет взять последние камни, так что выиграет второй игрок.
Ответ: При правильной игре выигрывает второй игрок.
