Регион 2024

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

Теперь покажем, что такое дерево существует, для этого докажем лемму.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Есть 2 четвёрки чисел

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

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

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

В случае и н.у.о. группируем

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Построив снизу вверх так первые уровня дерева, мы в итоге получим четверку различных чисел

далее рассмотрим вершины со значениями(и соответствующими потомками) и и последнем шаге сложим уже эти два числа, получив в корне.

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

Первый способ — сумма одинаковых дробей Построим три других представления. Заметим, что среди чисел

не более одной степени двойки и не более двух простых чисел (потому что простые числа, большие трех, могут давать только остатки 1 и 5 от деления на 6), уберем такие числа из рассмотрения. Любое оставшееся число можно представить в виде где и нечетно. Тогда кратно обозначим частное от деления через Получаем, что

Возьмем дроби вида и дроби вида Поскольку то

Посчитаем сумму этих дробей:

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

откуда и противоречие.