Maths Olympiad Prep

Library / /1 of 6

Number theory Difficulty 7.6 National Olympiad, round 2 Prove it Germany

Problem:

The Central Bank of Sikinia mints coins worth 11 and 12 Kulotnik. During a burglary, 11 Sikinian crooks cracked a safe and made off with coins of a total value of 5940 Kulotnik. For a while they try to divide the loot fairly among themselves - that is, so that everyone receives the same amount - but they do not manage to do so; after a while their leader claims to have figured out that this is indeed not possible.
Prove that they did not steal any coin worth 12 Kulotnik.

Solution

Solution:

Let the crooks have stolen aa coins worth 11 Kulotnik and bb coins worth 12 Kulotnik. Here aa and bb are two non-negative integers with
11a+12b=5940=11540=12495 11 a + 12 b = 5940 = 11 \cdot 540 = 12 \cdot 495
We now assume b>0b > 0 and try to find a fair division of the loot among the crooks.
By (1), 11a=12(495b)11 a = 12 \cdot (495 - b), i.e. 11a11 a is divisible by 12. Since 11 and 12 are coprime, it follows that aa is also a multiple of 12, and therefore the crooks can distribute the stolen 11-Kulotnik coins into a12\frac{a}{12} small bags, each of which contains 1211=13212 \cdot 11 = 132 Kulotnik. Similarly, (1) implies the equation 12b=11(540a)12 b = 11 \cdot (540 - a), and hence 12b12 b is divisible by 11. As before, this shows that bb is also divisible by 11. Since we assumed b>0b > 0, each of the crooks can take a coin worth 12 Kulotnik, and the number b11b - 11 of the remaining 12-Kulotnik coins is still divisible by 11, so that these can be distributed into b111\frac{b}{11} - 1 small bags, which likewise each contain 1112=13211 \cdot 12 = 132 Kulotnik.
Because of
59401112=5808=13244 5940 - 11 \cdot 12 = 5808 = 132 \cdot 44
the as yet undistributed remainder of the loot is now contained in 44=11444 = 11 \cdot 4 small bags of 132 Kulotnik each. If now each of the 11 crooks takes 4 of these small bags, they have altogether divided the loot fairly. But since their leader was able to prove that this is not possible at all, our assumption b>0b > 0 must have been false: in other words, there was indeed no coin worth 12 Kulotnik in the safe.

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 translated into English from de; metadata (topic, difficulty) added by this project.