Skip to main content
OlympiadHQ

Browse · MathNet

Print

62nd Czech and Slovak Mathematical Olympiad

Czech Republic counting and probability

Problem

Each of Robin Hoods () robbed some coins. Together they have earned 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 for which they can split the loot in equal parts ( coins each). (Ján Mazák)
Solution
Let denote through the process the number of coins of the -th Robin Hood.

Let . After any step, modulo does not change. That means for , , and (out of many choices), will never be the same as . Thus is not a solution.

Now we show that for each any initial the loot can be split in equal parts.

Let . We decrease number 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 can be reduced to in this way, we are done.

If , some of the outlaws has coins (), outlaws have coins each and all the others have coins each. If , we decrease in two steps: If is even, then after such "double" steps every outlaw will have coins each. If is odd then we end in the state in which one of the outlaws has coins, one has coins and all the others have coins. We finish as follows:
Final answer
all integers n ≥ 4

Techniques

Invariants / monovariantsGames / greedy algorithms