Maths Olympiad Prep

Library / /4 of 4

Combinatorics Difficulty 7.0 National Olympiad, round 2 Prove it Austria

There are nn children in a room. Each child has at least one piece of candy. In Round 1, Round 2, etc., additional pieces of candy are distributed among the children according to the following rule:
*In Round kk, each child whose number of pieces of candy is relatively prime to kk receives an additional piece.*
Show that after a sufficient number of rounds the children in the room have at most two different numbers of pieces of candy.

Solution

We observe that a child that has k1k - 1 or k+1k + 1 pieces of candy at the start of Round kk will receive an additional piece because of gcd(k,k±1)=1\text{gcd}(k, k \pm 1) = 1 and be in the same situation in the next round. Furthermore, in each round, the number of the round will increase by 1 and the number of pieces of each child will increase by 0 or by 1. Therefore, for each child, the difference of pieces and the round number is positive or zero at the start and after each round will either remain equal or drop by 1. Since we have already seen that the difference is stable at 1-1, it cannot drop below 1-1.
Therefore, it remains to show that the difference +1+1 and 1-1 are the only ones that can stay constant forever which will prove that for each child the number of pieces of candy will eventually drop to k1k - 1 or k+1k + 1.

If the difference is 0, the child has kk pieces of candy. For k=1k = 1, the child receives a piece, but receives nothing in the following round, so the difference drops to 1-1 after two steps. For k>1k > 1, the child immediately receives nothing and the difference drops to 1-1.
If the difference dd is bigger than 1, then there must occur a round with a number divisible by dd after at most dd steps. Either the difference already drops before this round or this dd will be a common divisor of round number and candy piece number, therefore the difference will drop by 1 after at most dd steps.
This proves that after sufficiently long time all children will have k1k-1 or k+1k+1 pieces of candy at the start of Round kk and all of them will receive one additional piece during each round forever after.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.