Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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. –  akkkk Nov 22 '12 at 17:32

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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