n integers totalling n - 1 are arranged in a circle. Prove that we choose one of the integers x1, so that the other integers going around the circle are, in order, x2, ... , xn and we have ∑1k xi ≤ k - 1 for k = 1, 2, ... , n.
Solution
Let the integers be yi (starting from an arbitary position). We use the convention that subscripts are reduced mod n when necessary. Let zj = ∑1j (yi - (n-1)/n). The amount (n-1)/n is chosen so that zn = 0 and hence the sum of any group of s consecutive yi: yr+1 + ... + yr+s is simply zr+s - zr + s(n-1)/n.
Let zh be the largest zj. Take x1 = zh+1. Then the sum of the first k terms is zh+k - zh + k(n-1)/n <= k(n-1)/n, since zh >= zh+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