Skip to main content
OlympiadHQ

Browse · MathNet

Print

National Math Olympiad

Slovenia number theory

Problem

Ten pirates find a chest filled with golden and silver coins. There are twice as many silver coins in the chest as there are golden. They divide the golden coins in such a way that the difference of the numbers of coins given to any two of the pirates is not divisible by . Prove that they cannot divide the silver coins in the same way.
Solution
Let denote the number of golden coins given to the first pirate, the number of golden coins given to the second pirate, and so on. Since for all , the numbers must give different remainders when divided by . There are only possible remainders, so these are exactly all the numbers . Write where is the remainder of when dividing by . The total number of golden coins is equal to Since the numbers are exactly the numbers (just not necessarily in this order), their sum is equal to . We conclude that there were golden coins in the chest.

Now, let us assume that the pirates can divide the silver coins in the same way. As above we come to the conclusion that the total number of silver coins is equal to for some integers . But the total number of silver coins is even, a contradiction.

Techniques

Modular ArithmeticPigeonhole principle