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

Пусть в разложении N на простые множители содержится k различных простых чисел. Число, делящее N, задаёт набор простых делителей; два числа взаимно просты, когда их наборы не пересекаются. Поэтому каждый ход, кроме записи 1, занимает хотя бы один из k простых делителей, а оставшиеся простые делители можно записывать по одному.

1. Запись 1 не мешает другим ходам, поскольку 1 взаимно просто с любым числом. Её можно рассматривать как дополнительный ход, который можно сделать один раз.
2. Без учёта 1 игра с k простыми делителями имеет выигрышную позицию для первого игрока при нечётном k: после любого хода остаётся меньшее число доступных простых делителей, а при оптимальной игре победа определяется чётностью k.
3. Дополнительный независимый ход 1 меняет победителя. Значит, Маруся выигрывает при нечётном k.
4. До 100 чисел с ровно одним различным простым делителем — 36: это простые степени. С тремя различными простыми делителями таких чисел 5: 30, 42, 66, 70, 78. С пятью или более различными простыми делителями число не меньше 2·3·5·7·11 = 231.

Итого: 36 + 5 = 41.

Ответ: 41.