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

Нөлге тең емес нақты $n$ санның қосындысы нөлге тең ($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}}$