In a finite sequence of real numbers the sum of any seven successive terms is negative and the sum of any eleven successive terms is positive. Determine the maximum number of terms in the sequence.
Problem
Source: IMO LongList, Vietnam 1, IMO 1977, Day 1, Problem 2
Tags: linear algebra, algebra, Sequence, maximization, Extremal combinatorics, IMO, IMO 1977
15.11.2005 20:17
This is in my Top 10 of all IMO problems. Not only because I was a competitor then, but also because I was present to the "problem solving session" organized by the hosts and I wached the Czech student Martin Chadek presenting his solution, which made the jury K.O. Here it is: Let $x_1,x_2,\ldots$ be the given sequence and let $s_n=x_1+x_2+\ldots+x_n$. The conditions from the hypothesis can be now written as $s_{n+7}<s_n$ and $s_{n+11}>s_n$ for all $n\ge 1$. We then have: $0<s_{11}<s_4<s_{15}<s_8<s_1<s_{12}<s_5<s_{16}<s_9<s_2<s_{13}<s_6<s_{17}<s_{10}<s_3<s_{14}<s_7<0,$ a contradiction. Therefore, the sequence cannot have $17$ terms. In order to show that $16$ is the answer, just take 16 real numbers satisfying $s_{10}<s_3<s_{14}<s_7<0<s_{11}<s_4<s_{15}<s_8<s_1<s_{12}<s_5<s_{16}<s_9<s_2<s_{13}<s_6$. We have $x_1=s_1$ and $x_n=s_n-s_{n-1}$ for $n\ge 2$. Thus we found all sequences with the given properties. As far as I know, Martin only solved this problem and got a special prize for it Other solutions are possible, including one using linear algebra. I'll post them if anyone is interested.
15.11.2005 21:27
Suppose a sequence of $17$ terms exists. Consider the matrix \[\begin{bmatrix} x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & x_8 & x_9 & x_{10} \ \ \ x_{11} \\ x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & x_8 & x_9 & x_{10} & x_{11} \ \ \ x_{12} \\ x_3 & x_4 & x_5 & x_6 & x_7 & x_8 & x_9 & x_{10} & x_{11} & x_{12} \ \ \ x_{13} \\ x_4 & x_5 & x_6 & x_7 & x_8 & x_9 & x_{10} & x_{11} & x_{12} & x_{13} \ \ \ x_{14} \\ x_5 & x_6 & x_7 & x_8 & x_9 & x_{10} & x_{11} & x_{12} & x_{13} & x_{14} \ \ \ x_{15} \\ x_6 & x_7 & x_8 & x_9 & x_{10} & x_{11} & x_{12} & x_{13} & x_{14} & x_{15} \ \ \ x_{16} \\ x_7 & x_8 & x_9 & x_{10} & x_{11} & x_{12} & x_{13} & x_{14} & x_{15} & x_{16} \ \ \ x_{17} \end{bmatrix}.\] The sum of the numbers in each of the rows is positive. The sum of the numbers in each of the columns is negative. That is a contradiction. It is easy to show that $16$ works
15.11.2005 21:35
Arne wrote: It is easy to show that 16 works This is the jury solution. They provided the example \[ 5,5,-13,5,5,5,-13,5,5,-13,5,5,5,-13,5,5. \] But how do you find such an example? That's why I loved Martin's solution
15.11.2005 22:26
More generally, it can be shown that : If $p,q$ are any two distinct positive integers such that none of them divides the other, and if a sequence has the property that the sum of any $p$ consecutive terms is always positive and the sum of any $q$ consecutive terms is negative then the maximal length of this sequence is $p+q-d-1$ where $d = \gcd (p,q).$ The proof I know is quite long, so that I will not write it here. It can be found in : Quadrature, n°54 (Oct. Dec. 2004), ex. E-218, p.34-36. Pierre.
15.11.2005 22:32
Well, this was proved during the competition by GB7, John Rickard, a gold medalist in 1977!
11.07.2013 10:14
enescu wrote: As far as I know, Martin only solved this problem and got a special prize for it No, he also fully solved Problem 4.
19.03.2022 05:08
Does this work or have I deluded myself? Not fully detailed. We claim that the answer is $16$. One can find a construction without too much difficulty. Call an $n$-sum the sum of $n$ consecutive terms. If we suppose, for contradiction, that the sequence has $17$ terms, then every $4$-sum can be written as an $11$-sum with a $7$-sum subtracted, and must hence be positive. Similarly, every $3$-sum can be written as a $7$-sum with a $4$-sum subtracted, and must therefore be negative. And, finally, every term can be written as a $4$-sum with a $3$-sum subtracted, and must therefore be positive again. However, if every term is positive, then it's impossible for every $7$-sum to be negative, and we've reached a contradiction.
21.03.2022 01:58
enescu wrote: Arne wrote: It is easy to show that 16 works This is the jury solution. They provided the example \[ 5,5,-13,5,5,5,-13,5,5,-13,5,5,5,-13,5,5. \]But how do you find such an example? That's why I loved Martin's solution >16 years late, but I think you can motivate this solution by noticing that $\frac 27>\frac 3{11}$, meaning that if we can make it so that we get exactly two negative numbers of pretty large magnitude in each block of length $7$ and $3$ in each block of length $11$ we would be done by making the other numbers all equal to some positive number. It's not so obvious to pick the numbers $5$ and $-13$, but maybe this is easier? \[20, 20, -51, 20, 20, 20, -51, 20, 20, -51, 20, 20, 20, -51, 20, 20.\] Note that the block of $11$ reaches from the first $-51$ to right before the last $20$.
18.07.2024 05:43
fairly popular technique in competitive programming - prefix sums! The answer is $16$. For $1 \leq |S| \leq 16$, we can consider any subset of $\{5,5,-13,5,5,5,-13,5,5,-13,5,5,5,-13,5,5\}$. For $0 \leq k \leq 17$, then suppose $P_k = S_1 + S_2 + \cdots + S_k$. Then, $P_{k} < P_{k-7}$ and $P_{k} < P_{k + 11}$. Therefore, \begin{align*} P_{0} < P_{11} < P_4 < P_{15} < P_1 < P_{12} < P_{5} < P_{16} < P_2 < P_{13} < P_6 < P_{17} < P_3 < P_{14} < P_0, \end{align*}which is clearly not possible. So, any sequence of $17$ real numbers has seven consecutive terms which sum to a negative value and has eleven consecutive terms which sum to a positive value. Thus, the maximum number of terms in the sequence is $\boxed{16}$.
06.01.2025 08:42
If $n \geq 17$ then take the first 17 numbers $a_1, \ldots, a_{17}$ and write them as follows. $$\begin{bmatrix} a_1 & a_2 & a_3 & a_4 & a_5 & a_6 & a_7\\ a_2 & \ddots & & & & & a_8 \\ \vdots & &\ddots & & & & \vdots\\ \vdots & & & \ddots & &\\ a_{11} & & & & & &a_{17} \end{bmatrix}$$ Summing across the rows we note that the total sum is negative, while summing across the columns we get that the total sum is positive. That is a contradiction. Thus $n \leq 16$, and $n=16$ can be constructed (posted in other posts above).