Maths Olympiad Prep

Library / /379 of 520

Number theory Difficulty 6.9 National olympiad Prove it

The central bank of Sikinia mints coins worth 11 and 12 Kulotnik. During a burglary, 11 Sicilian thieves cracked a safe and looted coins with a total value of 5940 Kulotnik. They try for a while to fairly divide the loot among themselves - so that everyone gets the same amount - but they can't manage it; after a while, their leader claims to have figured out that it is indeed impossible.
Prove that they did not loot any coin worth 12 Kulotnik.

Solution

The thieves may have looted 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 distribution of the loot among the thieves.
From (1), we have 11a=12(495b)11 a = 12 \cdot (495 - b), meaning 11a11 a is divisible by 12. Since 11 and 12 are coprime, aa must also be a multiple of 12. Therefore, the thieves can distribute the looted 11-Kulotnik coins into a12\frac{a}{12} bags, each containing 1211=13212 \cdot 11 = 132 Kulotnik. Similarly, (1) implies the equation 12b=11(540a)12 b = 11 \cdot (540 - a), so 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 thieves can take one coin worth 12 Kulotnik, and the number b11b - 11 of the remaining 12-Kulotnik coins is still divisible by 11, allowing them to be distributed into b111\frac{b}{11} - 1 bags, each containing 1112=13211 \cdot 12 = 132 Kulotnik.
Since

59401112=5808=13244 5940 - 11 \cdot 12 = 5808 = 132 \cdot 44

the undistributed remainder of the loot is now in 44=11444 = 11 \cdot 4 bags, each containing 132 Kulotnik. If each of the 11 thieves takes 4 of these bags, they will have fairly divided the loot. However, since their leader proved that this is impossible, our assumption b>0b > 0 must be false: In other words, there was indeed no coin worth 12 Kulotnik in the safe.

Remark. Some participants came up with very creative nicknames for the thieves: bank robbers, pirates, gangsters, bandits, criminals, offenders, thieves.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.