IMO 1985 SL 14

Problem

4b.(IRE 4) A set of 1985 points is distributed around the circumference of a circle and each of the points is marked with 1 or −1. A point is called “good” if the partial sums that can be formed by starting at that point and proceeding around the circle for any distance in either direction are all strictly positive. Show that if the number of points marked with −1 is less than 662, there must be at least one good point.

Solution

It suffices to prove the existence of a good point in the case of exactly 661 −1’s. We prove by induction on k that in any arrangement with 3k + 2 points k of which are −1’s a good point exists. For k = 1 this is clear by inspection. Assume that the assertion holds for all arrangements of 3n+2 points and consider an arrangement of 3(n + 1) + 2 points. Now there exists a sequence of consecutive −1’s surrounded by two +1’s. There is a point P which is good for the arrangement obtained by removing the two +1’s bordering the sequence of −1’s and one of these −1’s. Since P is out of this sequence, clearly the removal either leaves a partial sum as it was or diminishes it by 1, so P is good for the original arrangement. Second solution. Denote the number on an arbitrary point by a1, and the numbers on successive points going in the positive direction by a2, a3, . . . (in particular, ak+1985 = ak). We define the partial sums s0 = 0, sn = a1 + a2 + \cdot \cdot \cdot + an for all positive integers n; then sk+1985 = sk + s1985 and s1985 \geq663. Since s1985m \geq663m and 3 \cdot 663m > 1985(m + 2) + 1 for large m, not all values 0, 1, 2, . . .663m can appear thrice among the 1985(m + 2) + 1 sums s−1985, s−1984, . . . , s1985(m+1) (and none of them appears out of this set). Thus there is an integral value s > 0 that appears at most twice as a partial sum, say sk = sl = s, k < l. Then either ak or al is a good point. Actually, si > s must hold for all i > l, and si < s for all i < k (otherwise, the sum s would appear more than twice). Also, for the same reason there cannot exist indices p, q between k and l such that sp > s and sq < s; i.e., for k < p < l, sp’s are either all greater than or equal to s, or smaller than or equal to s. In the former case ak is good, while in the latter al is good.