Всесиб 2022, 9 класс, задача 5

Ответ. При , для всех натуральных .

Решение. ) Пусть сначала для некоторого натурального . Выигрышной стратегией для Пети является следующая: если после очередного хода Васи фишка оказалась на позиции с номером , то Петя называет число . После этого Вася передвинет фишку либо на позицию номер , либо на позицию номер по модулю . В любом случае максимальная степень двойки, делящая номер позиции, на которой фишка окажется после очередного хода Васи, увеличивается минимум на . Следовательно, после не более чем ходов номер позиции фишки станет делиться на , что возможно только для позиции с номером , и Петя выиграет.

) Пусть теперь , , где - максимальный нечётный делитель . Заметим, что позиции, номера которых делятся на , плохие для Васи: если он поставит сначала фишку на одну из них, то Петя, применяя стратегию, аналогичную описанной в п. ), называя каждый раз число , выиграет. Поэтому Вася должен сначала поставить фишку на любую позицию с номером , не делящимся на . Пусть очередным ходом Петя назвал любое натуральное число из диапазона от до . Одно из чисел и не делится на : в противном случае на делится их сумма, равная , а значит, на делится , что противоречит его выбору. Следовательно, на каждом ходу Вася может ставить фишку на позицию, номер которой не делится на , и она никогда не окажется на позиции с номером . Таким образом, для , не являющихся степенями двойки, Петя выиграть не сможет.