Имеется натуральное число N. Алиса… (вероятность и статистика)

Игра с делителями числа N

Имеется натуральное число $N$ . Алиса и Маруся по очереди выписывают на доску различные натуральные числа по следующему правилу: каждое выписанное число должно быть делителем $N$ и при этом быть взаимно просто со всеми числами, уже выписанными на доску. Алиса ходит первой. Проигрывает тот, кто не может сделать ход. Сколько существует натуральных чисел $N$ , не больших $90$ , таких, что Маруся имеет возможность выиграть независимо от действий Алисы?

Решение

Пусть у ровно различных простых делителей. Ход — это либо число (его можно записать один раз), либо делитель, составленный из ещё «неиспользованных» простых чисел. Показатели степеней не важны: после записи числа его простые делители «заняты». За один ход можно занять любое непустое множество свободных простых.

Разберём позиции, где ходит игрок. Пусть — осталось свободных простых и число ещё не записано, а — то же, но уже записана.

при — выигрыш ходящего: он берёт сразу все оставшиеся простые (например, число, содержащее все их).
— проигрыш ходящего.
— выигрыш: ходящий пишет .
— проигрыш. Если ходящий пишет , то соперник получает и выигрывает. Если ходящий занимает простое, то соперник пишет и выигрывает.
при — выигрыш: ходящий занимает простых и оставляет сопернику проигрышную позицию .

Алиса начинает в позиции .

(): Алиса пишет и выигрывает.
: выигрывает Алиса.
: проигрывает Алиса, то есть выигрывает Маруся.

Значит, нужны , являющиеся степенью простого числа: , .

Считаем:

простые числа до : , , , , , , , , , , , , , , , , , , , , , , , — их ;
степени двойки (от ): , , , , — чисел;
степени тройки (от ): , , — числа;
степени пятёрки: — число;
степени семёрки: — число.

💡 Почему так

Выигрыш зависит только от количества различных простых делителей . Если оно равно , то Маруся выигрывает, отвечая на ход Алисы так: после любого простого она пишет , а после — степень простого.

Ответ

✓ dzmen.ru

Помогло?

Имеется натуральное число N. Алиса и Маруся по очереди выписывают на доску…