Олимпиада имени Леонарда Эйлера 2023-2024 учебный год, I тур заключительного этапа

Дано натуральное число $k$. Из натуральных чисел, не превосходящих $12k^3$, выбраны $6k+20$ чисел. Докажите, что из них можно выбрать две непересекающиеся шестерки чисел с равными суммами. ( И. Богданов )

Комментарий/решение

Предположим противное.Будем выбирать пары пар чисел с равными суммами и выкидывать их из множества.Если нашлись три таких пары , из них собираются две шестёрки.Значит , выкинуто не более $8$ чисел.

В оставшемся множестве нет пар с равными суммами. Значит, если две тройки имеют равные суммы , они не пересекаются. Если найдутся две тройки с равными суммами, выкинем их.Два раза это повторить нельзя, иначе нашлись требуемые шестёрки.Значит,всего выкинуто не более, чем $8+6=14$ чисел.

В оставшемся множестве суммы всех троек различны.Однако все эти суммы меньше $3*12k^3=36k^3$, а троек хотя бы $(6k+6)(6k+5)(6k+4)/6>36k^3$.Противоречие.

Предположим, что выбрать две непересекающиеся шестерки с равными суммами нельзя.Если в наборе есть три пары чисел с равными суммами (a1+b1=a2+b2, a3+b3=a4+b4, a5+b5=a6+b6), то, объединив их левые и правые части, мы получим две непересекающиеся шестерки. Значит, таких пар не более двух. Удалим эти числа из набора (максимум 2×4=8 чисел).

В оставшемся множестве суммы всех пар различны. Если найдутся две тройки с равными суммами, они обязаны не пересекаться (иначе, удалив общий элемент, мы получили бы две пары с равной суммой, которых уже нет).Значит,две тройки с равной суммой это уже искомые две шестерки. Чтобы противоречие сохранялось, в остатке все суммы троек должны быть различны. На это право мы можем потратить еще максимум одну пару троек (выкинув 3×2=6 чисел).==>Всего удалено не более 8 + 6 = 14 чисел. Оставшееся количество чисел:

n=>(6k+20) - 14 = 6k+6.

Количество троек из всех этих чисел:

(6k+6)(6k+5)(6k+4)/6=(k+1)(6k+5)(6k+4)

Количество троек из этих чисел:

​Количество возможных сумм трех чисел: S<3×12k^3 = 36k^3

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

​Противоречие.