ВСОШ 2024, 11 класс, задача 10

Решение. Приведём стратегию для Пети. Для этого представим в виде суммы дробей с числителями , разобьём их на пары не равных, сложим числа в каждой паре. Затем полученных результатов вновь разобьём на пары не равных, и сложим числа в каждой паре. Будем продолжать так делать, пока не получится одно число. Поскольку сумма всех дробей равна , то после шагов остаётся число .

Предположим, что описанный выше процесс возможен. В таком случае Петя разложит в сумму двух чисел, которые складывались на -м шаге. Вася выберет одно из слагаемых, которые представимо как сумма двух чисел, сложением которых данное число было получено на -м шаге и т. д. В конечном итоге останется одна из исходных дробей.

Для реализации указанного процесса нам потребуется следующее вспомогательное утверждение.

Лемма. Есть четвёрки чисел и . Тогда их можно сгруппировать по парам , чтобы числа в каждой паре были различны и суммы чисел в каждой паре были различны.

Доказательство. Разберём несколько случаев:

. , . Если , не умаляя общности и можно сгруппировать . В случае и н.у.о. группируем .

. , сводится к предыдущему, если мы перейдём к четвёркам чисел .

. Пары и разные, а также пары и разные. В таком случае покажем, как сгруппировать числа первых двух пар между собой, с числами в третьей и четвёртой паре поступим аналогично, явно получив две меньшие суммы чем в первой паре. Если или подходит , в противном случае можно сгруппировать и .

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

Таким образом, достаточно представить в виде суммы дробей вида четырьмя разными способами, каждый раз используя разные знаменатели, не превосходящие .

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

Проделаем так для трёх различных значений , остаётся убедиться, что полученные представления не содержат одинаковых дробей. Ясно, что с первым выбранным набором три новых не пересекаются, а также дроби вида могут быть лишь в одном наборе. Остаётся проверить, что дроби вида различны. Предположим обратное, . Поскольку и нечётны, получаем, что , и это число — общий делитель и . Тогда кратно , поэтому . Однако, , откуда и , противоречие.

Замечание. Неформально говоря, Петя с самого начала анализирует все возможные способы течения игры и для каждого варианта заранее продумывает ответ. Этому можно сопоставить двоичное дерево ранга , в листьях которого содержатся все возможные исходные (дроби вида с суммой и знаменателями, не превосходящими ), а в каждой из остальных вершин записано число, равное сумме чисел в вершинах-потомках. Задача эквивалентна тому, что существует такое дерево, причём у каждой вершины (кроме листьев), в вершинах-потомках записаны разные числа.