Skip to main content
OlympiadHQ

Browse · MathNet

Print

Mathematical Olympiad Rioplatense

Argentina number theory

Problem

There are only coins of pesos and 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 pesos. The cone costs 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 pesos is sufficient. There is only one way to express as with , nonnegative integers: with and . So each customer has coins of and coins of . Hence to serve a customer as desired it is enough to have available either coins of or coins of (or both). In the first case the salesperson takes from the customer coins of and gives back coins of : . In the second case the salesperson takes coins of and gives back coins of : .

An initial amount of pesos ensures coins of or coins of . Indeed if there were at most coins of and at most coins of then . So the first customer can be attended whenever . The remaining ones can be attended too, because will be still greater when their turn comes.
Final answer
108

Techniques

Techniques: modulo, size analysis, order analysis, inequalitiesInvariants / monovariants