Maths Olympiad Prep

Library / /11 of 19

Number theory Difficulty 5.1 AIME, harder Prove it United States

Problem:

In a certain kingdom, the only coin values are 33 and 55. Determine all possible amounts of money you can have using only these coins.

Solution

Solution:

The amounts of money that you can have are all positive integers except 1,2,41, 2, 4, and 77. We can see that all these are impossible. To show that all other amounts are possible, it is clear that 33 and 55 are possible. Also, 6,8,96, 8, 9, and 1010 are all possible, since
6=3+3,8=3+5,9=3+3+3,10=5+5. \begin{aligned} 6 & = 3 + 3, \\ 8 & = 3 + 5, \\ 9 & = 3 + 3 + 3, \\ 10 & = 5 + 5. \end{aligned}
Now, any higher amount of money has a remainder of 0,10, 1, or 22 when divided by 33. If it has a remainder of 00, it is 99 plus a multiple of 33; if it has a remainder of 11, it is 1010 plus a multiple of 33; and if it has a remainder of 22, it is 88 plus a multiple of 33. No matter what, it is one of 8,98, 9, or 1010 plus a multiple of 33, so we can just add more 33 coins to get from one of 8,98, 9, or 1010 to our number. Thus, all higher amounts of money can be made.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.