n integers totalling n - 1 are arranged in a circle. Prove that we choose one of the integers x_{1}, so that the other integers going around the circle are, in order, x_{2}, ... , x_{n} and we have ∑_{1}^{k} x_{i} ≤ k - 1 for k = 1, 2, ... , n.

**Solution**

Let the integers be y_{i} (starting from an arbitary position). We use the convention that subscripts are reduced mod n when necessary. Let z_{j} = ∑_{1}^{j} (y_{i} - (n-1)/n). The amount (n-1)/n is chosen so that z_{n} = 0 and hence the sum of any group of s consecutive y_{i}: y_{r+1} + ... + y_{r+s} is simply z_{r+s} - z_{r} + s(n-1)/n.

Let z_{h} be the largest z_{j}. Take x_{1} = z_{h+1}. Then the sum of the first k terms is z_{h+k} - z_{h} + k(n-1)/n <= k(n-1)/n, since z_{h} >= z_{h+k}. Hence the sum of the first k terms is < k, but it is integral, so it is ≤ k-1.

© John Scholes

jscholes@kalva.demon.co.uk

12 Dec 1998