# Exchange without changes

There are three type of amount currencies that is less than 10 namely: 1, 2, and 5. You are going to drug store, supermarket, restaurant today where you will have three exchanges(buy medicine, buy goods, eat food ). For convenience you don't want to any changes which are less than 10 denomination(amount type of 1, 2, and 5) in these three exchanges, How many changes with amount type of 1, 2, 5 should you bring respectively at least?

My thought is: if there is only one exchange involved, you'd bring number of small changes 1, 2, and 5 whose sum combination equal any integer numbers from 1 to 9. So I get the result list{1, 2, 2, 5} i.e. one number of one amount currency, two number of two amount currency, and one number of five amount currency. Now considering three exchanges, I'd simply multiply this with three so the result list is {1, 1, 1, 2, 2, 2, 2, 2, 2, 5, 5, 5}.

Is my reasoning correct? and How will you think this question?

-
That is, you want to be able to make the amount $x$, then the amount $y$, then the amount $z$, each amount being less than 10, and you want to make these amounts using only 1s, 2s, and 5s, and you want to carry around as few coins as possible (and you don't know in advance what $x,y,z$ will be). – Gerry Myerson Jul 15 '11 at 12:50

## 2 Answers

You have shown your set will work, but you have not proved it minimal. An alternate set (no better in count, but lower total value) for a single transaction is {5,2,1,1}. You must bring at least 27 in total value, but you have 30. If you remark that if each transaction is 9 it takes at least four coins then you show that you must bring 12 and you are done. Added: but see Gerry's point below. It can be done with 11, making use of the extra value in the 2s.

-
3 5s, 5 2s, 3 1s can make 3 9s with just 11 coins; 5-2-2, 5-2-2, 5-2-1-1. – Gerry Myerson Jul 15 '11 at 12:57
@Gerry: good point. – Ross Millikan Jul 15 '11 at 12:59
@Gerry, you missed one 1s in your break down – didxga Jul 15 '11 at 13:04
@Ross, thanks. but is there formal mathematics reasoning? – didxga Jul 15 '11 at 13:11
@didxga: I would start with the fact that you need 27 in total value, must have 3 1's, and have shown you can do it with 12 coins. Also you can't have 4 5's (as no transaction can use 2). There aren't many cases left, so just check them all. Clearly I missed one. – Ross Millikan Jul 15 '11 at 13:28

If I understand the problem, I suspect you can get away with just 5 2s, not 6.

-
+1 This is why it is a good puzzle. – Ross Millikan Jul 17 '11 at 4:45