Задача 5. Красные и зелёные в десятках

Одного десятка не хватает

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

Но раскраска может быть «вредной». Пусть в каждом десятке красное — последнее число ($10, 20, 30, \ldots$), а зелёное — первое ($1, 11, 21, \ldots$). Тогда в каждом десятке красное больше зелёного, и сколько таких пар ни бери, сумма красных окажется больше. Значит, красные и зелёные числа нужно брать из разных десятков.

Какие десятки взять? Удобнее всего соседние: про их числа можно сказать точно, насколько одно больше другого. Это и сделаем.

Соседние десятки: разность от 1 до 19

Разобьём все $100000$ десятков на $50000$ блоков из двух соседних десятков: первый со вторым (числа $1$–$10$ и $11$–$20$), третий с четвёртым ($21$–$30$ и $31$–$40$) и так далее. Разные блоки не имеют общих чисел.

Возьмём один блок. Число левого десятка запишем как $10a+x$, число правого — как $10a+10+y$, где $x$ и $y$ — целые числа от $1$ до $10$. Их разность

Самая маленькая она при $y=1$, $x=10$: получается $1$. Самая большая — при $y=10$, $x=1$: получается $19$. Итак, любое число правого десятка больше любого числа левого хотя бы на $1$ и не больше чем на $19$ (на рисунке: от $31-30=1$ до $40-21=19$).

В каждом блоке посмотрим на две разности:

• $u$ = зелёное правого десятка − красное левого;
• $w$ = красное правого десятка − зелёное левого.

Обе — целые числа от $1$ до $19$. В разность $u$ входит пара чисел «красное левого, зелёное правого», в разность $w$ — пара «зелёное левого, красное правого»; вместе это четыре разных числа блока.

Принцип Дирихле: одинаковые разности

Блоков $50000$, а разность $u$ может быть только одним из $19$ чисел $1, 2, \ldots, 19$. Если бы каждое значение встречалось не больше чем в $18$ блоках, всего блоков было бы не больше $19 \cdot 18 = 342$. А их $50000$. Значит, какое-то значение $u$ — назовём его $p$ — встречается хотя бы в $19$ блоках.

Точно так же какое-то значение $w$ — назовём его $q$ — встречается хотя бы в $19$ блоках. Числа $p$ и $q$ лежат от $1$ до $19$; они могут совпасть, а могут и различаться, и блоки с $u=p$ и с $w=q$ тоже могут совпадать — это не помешает.

Уравновешиваем: q раз по p и p раз по q

Пары с разностью $u$ дают перевес зелёным, пары с разностью $w$ — красным. Одинаковые перевесы $p$, взятые несколько раз, надо сравнять с одинаковыми перевесами $q$, взятыми несколько раз. Проще всего сделать оба перевеса равными $p \cdot q$:

• возьмём $q$ блоков, где $u = p$ (их хватает: таких блоков хотя бы $19$, а $q \le 19$). Из каждого — красное число левого десятка и зелёное правого. В каждой такой паре зелёное больше красного на $p$, всего зелёные этих пар больше красных на $q \cdot p$;
• возьмём $p$ блоков, где $w = q$ (их тоже хватает). Из каждого — зелёное число левого десятка и красное правого. В каждой паре красное больше зелёного на $q$, всего красные больше на $p \cdot q$.

Перевесы одинаковые: $q \cdot p = p \cdot q$. Поэтому сумма всех выбранных красных чисел равна сумме всех выбранных зелёных. На рисунке ниже — пример с $p = 2$ и $q = 3$: три пары, где зелёное больше на $2$, и две пары, где красное больше на $3$; перевесы $3 \cdot 2 = 2 \cdot 3 = 6$ взаимно гасятся.

Проверяем все требования

• Поровну. В каждой паре одно красное и одно зелёное число, пар $q + p$. Значит, красных чисел выбрано $p + q$ и зелёных столько же.
• Не больше $50$. Так как $p \le 19$ и $q \le 19$, получаем $p + q \le 38$, а это меньше $50$.
• Ни одно число не взято дважды. Разные блоки не имеют общих чисел. Если один блок попал в обе группы, из него взяты красное и зелёное левого десятка и красное и зелёное правого — четыре разных числа.
• Суммы равны — это шаг 4.

Такой выбор есть при любой раскраске, что и требовалось доказать. Запас в условии большой: рассуждение работает уже для первых $686$ десятков — в них $343$ блока, а $343 > 19 \cdot 18$.