49th Kürschák 1948

Prove that among any n positive integers one can always find some (at least one) whose sum is divisible by n.

Solution

Call the numbers a₁, a₂, ... , a_n. Consider the n sums a₁, a₁+a₂, a₁+a₂+a₃, ... , a₁+a₂+ ... +a_n. If any of them = 0 mod n, then we are home. If not, then two of them, a₁+a₂+ ... +a_i and a₁+a₂+ ... +a_j (with i < j) must be equal mod n (only n-1 other values available mod n). But then their difference, a_i+1+a_i+2+ ... +a_j, is divisible by n.

49th Kürschák 1948

© John Scholes
jscholes@kalva.demon.co.uk
29 Oct 2003
Last corrected/updated 29 Oct 03