В средней клетке полоски 1×2005 стоит фишка. Два игрока по очереди сдвигают ее: сначала первый игрок передвигает фишку на одну клетку в любую сторону, затем второй передвигает ее на 2 клетки, 1-й – на 4 клетки, 2-й – на 8 и т.д. (k-й сдвиг происходит на 2^k-1 клеток). Тот, кто не может сделать очередной ход, проигрывает. Кто может выиграть независимо от игры соперника?

   Решение

Темы:    [ Теорема Эйлера ] [ Арифметическая прогрессия ] [ Простые числа и их свойства ] [ Разложение на множители ]

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

Прислать комментарий

Условие

В любой арифметической прогрессии  a,  a + d,  a + 2d,  ...,  a + nd,  ...,  составленной из натуральных чисел, есть бесконечно много членов, в разложении которых на простые множители входят в точности одни и те же простые числа. Докажите это.

Решение

  Заметим, что если первый член a и разность d прогрессии имеют общий наибольший делитель  q > 1,  то на q можно разделить все члены прогрессии. Достаточно решить задачу для этой новой прогрессии, поскольку если какие-то члены новой прогрессии имеют одни и те же простые множители, то и после умножения на q они будут иметь одни и те же простые множители. Итак, мы можем считать, что a и d взаимно просты. Поэтому существует такое k, что  a^k – 1  делится на d (см. задачи 73597 и 60779).
  Следовательно, при любом целом  m > 0   a^km+1 – a = a(a^k – 1)(a^k(m–1) + a^k(m–2) + ... + 1)  делится на d, то есть  a^km+1 – a = nd,  где n – целое число. Таким образом, для каждого натурального m число  a^km+1 = a + nd  входит в нашу прогрессию, то есть существует бесконечно много членов прогрессии, являющихся некоторой степенью её первого члена a. Ясно, что все эти члены имеют одни и те же простые множители.

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