(French Mathematical Olympiad 1997) Each vertex of a regular $1997$-gon is labeled with an integer, so that the sum of the integers is $1$. We write down the sums of the first $k$ integers read counterclockwise, starting from some vertex ($k = 1,2,\dots,1997$). Can we always choose the starting vertex so that all these sums are positive? If yes, how many possible choices are there? Thanks!
How many possible choices are there?
-
0For the existence part, start from any vertex $n$, and choose $i$ such that the partial sum of the integers from vertex $n$ through $i$ is minimal. Now, for any $k$, starting from $i+1$ will work. – 2012-11-22
1 Answers
The answer is “yes”. We can always choose a starting vertex like that.
First, let's change the problem a bit. Subtract $1/1997$ from each integer. Now numbers at vertices of the polygon are no longer integers; but rather they are rational numbers. The sum of all numbers is $0$. Our goal now is to find a starting point $i$ such that the sum of any $k$ numbers starting from $i$ is non-negative (this is equivalent to the original condition).
Let $S_i$ be the sum of first $i$ numbers starting from vertex $1$. Note that the sum of numbers between $i$ and $j$ equals $S_j - S_i$ (here we use that all numbers add up to $0$). We need to find $i$ such that for every $j$: $S_j - S_i \geq 0$.
That happens precisely when $S_i$ is less than or equal to all other numbers $S_j$.
Obviously, there is always at least one such $i$. On the other hand, note that all numbers $S_i$ are distinct. Indeed, $S_i$ equals to an integer minus $i/1997$ and for every two distinct $i$ and $j$ the number $i-j$ is not divisible by $1997$. So there is exactly one number $S_i$ that is less than or equal to all numbers $S_j$.
Answer: There is only one way to choose the starting vertex as required.