Maths Olympiad Prep

Library / /13 of 18

Number theory Difficulty 7.2 National olympiad, round 2 Prove it Argentina

There are only coins of 1111 pesos and 1313 pesos in a country (and no bills). An ice-cream shop is about to open and there is a line of customers waiting. Every customer wants to buy a cone of ice-cream and has exactly 155155 pesos. The cone costs 1212 pesos. The salesperson wants to attend everyone by giving back the exact change without borrowing or exchanging money. Find the minimum amount of money she needs to have in advance in order to do so.

Solution

Having 108108 pesos is sufficient. There is only one way to express 155155 as 11a+13b11a + 13b with aa, bb nonnegative integers: with a=7a = 7 and b=6b = 6. So each customer has 77 coins of 1111 and 66 coins of 1313. Hence to serve a customer as desired it is enough to have available either 66 coins of 1111 or 55 coins of 1313 (or both). In the first case the salesperson takes from the customer 66 coins of 1313 and gives back 66 coins of 1111: 613611=126 \cdot 13 - 6 \cdot 11 = 12. In the second case the salesperson takes 77 coins of 1111 and gives back 55 coins of 1313: 711513=127 \cdot 11 - 5 \cdot 13 = 12.

An initial amount of N108N \ge 108 pesos ensures 66 coins of 1111 or 55 coins of 1313. Indeed if there were at most 55 coins of 1111 and at most 44 coins of 1313 then N511+413=107N \le 5 \cdot 11 + 4 \cdot 13 = 107. So the first customer can be attended whenever N108N \ge 108. The remaining ones can be attended too, because NN will be still greater when their turn comes.

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.