Problem

Source:

Tags: algorithm, relatively prime, modular arithmetic, combinatorics, invariant, IMO Shortlist



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.