19-я Международная Жаутыковская олимпиада по математике, 2023 год

Сумма $n>2$ ненулевых вещественных чисел (не обязательно различных) равна нулю. Для каждого из $2^n-1$ способов выбрать несколько (не менее одного) из этих чисел подсчитали сумму выбранных чисел и все полученные $2^n-1$ сумм выписали в строку в невозрастающем порядке. Первое число в строке равно $S$. Найдите наименьшее возможное значение второго числа в строке. ( А. Голованов )

Комментарий/решение

Заметим, тогда сумма всех положительных чисел по модулю равна сумме всех отрицательных чисел.

Также, чтобы получить второе число мы должны либо прибавить к $S$ минимальное по модулю отрицательное либо отнять минимальное положительное. Разделим все числа на 2 группы: положительных и отрицательных. Тогда в какой-то группе по принципу Дирихле$ \geq \lceil \frac{n}{2} \rceil$. Опять применив принцип Дирихле, получим что существует элемент по модулю $\leq \frac{S}{\lceil \frac{n}{2} \rceil}$. Это значит что второе число $\geq S - \frac{S}{\lceil \frac{n}{2} \rceil}$.

Приведем пример на получившуюся оценку:

Пусть изначально заданы $\lceil \frac{n}{2} \rceil$ чисел равных $\frac{S}{\lceil \frac{n}{2} \rceil}$, а все остальные числа равны $-\frac{S}{\lfloor \frac{n}{2} \rfloor}$.

Пусть $x_1\ge x_2\ge ...\ge x_m>0>x_{m+1}\ge x_{m+2}...\ge x_n$ — $n$ числа.

Поскольку все числа ненулевые, $n>2$ и $\sum x_i=0$, имеем $n>m\ge 1$

Пусть $S,T$ — два первых числа в строке:

$S=\sum_{i=1}^mx_i$ и $T=S-\min(|x_m|,|x_{m+1}|)$

$S=\sum_{i=1}^mx_i\ge mx_m$ и, следовательно, $|x_m|\le\frac Sm$

$0=\sum_{i=1}^nx_i\le \sum_{i=1}^mx_i+(n-m)x_{m+1}$ и поэтому $|x_{m+1}|\le \frac S{n-m }$

Итак, $\min(|x_m|,|x_{m+1}|)\le \min(\frac Sm,\frac S{n-m})=\frac S{\max(m,n-m)}$

Итак, $T\ge S-\frac S{\max(m,n-m)}$ и для наименьшего $T$ мы ищем наименьший $\max(m,n-m)$, который равен $\left\ lceil\frac n2\right\rceil$

И это наименьшее значение действительно может быть достигнуто, например, с помощью чисел:

$\overbrace{\frac S{\left\lceil\frac n2\right\rceil},\cdots,\frac S{\left\lceil\frac n2\right\rceil}}^{\times\left\lceil\ frac n2\right\rceil},\overbrace{-\frac S{\left\lfloor\frac n2\right\rfloor},\cdots,-\frac S{\left\lfloor\frac n2\right\rfloor}} ^{\times\left\lfloor\frac n2\right\rfloor}$

Следовательно, ответ $\boxed{S-\frac S{\left\lceil\frac n2\right\rceil}}$