Maths Olympiad Prep

Library / /29 of 35

Number theory Difficulty 6.3 National olympiad Prove it Slovenia

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 1010. Prove that they cannot divide the silver coins in the same way.

Solution

Let a1a_1 denote the number of golden coins given to the first pirate, a2a_2 the number of golden coins given to the second pirate, and so on. Since 10aiaj10 \nmid a_i - a_j for all iji \ne j, the numbers a1,a2,,a10a_1, a_2, \dots, a_{10} must give different remainders when divided by 1010. There are only 1010 possible remainders, so these are exactly all the numbers aia_i. Write ai=10ki+lia_i = 10k_i + l_i where lil_i is the remainder of aia_i when dividing by 1010. The total number of golden coins is equal to
a1+a2++a10=10(k1++k10)+(l1++l10). a_1 + a_2 + \dots + a_{10} = 10(k_1 + \dots + k_{10}) + (l_1 + \dots + l_{10}).
Since the numbers l1,,l10l_1, \dots, l_{10} are exactly the numbers 0,1,2,,90, 1, 2, \dots, 9 (just not necessarily in this order), their sum is equal to l1+l2++l10=0+1+2++9=45l_1 + l_2 + \dots + l_{10} = 0 + 1 + 2 + \dots + 9 = 45. We conclude that there were 10(k1++k10)+4510(k_1 + \dots + k_{10}) + 45 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 10(m1+m2++m10)+4510(m_1 + m_2 + \dots + m_{10}) + 45 for some integers m1,,m10m_1, \dots, m_{10}. But the total number of silver coins is even, a contradiction.

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 and solution reproduced as published; topic and difficulty added by this site.