IMO 1985 SL 13

Problem

4a.(BUL 1) Let m boxes be given, with some balls in each box. Let n < m be a given integer. The following operation is performed: choose n of the boxes and put 1 ball in each of them. Prove: (a) If m and n are relatively prime, then it is possible, by performing the operation a finite number of times, to arrive at the situation that all the boxes contain an equal number of balls. (b) If m and n are not relatively prime, there exist initial distributions of balls in the boxes such that an equal distribution is not possible to achieve.

Solution

If m and n are relatively prime, there exist positive integers p, q such that pm = qn + 1. Thus by putting m balls in some boxes p times we can

achieve that one box receives q + 1 balls while all others receive q balls. Repeating this process sufficiently many times, we can obtain an equal distribution of the balls. Now assume gcd(m, n) > 1. If initially there is only one ball in the boxes, then after k operations the number of balls will be 1 + km, which is never divisible by n. Hence the task cannot be done.