Baltic Way 2011 · Shortlist problem

Answer: $k$.

Call stable tuples, whose elements are alternately negative and non-negative, interesting. We first show that each interesting tuple contains at least one stable subtuple of 3 elements.

For that, consider elements whose absolute value is minimal in the tuple. If there exists a negative such element, denote it $a_i$, then the sum of $a_i$ and its any neighbour is non-negative. Thus $a_i$ is neither the first nor the last in the tuple because of stability of the tuple. But then both $a_{i-1} + a_i$ and $a_i + a_{i+1}$ are non-negative, as well as $a_{i-1} + a_i + a_{i+1}$, hence $(a_{i-1}, a_i, a_{i+1})$ is a stable subtuple.

On the other hand, if all elements with minimal absolute value are non-negative then let $a_i$ be any of them. Analogously to the previous case, both $a_{i-1} + a_i$ and $a_i + a_{i+1}$ are negative, as well as $a_{i-1} + a_i + a_{i+1}$, whence $(a_{i-1}, a_i, a_{i+1})$ is a stable tuple.

Next we can see that replacing an element in a stable tuple with a stable subtuple whose sum of elements equals to the element removed always leads to a stable tuple. For that, let the original tuple be $(a_1, \dots, a_n)$ and let $a_i$ be replaced with $b_1, \dots, b_m$. If $n=1$ then the claim is trivial, hence assume that $n > 1$. Consider an arbitrary subtuple starting from the beginning of the whole tuple. If either no substituted elements are included or all substituted elements are included then the sum falls to the right side of zero by assumptions. If the subtuple ends with some $b_j$ then the sum of its elements is $a_1 + \dots + a_{i-1} + b_1 + \dots + b_j$. By stability of $(b_1, \dots, b_m)$, the sum $b_1 + \dots + b_j$ falls to the same side from zero as $a_i$ and $b_{j+1} + \dots + b_m$. Hence $b_1 + \dots + b_j$ falls between 0 and $a_i$. As $a_1 + \dots + a_{i-1}$ and $a_1 + \dots + a_{i-1} + a_i$ fall to the same side from zero, also $a_1 + \dots + a_{i-1} + b_1 + \dots + b_j$ falls to the same side. Similarly, we can show the desired property for subtuples taken from the end of the tuple.

Lastly, we show by induction on $k$ that any interesting $(2k+1)$-tuple contains at least $k$ stable subtuples containing more than one element. If $k = 0$ then the claim holds trivially. Suppose that $k > 0$ and the claim holds for $k - 1$. Find a stable subtuple of 3 elements in the given $(2k + 1)$-tuple. After replacing these three elements with their sum, we get a $(2(k - 1) + 1)$-tuple that is clearly stable. By stability of the 3-tuple replaced, the sum of its elements falls to the same side from zero as its first and third element, hence the alternation of signs is also maintained. By the induction hypothesis, the new tuple contains at least $k-1$ stable subtuples of more than one element. After substituting the removed elements back, each of these $k$ stable subtuples remains stable. Moreover, the 3-tuple itself will be the desired $k$th stable subtuple.

It remains to show that there are interesting $(2k+1)$-tuples that contain no more than $k$ stable subtuples. For example, let $a_i = \left(-\frac{1}{2}\right)^i$ for $i = 1, \dots, 2k$ and $a_{2k+1} = -\frac{1}{3}$. The sum of the first $2j$ elements is $-\frac{1 - \frac{1}{4j}}{3}$ that is negative. Thus also the sum of $2j+1$ elements is always negative. As $a_2 + \dots + a_{2k} = -\frac{1 - \frac{1}{4k}}{3} + \frac{1}{2} < \frac{1}{3}$, also all sums of consecutive elements taken from the end are negative. Thus the tuple is stable.

Consider any subtuple $(a_u, \dots, a_v)$ where $u < v \le 2k$. If $u$ and $v$ have different parity then the subtuple is not stable (every interesting tuple must have an odd number of elements). If $u$ and $v$ are both odd then $a_u + a_{u+1} < 0$ while $a_{v-1} + a_v > 0$. The case with $u$ and $v$ both even is analogous. Thus the subtuple under consideration is not stable.

Hence only those of the subtuples with more than one element that contain $a_{2k+1}$ can be stable. But there are only $k$ such subtuples of odd length. This completes the solution.