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 x1,x2,… be the given sequence and let sn=x1+x2+…+xn. The conditions from the hypothesis can be now written as sn+7<sn and sn+11>sn for all n≥1. We then have: 0<s11<s4<s15<s8<s1<s12<s5<s16<s9<s2<s13<s6<s17<s10<s3<s14<s7<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 s10<s3<s14<s7<0<s11<s4<s15<s8<s1<s12<s5<s16<s9<s2<s13<s6. We have x1=s1 and xn=sn−sn−1 for n≥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 [x1x2x3x4x5x6x7x8x9x10 x11x2x3x4x5x6x7x8x9x10x11 x12x3x4x5x6x7x8x9x10x11x12 x13x4x5x6x7x8x9x10x11x12x13 x14x5x6x7x8x9x10x11x12x13x14 x15x6x7x8x9x10x11x12x13x14x15 x16x7x8x9x10x11x12x13x14x15x16 x17]. 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).