Competition problem — Combinatorics

Library / /11 of 11

Combinatorics Difficulty 6.5 National olympiad Prove it Estonia

Call a tuple $(a_1, \dots, a_n)$ of real numbers stable if the sums $a_1 + a_2 + \dots + a_k$ , as well as the sums $a_k + a_{k+1} + \dots + a_n$ , where in both cases $0 < k \le n$ , are either all negative or all non-negative.
For instance, the tuple $(3, -1, 2)$ is stable, since:
$\begin{array}{lclcl} 3 & \ge & 0, & 2 & \ge 0, \\ 3 + (-1) & \ge & 0, & (-1) + 2 & \ge 0, \\ 3 + (-1) + 2 & \ge & 0; & 3 + (-1) + 2 & \ge 0. \end{array}$
Prove that in any stable tuple with at least 3 terms where all terms are alternately negative and non-negative (it is unknown whether the first term is negative or non-negative), there exist 3 consecutive terms that together (without reordering) form a stable tuple on their own.

Solution

Consider terms 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}$ together form a stable subtuple. 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}$ , hence $a_{i-1}$ , $a_i$ , $a_{i+1}$ together form a stable tuple.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.