Задача 4. Две шестёрки из блоков

Блок: две группы с равной суммой

Назовём блоком две группы чисел одинакового размера, у которых нет общих чисел и равны суммы. Например, пары $\{20, 41\}$ и $\{14, 47\}$ — блок-пара: $20+41 = 14+47 = 61$. Две тройки с равной суммой и без общих чисел — блок-тройка.

Почему нельзя просто сосчитать шестёрки? Шестёрок из $6k+20$ чисел очень много, а сумма шестёрки не превосходит $6 \cdot 12k^3 = 72k^3$, так что две *разные* шестёрки с равной суммой найдутся. Но у них могут быть общие числа, а нам нужны непересекающиеся. Общие числа можно вычеркнуть из обеих групп — суммы уменьшатся на одно и то же и останутся равными, — только группы станут меньше шести. Поэтому будем собирать шестёрки из частей.

Обрезка. Пусть две *разные* тройки имеют равную сумму. Вычеркнем из обеих их общие числа: суммы останутся равными, а общих чисел больше нет (рисунок ниже). Какого размера остались группы? Двух общих чисел быть не могло: тогда третьи числа троек были бы равны, и тройки совпали бы. Значит, общих чисел $0$ или $1$, и остались две группы по $3$ или по $2$ числа. Итак, две разные тройки с равной суммой всегда дают блок-пару или блок-тройку.

Из блоков складываются шестёрки

Пусть отложены три блока-пары и все $12$ чисел в них различны (каждый блок брали из чисел, не попавших в прежние). Соберём левые пары в одну шестёрку, правые — в другую (рисунок ниже). Общих чисел у шестёрок нет, а суммы равны: каждая из них — сумма трёх одинаковых слагаемых, по одному от каждого блока. Точно так же из двух блоков-троек получаются две шестёрки: $3+3 = 6$.

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

Вынимаем блоки, пока получается

Смотрим только на числа, ещё не попавшие в блоки. Если среди них есть две разные тройки с равной суммой, по шагу 1 получаем блок-пару или блок-тройку и откладываем его. Как только отложено три блока-пары или два блока-тройки, две шестёрки собраны (шаг 2).

Предположим, что до этого не дошло: в какой-то момент среди оставшихся чисел любые две тройки имеют разные суммы, а комплекта ещё нет. Сколько чисел к этому моменту вынуто? Блоков-пар отложено не больше двух (иначе их уже три), блоков-троек — не больше одного (иначе уже два). Блок-пара — это $4$ числа, блок-тройка — $6$. Всего вынуто не больше $2 \cdot 4 + 6 = 14$ чисел, и осталось хотя бы $6k+20-14 = 6k+6$ чисел (рисунок ниже).

Осталось показать, что среди $6k+6$ чисел две разные тройки с равной суммой есть обязательно. Тогда предположение неверно: процесс не может остановиться, пока комплект не собран. А остановиться он когда-нибудь должен — чисел конечное количество, и каждый блок забирает хотя бы четыре.

Троек больше, чем значений суммы

Сколько троек можно составить из $n = 6k+6$ чисел? Первое число выбираем $n$ способами, второе — $n-1$, третье — $n-2$; каждую тройку мы так насчитали $3 \cdot 2 \cdot 1 = 6$ раз (во всех порядках), поэтому троек

Так как $6k+6 = 6(k+1)$, после сокращения на $6$ получаем $(k+1)(6k+5)(6k+4)$ троек. Множители больше, чем $k$, $6k$ и $6k$, поэтому троек больше, чем $k \cdot 6k \cdot 6k = 36k^3$.

Сколько разных значений может принимать сумма тройки? Числа различны и не превосходят $12k^3$, поэтому сумма не меньше $1+2+3 = 6$ и не больше $12k^3 + (12k^3-1) + (12k^3-2) = 36k^3-3$. Целых чисел от $6$ до $36k^3-3$ ровно $36k^3-8$ — меньше, чем $36k^3$.

Представим ящики, подписанные значениями суммы, и положим каждую тройку в ящик с её суммой (рисунок ниже). Троек больше $36k^3$, а ящиков меньше $36k^3$ — в каком-то ящике лежат две тройки. Это две разные тройки с равной суммой, а по предположению шага 3 их нет. Противоречие.

Значит, процесс из шага 3 останавливается только сборкой комплекта: три блока-пары или два блока-тройки. Из них по шагу 2 складываются две непересекающиеся шестёрки с равными суммами. Что и требовалось доказать.