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.
Problem
Source:
Tags: algorithm, relatively prime, modular arithmetic, combinatorics, invariant, IMO Shortlist
30.08.2010 12:19
There is an easy way to show that if m=n+1 then you can win: Base case: trivial now let M be the largest number of balls in our initial condition. Now by the induction hypothesis u can make the other m-1 boxes have the same number of balls by choosing n-1 boxes at each iteration, at each step the remaining box to be chosen is the one that started off with M. It is easy to see that this box now has the largest number of balls. Now just keep placing a ball in each of the other m-1 boxes until you win. You can extend this easily to the case where $m \equiv 1 \mod n$: Firstly order your boxes in order of the ammount of balls in them initially. Focusing on the first lot of n+1 boxes we know by the previous result that we can win this mini game on these n+1 boxes. Then play the game on boxes n+1,n+2...2n+1, then play the game on the boxes 2n+1,2n+2...3n+1 etc. etc. You then have the case where the first n boxes have the same number of balls, then the next n boxes have the same number of balls ... etc. the last lot of n+1 boxes have the same number of balls. Also, the number of balls are in increasing order, so we can just easily add in just enough balls in the first lot of m-(n+1) to win the whole game.
31.08.2010 04:02
Ok I have completed part 1 now: let $a_i$ be the number of balls in the ith box. Using the ideas in my previous post, it is obvious that given any initial condition, we can ALWAYS end up with the case where there are only at most two different $a_i$. SO suppose we have such a case, we can assume WLOG that the $a_i$ are: x x x x ... x 0 0 0 ... 0. In fact for simplicity we will prove it for x=1, and the the general case follows (since you can just apply the same procedure except by adding 1 ball u add x balls by doing the operation x times). so I will give a demonstration of my algorithm for m=7,n=4 and the following initial condition. 1 1 0 0 0 0 0 we start by adding 1's to the next four: 1 1 1 1 1 1 0 then again (except the remaining ones we cycle back to the start): 2 2 2 1 1 1 1 then again: 2 2 2 2 2 2 2 done! Now to prove that this algorithm works when $gcd(m,n)=1$, take a look at the bold numbers above, it is the "last box with the largest number of balls", let's say the position of this box after $k$ iterations is $x_k$, and $x_0$ is the initial position (so $x_0=2$ in our example). Now $x_k=x_0 + kn$ (in $\mathbb{Z}\big / m\mathbb{Z}$) but from simple modular arithmetic: $n=x_0+kn$ must have some solution $k$.