Задача 32890

Темы:    [ Выигрышные и проигрышные позиции ] [ Простые числа и их свойства ]

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

Условие

Автор: Хачатурян А.В.

На доске записано целое положительное число N. Два игрока ходят по очереди. За ход разрешается либо заменить число на доске на один из его делителей (отличных от единицы и самого числа), либо уменьшить число на единицу (если при этом число остается положительным). Тот, кто не может сделать ход, проигрывает. При каких N первый игрок может выиграть, как бы ни играл соперник?

Решение

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

  Пользуясь этим утверждением, можно, рассматривая натуральные числа последовательно, выяснить про любое конкретное число, является оно выигрышным или проигрышным: число 1 – проигрышное, число 2 – выигрышное, число 3 – проигрышное (так как единственный ход ведет из него в выигрышное число 2), число 4 – выигрышное (так как из него есть ход в проигрышное число 3) и так далее:

  Заметим, что число 16 является проигрышным, а, следовательно, простое число 17 является выигрышным. Число 33 – выигрышное: из него можно пойти в проигрышное число 3. Поэтому число 34 является хоть и составным, но проигрышным (все три хода из него – в 2, в 17 и в 33 – ведут в выигрышные числа).

  Докажем, что 2 и 17 – единственные выигрышные простые числа. Предположим, что это не так, и рассмотрим следующее выигрышное простое число p. В таком случае  p – 1  – проигрышное чётное число, поэтому среди делителей числа  p – 1  не может быть проигрышных простых чисел, то есть  p – 1 = 2ⁿ·17^k  (n ≥ 1).  Но тогда от него можно перейти либо к числу 34, либо к числу 16 и выиграть.
  Если составное число N имеет простой делитель p, отличный от 2 и 17, то из него есть ход в проигрышное число p, то есть число N является выигрышным. Остались числа вида  N = 2ⁿ·17^k.
  Выше показано, что 2, 4, 8 – выигрышные, а 16 – проигрышное, поэтому числа 2ⁿ  (n > 4)  – выигрышные: от них можно перейти к 16.
  Число 34 – проигрышное; поэтому числа вида  N = 2ⁿ·17^k  (n, k > 1)  – выигрышные: от них можно перейти к 34.
  Число  17² = 289  – проигрышное; поэтому числа 17^k  (k > 2)  – выигрышные, от них можно перейти к 17².

Ответ

При  N = 2,  N = 17,  а также при всех составных N, кроме  N = 16, 34 и 289.

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

олимпиада
Название	Московская математическая олимпиада
год
Год	2013
Номер	76
класс
Класс	8
задача
Номер	6