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.
Problem
Source:
Tags: combinatorics, point set, combinatorial geometry, Ramsey Theory, IMO Shortlist
30.08.2010 16:26
In the question replace $1985 \to n$, and $662 \to \frac{n}{3}$, and use induction. The statement is trivially true for $n=1,2,3$, now suppose it is true for $n\le k$ and consider $n=k+3$. Among the $k+3$ points find some sequence that goes $+1, \underbrace{-1,-1,\dots,-1}_{\ge 1},+1$. Now remove the two $+1$'s and one $-1$. This leaves $n$ points, so by our assumption there is a good point, $p$ (which must be poisitive). Now when we replace the points we removed, the point $p$ is still a good point because the two positive values lie either side of the negative value and therefore don't decrease the partial sums from either direction.
21.06.2011 01:27
Just another solution: We use n and n/3 again.. Assume towards a contradiction that there exists no good point. Then, for every 1, consider the contiguous sum of smallest length that starts with that 1 and equals 0. Clearly, that sum ends with a -1. Now, every 1 corresponds to exactly 1 -1 (if there are 2 sequences of minimal length, pick the one that goes right). For every -1, there can be at most 2 1s that correspond to it (this isn't hard to see.) But this is a contradiction since if we have <n/3 ones, we can't possibly have this correspondence.
21.06.2011 05:56
riemannHypothesis2.71828 wrote: For every -1, there can be at most 2 1s that correspond to it (this isn't hard to see.) $1$ on the $B,C,D$ correspond to $-1$ on $A$.
Attachments:
21.06.2011 07:20
Consider three consecutive blocks of equal lengths such that the first and third blocks consist of +1s and the middle block consists of -1s. Remove such blocks repeatedly until no -1 remains (clearly possible since # of +1s > twice # of -1s). At the end, the remaining +1 is good. Obviously it is also good in the beginning.
21.06.2011 09:26
Yinxiu, what drawing program did you use? Thanks.
21.06.2011 10:56
The Geometer'S Sketchpad