Задача 10. Наборы из нулей и единиц со знаками

Квадрат суммы

Сумма попарных произведений появляется, когда возводят сумму в квадрат: каждое произведение $a_i a_j$ с $i < j$ встречается в квадрате дважды. Пусть $t = a_1 + \ldots + a_5$. Тогда

Каждое $a_i^2$ равно $1$, если $a_i = \pm 1$, и $0$, если $a_i = 0$. Поэтому сумма квадратов равна $m$ — числу ненулевых чисел в наборе, и

Чтобы $S$ было маленьким, нужно, чтобы $m$ было большим, а $t^2$ — маленьким.

Оценка снизу

Сумма $t$ состоит из $m$ слагаемых $\pm 1$, поэтому $t$ той же чётности, что и $m$. Переберём $m$:

• $m = 5$: $t$ нечётно, значит $t^2 \geqslant 1$ и $S \geqslant \dfrac{1 - 5}{2} = -2$;
• $m = 4$: $t$ чётно, $t^2 \geqslant 0$ и $S \geqslant \dfrac{0 - 4}{2} = -2$;
• $m \leqslant 3$: $S \geqslant \dfrac{0 - 3}{2} > -2$.

Итак, всегда $S \geqslant -2$, и $S = -2$ бывает только в двух случаях: $m = 5,\ t = \pm 1$ или $m = 4,\ t = 0$.

Случай без нулей

$m = 5$, $t = \pm 1$: все числа ненулевые, и из них три одного знака и два другого (например, $1 + 1 + 1 - 1 - 1 = 1$). При $t = 1$ нужно выбрать, на каких $2$ местах из $5$ стоят минусы: $C_5^2 = 10$ способов; при $t = -1$ — ещё $10$. Всего $20$ наборов.

Случай с одним нулём

$m = 4$, $t = 0$: ровно один ноль и среди остальных четырёх — два плюса и два минуса. Место нуля выбираем $5$ способами, затем места двух плюсов среди оставшихся четырёх — $C_4^2 = 6$ способами. Всего $5 \cdot 6 = 30$ наборов.

Ответ

Наименьшее значение $S = -2$ достигается в

упорядоченных наборах. Для нечётного $n$ так же получается $2\,C_n^{\frac{n-1}{2}} + n\,C_{n-1}^{\frac{n-1}{2}}$.