Задача 10. Двенадцать сосудов

Переворачиваем вопрос

Утверждение «найдутся два сосуда, которые отличаются не более чем на $\alpha$ л» верно для данного $\alpha$, если такая пара есть при любой расстановке воды (по литру в каждом ряду). И оно неверно, если найдётся хотя бы одна расстановка, где любые два сосуда отличаются больше чем на $\alpha$.

Поэтому спросим по-другому: насколько сильно можно «раздвинуть» количества воды? Для каждой расстановки посмотрим на наименьшую разницу между двумя сосудами на столе — любыми, не обязательно из одного ряда. Обозначим её $d$.

Если удастся доказать, что всегда $d\le D$, и предъявить расстановку, где $d$ ровно равно $D$, то задача решена:

• при $\alpha\ge D$ в любой расстановке два самых близких сосуда отличаются на $d\le D\le\alpha$;

• при $\alpha<D$ в примере любые два сосуда отличаются хотя бы на $D$, то есть больше чем на $\alpha$.

План: найти число $D$, доказать оценку (шаги 2–3) и построить пример (шаг 4).

Лесенка и слишком слабая оценка

Возьмём любую расстановку и её наименьшую разницу $d$. Выстроим сосуды по возрастанию количества воды и пронумеруем: номер $0$ — сосуд, где воды меньше всего, номер $11$ — где больше всего (если количества совпадают, порядок между ними любой; тогда $d=0$).

Каждый следующий сосуд в этой цепочке (не путать с рядами на столе!) не меньше предыдущего плюс $d$: ведь разница любых двух сосудов не меньше $d$. В сосуде номер $0$ воды не меньше нуля. Значит, в сосуде номер $1$ не меньше $d$, в сосуде номер $2$ не меньше $2d$ и вообще в сосуде номер $k$ не меньше $k\cdot d$ л — как на лесенке со ступеньками высотой хотя бы $d$.

Первая мысль — сложить всё. Всего воды $4$ л (четыре ряда по литру), а по лесенке не меньше

Получаем $66d\le 4$, то есть $d\le\frac{2}{33}$. Но так много не бывает: равенство требует, чтобы количества были ровно $0,\ \frac{2}{33},\ \frac{4}{33},\ \ldots,\ \frac{22}{33}$ л. Все числители чётные, а в ряду нужна сумма $\frac{33}{33}$ с нечётным числителем — три чётных числа так не сложить. Общая сумма ничего не знает про ряды; используем их.

Оценка через ряды

Номера $0, 1, \ldots, 11$ разошлись по четырём рядам, по три в каждом. Их сумма

Если бы в каждом ряду сумма номеров была не больше $16$, то всего вышло бы не больше $4\cdot16=64$, а это меньше $66$. Значит, есть ряд, в котором сумма номеров $i+j+k$ не меньше $17$ (это принцип Дирихле в форме «среднее»: $66:4=16{,}5$, а сумма — целое число).

В этом ряду по лесенке воды не меньше

Но в каждом ряду ровно $1$ л. Значит, $17d\le1$, то есть $d\le\frac{1}{17}$.

Итак, в любой расстановке найдутся два сосуда, которые отличаются не больше чем на $\frac{1}{17}$ л. Поэтому при каждом $\alpha\ge\frac{1}{17}$ утверждение верно.

Пример: разница ровно 1/17

Теперь покажем, что $\frac{1}{17}$ улучшить нельзя. Удобно мерить воду в семнадцатых долях литра: тогда в каждом ряду должно быть $17$ долей, а если все количества — разные целые числа долей, любые два отличаются хотя бы на $1$ долю, то есть на $\frac{1}{17}$ л.

Нужно $12$ разных целых чисел от $0$, всего $4\cdot17=68$ долей. Самые маленькие разные числа $0, 1, \ldots, 11$ дают $66$ — не хватает двух. Добавим их сверху: вместо $10$ и $11$ возьмём $11$ и $12$. Получились числа от $0$ до $12$ без $10$. Раскладываем их по рядам с суммой $17$, ставя к большим числам маленькие:

То есть в первом ряду $\frac{12}{17}$, $\frac{5}{17}$ и $0$ л, во втором — $\frac{11}{17}$, $\frac{4}{17}$ и $\frac{2}{17}$ л, в третьем — $\frac{9}{17}$, $\frac{7}{17}$ и $\frac{1}{17}$ л, в четвёртом — $\frac{8}{17}$, $\frac{6}{17}$ и $\frac{3}{17}$ л.

Проверка: в каждом ряду ровно $\frac{17}{17}=1$ л; все двенадцать чисел долей разные, поэтому любые два сосуда отличаются хотя бы на $\frac{1}{17}$ л. Значит, при $\alpha<\frac{1}{17}$ в этой расстановке нет двух сосудов, отличающихся не более чем на $\alpha$ л, и утверждать этого нельзя (при отрицательных $\alpha$ — тем более).

Собираем ответ

Шаг 3: при любой расстановке наименьшая разница не больше $\frac{1}{17}$ л, поэтому все $\alpha\ge\frac{1}{17}$ подходят. Шаг 4: есть расстановка, где наименьшая разница ровно $\frac{1}{17}$ л, поэтому никакое $\alpha<\frac{1}{17}$ не подходит.

Заметь, что в примере оценка шага 3 обращается в равенство: номера сосудов по возрастанию — $0,1,\ldots,9$ у чисел $0$–$9$, номер $10$ у числа $11$ и номер $11$ у числа $12$; в ряду $9+7+1$ сумма номеров ровно $17$, и воды там ровно $17\cdot\frac{1}{17}=1$ л.