Высшая проба 2022, 9-10 классы, задача 6

Решение. Ответ: .

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

Покажем, что при любом количестве чисел верна оценка

Доказывать это будем, как ни странно, индукцией по .

База при проверяется непосредственно.

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

Лемма. Определим операцию преобразования набора: заменим в наборе два числа разных знаков и (пусть ) на одно число . Тогда если полученный набор допускает расстановку для некоторого числа и выполняется , то исходный допускал расстановку для .

Доказательство. Расставим по кругу преобразованный набор, и воспользуемся переформулированным условием, начиная от позиции, на которой стоит добавленное число . Тогда по переформулированному условию все суммы дуг, начинающихся в этой позиции (включая сумму, равную нулю) покрываются отрезком длины . Тогда в этот отрезок попало и одно из чисел и , поскольку они не могут лежать с разных сторон от отрезка - расстояние между ними равно , то есть не превосходит длины отрезка. Если попало число - заменим на числа , (в таком порядке), у полученной расстановки те же суммы, что у исходной, и еще сумма , лежащая где нужно. Аналогично заменим на числа , , если попало .

Теперь докажем индукционный переход. Рассмотрим набор из чисел, не больших по модулю, с суммой . Рассмотрим наименьшие по модулю положительное и отрицательное число. Если их сумма модулей не больше

то можно воспользоваться Леммой. Пусть их сумма больше.

Тогда это возможно при четном только если положительных и отрицательных поровну. Тогда разобьем их на пары, как при доказательстве Леммы. Тогда сумма чисел в каждой паре (то есть "новое" число) по модулю не превосходит . Наша задача расположить их по кругу так, чтобы для некоторой позиции сумма по любой дуге с левым концом в лежала бы на отрезке , это очевидно можно сделать. Теперь вспомним, что каждое новое число - это на самом деле два старых, и расположим эти старые в порядке положительное-отрицательное. Добавились суммы, получающиеся из старых добавлением одного из первых чисел пары, то есть не более чем единицы. Поскольку все старые суммы лежали на отрезке длины , теперь все суммы лежат на отрезке длины , что и требовалось.

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

Каждое положительное число, кроме самого маленького, объединим в пару с отрицательным. Получили набор из чисел (оставшееся положительное и сумм в парах, суммы в парах по модулю не больше ), оставшееся положительное обозначим .

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

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