1
$\begingroup$

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?

  • 1
    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).2011-07-15

2 Answers 2

1

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.

  • 0
    @Gerry Sorry I missed a 1.2011-07-15
1

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