# How to do the computation to find the number of coins in a chest if there are different denominations?

This problem has left me going in circles, since I don't know how to relate the number of coins and denominations to obtain a maximum quantity. Does this problem requires the use of derivatives?. If not, then how can I solve it?

The problem is as follows:

At a vending machine factory a group of technicians have been tasked to build a new beverages dispensing machine with an upgraded cash accepting system. This mechanism can accept coins of $$20$$ cents, $$50$$ cents and $$1$$ dollar, $$2$$ dollars and $$5$$ dollars. After the initial run, the vending machine collected a total of $$100$$ dollars. Assuming that in this currency all quantities stated are coins and $$100$$ cents is $$1$$ dollar. What is the maximum quantity of coins the machine can have in its money chest if at least the machine received five coins of each denomination?.

The alternatives given in my book are:

$$\begin{array}{ll} 1.&294\,\textrm{coins}\\ 2.&298\,\textrm{coins}\\ 3.&308\,\textrm{coins}\\ 4.&316\,\textrm{coins}\\ 5.&306\,\textrm{coins}\\ \end{array}$$

Normally I would try to show my attempt into solving this problem, but in this particular situation I don't know how to proceed from the very beginning.

The only thing I could come up with was to build a system of $$1\times 1$$ equation where it would be like this:

$$0.2\left(x+5\right)+0.5\left(x+5\right)+1\left(x+5\right)+5\left(x+5\right)=100$$

Therefore:

$$\left(x+5\right)\left(0.2+0.5+1+5\right)=100$$

$$\left(x+5\right)=\frac{100}{6.7}=\frac{1000}{67}$$

$$x=\frac{1000}{67}-5=\frac{5000-335}{67}=\frac{4665}{67}$$

Needless to say that my answer doesn't get any close of what the alternatives given are. Therefore I'm requesting assistance with this particular problem. What would be the method to choose or how can I solve this riddle?.

I'm often confused whether if derivatives should apply in this situation?. Can somebody help me with an answer for this?. Something which could help me a lot it is to know if there exist a graphical approach?.

## 1 Answer

You seem to have forgotten about the $$2$$ dollar coin. Since we know that there are at least five coins of each value, we can subtract:

$$5 \cdot (0.2 + 0.5 + 1 + 2 + 5) = 5 \cdot 8.7 = 43.5$$

We thus need to achieve the highest number of coins that achieve a sum of $$100 - 43.5 = 56.5$$. Most of the times, we can achieve this by assigning the lowest value first. Note that, had the remaining amount been a multiple of $$0.2$$, we could have simply divided this amount by $$0.2$$ to achieve the highest number of coins. However, since this is not the case, we first need to subtract one coin of $$0.5$$ to find us left with a total sum of $$56$$. As such, the maximum number of coins equals:

$$5 \cdot 5 + 1 + \frac{56}{0.2} = 306$$

• Yes. I'm sorry I forgot the $2$ coin as I was in a rush when I wrote my attempted solution. But I'm still stuck at trying to understand the reason behind using the $0.2$ quantity. So far what I can just think that for the machine to have the maximum number of coins happens when the denomination is the lowest one since it mentions that the machine has received at least five of each denomination. However how can be sure that ammount gives us the maximum number of coins?. Can't be more?. – Chris Steinbeck Bell Feb 14 '19 at 15:00
• You found $56$ which is divisible by $0.2$ but why we don't need to mind that is not divisible by $0.5$?. Could it be that the reason we mind about it is due the fact that to attain the maximum number of coins we are looking to get a quanitity whose divisibility is by the lowest denomination in this case $0.2$?. Is that the reason?. I'm sorry but I'm slow at catching up these things. I hope to be understanding well what you intended to explain in your answer. I'm still confused on the word at least from the problem. – Chris Steinbeck Bell Feb 14 '19 at 15:03
• @ChrisSteinbeckBell Since you know that the machine has received at least five coins of each value, we can discard the amount of \$43.5: we are certain these 25 coins are there. Then, we need to find the largest amount of coins which in total results in \$56.5. Had this amount been a multiple of \$0.2, we could have just used only these coins in order to maximize the total number of coins (they have the lowest value, after all). However, in this case, we must assign at least one coin \$0.5 (otherwise, we cannot obtain a sum of \$56.5). Then, we assign the remaining amount to the \$0.2 coins. – jvdhooft Feb 14 '19 at 15:07
• Because the way how it is mentioned gives me the impression that there can exist more than the coins you calculated. But I have to say that it makes sense to account the number of coins the problem says that there is at least plus the number of coins which one can get when use the lowest denomination possible and the coin subtracted so that the ammount is divisible by that number. I had to split my comments due there is limitation in the characters. Sorry. I hope you can help me to clear my doubts. – Chris Steinbeck Bell Feb 14 '19 at 15:08
• Okay!. :-) I understood the part you mentioned in the earlier comment. It seems to confirm what I thought was the intended explanation. So far I'm learning from your post that to maximize a quantity (in this case coins) I'd like to look for the lowest value so it will require as much to attain the requested ammount. Otherwise to minimize would be the contrary and choose the highest value right?. – Chris Steinbeck Bell Feb 14 '19 at 15:12