МОШ 2026, 11 класс, задача 3
Петя и Вася играют в следующую игру. Сначала они пишут по единице, каждый на своей доске. Далее они по очереди (начинает Петя) заменяют каждый своё число, умножая его либо на , либо на , причём после каждого хода числа, записанные на досках, должны быть различными. Пусть — количество натуральных делителей числа Пети после его -го хода, а — количество натуральных делителей числа Васи после его -го хода. По итогам игры Петя получает фантиков. При каком наибольшем натуральном Петя может действовать так, чтобы гарантированно получить не менее фантиков вне зависимости от действий Васи?
(И. Михайлов)
Ответ
Решение. Стратегия Пети. Покажем, как Пете действовать так, чтобы по итогам игры получить фантиков. Пусть Петя на -м ходу заменяет своё число на (это возможно, поскольку для каждого натурального числа после ходов Пети и -го хода Васи в разложении числа Пети на простые множители участвует ровно на один сомножитель больше, чем в разложении числа Васи, поэтому их числа после хода Пети совпасть не могут). Индукцией по докажем, что тогда после ходов Васи на его доске написано число .
База: при Васе запрещено писать число , поэтому он запишет число .
Переход: если после ходов на досках Пети и Васи записаны числа и соответственно, то после -го хода Пети на его доске будет . Тогда Вася не сможет умножить своё число на , поскольку в таком случае числа на досках оказались бы равными, то есть запишет число , что и требовалось доказать.
В соответствии с доказанным утверждением после окончания игры на досках Пети и Васи будут записаны числа и соответственно. Значит, Петя получит фантиков.
Стратегия Васи. Покажем теперь, как Васе действовать так, чтобы по итогам игры Петя получил не больше фантиков. Без ограничения общности предположим, что первым ходом Петя записал на своей доске число . Тогда пусть Вася своим первым ходом запишет число , а далее на -м ходу (для каждого ) умножает своё число на то же число ( либо ), на которое умножает своё число Петя на его -м ходу (тем самым после каждого хода Васи отношение его числа к числу Пети будет оставаться равным ).
Тогда для каждого если после ходов Пети на его доске записано число , где , то после ходов Васи на его доске записано число , отличное от .
Пусть после ходов Пети на его доске записано число для некоторых целых чисел и с суммой . Тогда в соответствии с предыдущим замечанием после ходов Васи на его доске будет записано число . Значит, по итогам игры Петя получит не более
фантиков, где последнее неравенство выполнено, поскольку .
Ответ: .