Олимпиада Туймаада по математике. Младшая лига. 2019 год

В последовательности целых чисел $a_1$, $a_2$, $ldots$ произведение $a_1a_2$ отрицательно, а при $n > 2$ для вычисления $a_n$ среди всех пар $(i, j)$, $1\leq i < j < n$, которые ранее не выбирались, выбирается одна пара $(i, j)$, для которой $a_i+a_j$ имеет наименьшую абсолютную величину, и полагается $a_n=a_i+a_j$. Докажите, что $a_i=0$ при некотором $i$. ( А. Голованов )

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

Учитывая $a_1$,$a_2$, мы можем найти $a_3$. Предположим, у нас есть $a_1,a_2,...a_n$. Обратите внимание, что мы еще не использовали пару наименьших положительных чисел и наибольшего отрицательного числа среди $. a_1,a_2,...a_n$, чтобы получить член этой последовательности. Допустим, этот член равен $P$ и $N$. Итак, мы имеем $|a_{n+1}|\le P+N$. Предположим, что $P+N$ положителен.

Теперь мы утверждаем, что в последовательности есть число, принадлежащее $[N+1,P-1]$.

Доказательство: если $a_{n+1}\in [N+1,P-1]$, то все готово. В противном случае $a_{n+1} \in [-(P+N),N+1]$. Если все $a_i$ после $a_{n+1}$ находятся в $[-(P+N), N+1]$, то, поскольку эти $a_i$ представляют собой сумму двух предыдущих $a_s$ и $a_t$, и если они имеют разные знаки, то их абсолютное значение будет не меньше $P$. Существует только конечное число таких членов. .Таким образом, эти члены можно представить как сумму нескольких отрицательных предыдущих $a_i$. Итак, если $P+N < r|N + 1|$ для некоторого r, то в образуя эти термы. Но опять же, таких термов существует лишь определенно много. Значит, здесь должен быть терм из $[N+1,P-1]$.

Таким образом, разница между максимальным отрицательным и минимальным положительным значением уменьшается как минимум на 1. Итак, через некоторое время мы должны получить $a_i$ с

$|a_i| < 1$.