3
$\begingroup$

(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!

$\endgroup$
  • $\begingroup$ For 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. $\endgroup$ – akkkk Nov 22 '12 at 17:32
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.