Рассматриваются всевозможные наборы действительных чисел
Докажем что Рассмотрим набор из 1010 чисел −1, и 1011 чисел Ясно что при любой расстановке по кругу два положительных окажутся рядом, значит, найдется дуга с суммой
Покажем, что при любом количестве чисел n верна оценка
Доказывать это будем, как ни странно, индукцией по n. База при проверяется непосредственно. Так же заметим, что для расстановки чисел по кругу условие, что сумма на любой дуге по модулю не больше C, эквивалентно условию, что для произвольной позиции на круге множество сумм по всем дугам, имеющим левый конец в этой позиции, умещается на отрезке длины C. Этой переформулировкой мы и будем пользоваться в дальнейшем.
Лемма. Определим операцию преобразования набора: заменим в наборе два числа разных знаков a и −b (пусть на одно число a − b. Тогда если полученный набор допускает расстановку для некоторого числа C и выполняется то исходный допускал расстановку для C.
Доказательство. Расставим по кругу преобразованный набор, и воспользуемся переформулированным условием, начиная от позиции, на которой стоит добавленное число a − b. Тогда по переформулированному условию все суммы дуг, начинающихся в этой позиции (включая сумму, равную нулю) покрываются отрезком длины C. Тогда в этот отрезок попало и одно из чисел a и −b, поскольку они не могут лежать с разных сторон от отрезка — расстоянии между ними равно a + b, то есть не превосходит длинны отрезка. Если попало число a — заменим a − b на числа a, −b (в таком порядке), у полученной расстановки те же суммы, что у исходной, и еще сумма a, лежащая где нужно. Аналогично заменим на числа −b, a если попало −b.
Теперь докажем индукционный переход. Рассмотрим набор из n чисел не больших 1 по модулю с суммой 0. Рассмотрим наименьшие по модулю положительное и отрицательное число. Если их сумма модулей не больше
то можно воспользоваться Леммой. Пусть их сумма больше.
Тогда это возможно при четном n только если положительных и отрицательных поровну. Тогда разобьем их на пары, как при доказательстве Леммы. Тогда сумма чисел в каждой паре (то есть «новое» число) по модулю не превосходит
Наша задача расположить их по кругу так, чтобы для некоторой позиции A сумма по любой дуге с левым концом в A лежала бы на отрезке
это очевидно можно сделать. Теперь вспомним, что каждое новое число это на самом деле два старых, и расположим эти старые в порядке положительное отрицательное. Добавились суммы, получающиеся из старых добавлением одного из первых чисел пары, то есть не более чем единицы. Поскольку все старые суммы лежали на отрезке длины
теперь все суммы лежат на отрезке длины
что и требовалось. Пусть тогда сумма модулей наименьших по модулю положительного и отрицательного чисел может быть слишком большой только если количество положительных и отрицательных чисел отличается на единицу. Без ограничения общности пусть положительных k. Каждое положительное число, кроме самого маленького, объединим в пару с отрицательным. Получили набор из k чисел (оставшееся положительное и k − 1 сумм в парах, суммы в парах по модулю не больше оставшееся положительное обозначим x, естественно
Мы хотим эти числа расставить по кругу с началом отсчета так, чтобы последним стояло x, а все суммы кроме суммы k − 1 пары лежали на отрезке Для этого сначала выберем пару, которая встанет
Теперь перейдем от расстановки пар к расстановки исходных чисел, поставив числа в каждой паре в порядке отрицательное-положительное. Поскольку до этого все суммы лежали на отрезке значит, и на отрезке теперь они лежат на отрезке — победа.
Ответ: