- 177

- 24

Here in Europe, however, people often still use cash in many situations.

This obviously has a side effect concerning coins.

Except when you go to a bar, restaurant, etc, and round the sum to leave a tip, in all other cases you have to pay an exact amount of money, which is most often a decimal number.

So, if you pay the exact amount, or a whole number in excess of it plus the decimal part, you will get no small coins in return: at most pieces of 1.00 and 2.00.

But if you pay an amount corresponding to a whole number, you will most often get back small coins, i.e. pieces of 0.01, 0.02, 0.05, 0.10, 0.20 and 0.50.

Suppose you want to get rid of these small coins by spending them, but of course you don't want to carry a lot of weight around with you.

So here's the question: what is the smallest set of small coins (pieces of 1, 2, 5, 10, 20 and 50 cents) you need to have with you to be able to put together (once) any sum between 1 and 99 cents?

I thought this kind of problem had to do with the theory of Diophantine equations, but I wasn't sure how to set it up, so I just went by trial and error, and my solution seemed to be the following:

[1,2,5,10,20,50] + any one of [1,10], [1,20], [2,10], [2,20]

I know that with these 8 coins one can indeed make any number between 1 and 99.

But is this the optimal solution? Or could one do this with even fewer coins?

L