Задача 105179

Темы:    [ Теория игр (прочее) ] [ Деление с остатком ] [ Произведения и факториалы ] [ Основная теорема арифметики. Разложение на простые сомножители ]

Сложность: 4 Классы: 8,9,10

Условие

Назовём натуральное число разрешённым, если оно имеет не более 20 различных простых делителей. В начальный момент имеется куча из 2004! камней. Два игрока по очереди забирают из кучи некоторое разрешённое количество камней (возможно, каждый раз новое). Побеждает тот, кто заберёт последние камни. Кто выигрывает при правильной игре?

Решение

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

Ответ

Второй игрок.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	67
Год	2004
вариант
Класс	10
задача
Номер	4
олимпиада
Название	Московская математическая олимпиада
год
Номер	67
Год	2004
вариант
Класс	9
задача
Номер	5