Olympiad Maths Prep

Library / /9 of 11

Combinatorics Difficulty 6.7 National olympiad Prove it Czech Republic

Each of nn Robin Hoods (n3n \ge 3) robbed some coins. Together they have earned 100n100n coins. They have decided to cut the loot in a following way: in one step one Robin can take his two coins and give to some other two Hoods, one coin each. Find all positive integers n3n \ge 3 for which they can split the loot in equal parts (100100 coins each). (Ján Mazák)

Solution

Let ziz_i denote through the process the number of coins of the ii-th Robin Hood.

Let n=3n = 3. After any step, z1z2z_1 - z_2 modulo 33 does not change. That means for z1=101z_1 = 101, z2=100z_2 = 100, and z3=99z_3 = 99 (out of many choices), z1z_1 will never be the same as z2z_2. Thus n=3n = 3 is not a solution.

Now we show that for each n4n \ge 4 any initial ziz_i the loot can be split in equal parts.

Let s=zi100s = \sum |z_i - 100|. We decrease number ss as long as it can be done in the way that some of the outlaws with maximal count of coins gives his two coins to (some of the) Hoods with the minimal count of coins. If ss can be reduced to 00 in this way, we are done.

If s0s \neq 0, some of the outlaws has 100k100-k coins (k>0k > 0), kk outlaws have 101101 coins each and all the others have 100100 coins each. If k2k \ge 2, we decrease ss in two steps:
100k, 101, 101100k+1, 102, 99100k+2, 100, 100. 100 - k,\ 101,\ 101 \rightarrow 100 - k + 1,\ 102,\ 99 \rightarrow 100 - k + 2,\ 100,\ 100.
If kk is even, then after 12k\frac{1}{2}k such "double" steps every outlaw will have 100100 coins each. If kk is odd then we end in the state in which one of the outlaws has 9999 coins, one has 101101 coins and all the others have 100100 coins. We finish as follows:
99, 100, 100, 10199, 101, 101, 9999, 102, 99, 100100, 100, 100, 100. 99,\ 100,\ 100,\ 101 \rightarrow 99,\ 101,\ 101,\ 99 \rightarrow 99,\ 102,\ 99,\ 100 \rightarrow 100,\ 100,\ 100,\ 100.

Looking for a route rather than 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 and solution reproduced as published; topic and difficulty added by this site.