Associativity from 1977 IMO

Here's Problem 2 from the 1977 IMO:

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.

Solutions can be found online or in [Engel, 85-86]. I'll cheat a little and solve a somewhat simpler problem:

In a finite sequence of real numbers the sum of any three successive terms is negative, and the sum of any five successive terms is positive. Determine the maximum number of terms in the sequence.

I propose that it could be useful to investigate an even simpler problem:

In a finite sequence of real numbers the sum of any two successive terms is negative, and the sum of any three successive terms is positive. Determine the maximum number of terms in the sequence.

Solution

So, in the sequence $x_1,x_2,\ldots,x_n,$ the sum of any three successive terms is negative, and the sum of any five successive terms is positive.

The main tool in solving the problem is associativity of addition.

First note that the sequence must have fewer than $3\cdot 5=15$ terms. Indeed, if $n\ge 15,$ we'll have, on one hand, $\displaystyle\sum_{i=1}^{15}x_{i}=\sum_{k=0}^{2}(x_{5k+1}+x_{5k+2}+x_{5k+3}+x_{5k+4}+x_{5k+5})\gt 0.$ On the other hand, $\displaystyle\sum_{i=1}^{15}x_{i}=\sum_{k=0}^{4}(x_{3k+1}+x_{3k+2}+x_{3k+3})\lt 0.$

And this is a contradiction. But the bound of $15$ for the chosen problem is too large. Next, I'll show that the number of terms could not be even $7.$ Indeed, Assume there are seven terms $x_1,$ $x_2,$ $x_3,$ $x_4,$ $x_5,$ $x_6,$ $x_7.$ Then

$\displaystyle\sum_{i=1}^{6}x_{i}=\sum_{i=1}^{3}x_{i}+\sum_{i=4}^{6}x_{i}\lt 0.$

However, $\displaystyle\sum_{i=1}^{5}x_{i}\gt 0$. It follows that $x_{6}\lt 0.$ Similarly, $\displaystyle\sum_{i=2}^{7}x_{i}\lt 0$ but $\displaystyle\sum_{i=3}^{7}x_{i}\gt 0,$ implying $x_{2}\lt 0.$ Now we obtain a contradiction:

$\displaystyle 0\lt \sum_{i=2}^{6}x_{i}=x_{2}+\sum_{i=3}^{5}x_{i}+x_{6}\lt 0.$

Finally, a sequence of six terms could be constructed in many ways. Choose arbitrary values for the sums (four three-terms sums and two five-term sums) and solve a linear system of six equations with six unknowns. The system can easily be reduced to a triangular form, and solved by Gauss elimination. For example, one can easily verify that the sequence $-3,5,-3,-3,5,-3.$ satisfies the requirements.

In general, assuming $p$ and $q$ are mutually prime, if every sum of $q$ successive terms is negative while the sum of $p$ successive terms is positive, the sequence may have at most $p+q-2$ terms, such that for the original IMO problem the answer was $7+11-2=16.$

References

  1. A. Engel, Problem-Solving Strategies, Springer Verlag, 1998

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

71935820