Имеется натуральное число N. Алиса и Маруся по очереди выписывают на доску различные натуральные числа по следующему правилу: каждое выписанное число должно быть делителем N и при этом быть взаимно просто со всеми числами, уже выписанными на доску. Алиса ходит первой. Проигрывает тот, кто не может сделать ход. Сколько существует натуральных чисел N, не больших 100, таких, что Маруся имеет возможность выиграть независимо от действий Алисы?
Пусть у
-
Число
— делитель и взаимно просто с любым числом, поэтому его можно выписать один раз в любой момент. Это отдельный ход, который не затрагивает простые числа. -
Любое число, большее
, использует непустой набор простых делителей . Следующие числа не должны содержать эти простые. Значит, за один ход можно «забрать» любое непустое подмножество оставшихся простых: достаточно выписать их произведение, оно делит . Показатели степеней не важны. -
Игра равносильна игре Ним с двумя кучами: в одной
камней (простые делители), в другой камень (число ). За ход берут любое положительное число камней из одной кучи, проигрывает тот, кто не может ходить. -
Выигрывает второй игрок (Маруся) тогда и только тогда, когда
, то есть .
- При
: Алиса берёт либо простое, либо , Маруся берёт оставшееся, и Алиса не может ходить. - При
( ) Алиса пишет и выигрывает. - При
Алиса первым ходом забирает простых (произведением), оставляя Марусе позицию с и , которую выигрывает ходящий вторым, то есть Алиса.
- Значит, нужны
, у которых ровно один простой делитель, то есть степени простых , :
- простых чисел до
: ; - степени
(от ): — чисел; - степени
: — числа; и — числа.
Итого:
Ход «выписать
