Question

In cents, what is the least total amount that cannot be obtained by using a combination of fewer than eight coins from a collection of pennies, nickels, dimes and quarters?

Answer 1

94 cents

Explanation:

Using eight coins, the maximum is
`2` dollars, so we need to find a value lower than that. If we imagine
`8` pennies, and add one to that, since we can make any value under
`8` cents, we will get
`9` cents. We can make this with a nickel, so we also need to be out of range of nickels, so we should try
`40+1`. We can make this with dimes, so we should try
`8\cdot10+1`.
`81` can be made with quarters, so we should try
`200+1` and get
`201` cents. But, we cannot forget about subtracting from these values. If we try
`40-1`, we get
`39`, which is made with dimes. Trying
`8\cdot10-1` makes
`79`, but if we keep moving it down to the nearest multiple of
`25`, or a quarter, we will get
`74`.
`74` can be made with
`8` coins though, but if we take it away again down to
`7\cdot10-1`, we get
`69`. This looks hopeful. This has
`2` quarters,
`1` dime,
`1` nickel, and four pennies. If we keep trying and move it down to
`64`, we can still make it. If we keep moving down till we get to the LCM of the values, we get
`50-1=49`. Making this does works, so now we know it is between
`75` cents and
`200` cents. Trying the nearest multiple of
`5` minus
`1`, we get
`79`. This obviously works, so we need to get away from the multiple of
`25`. Trying
`84`, we get
`3`,
`1`, and
`4` coin types, so this works. Now try
`89`. This is
`3` quarters,
`1` dime, and four pennies. Trying
`94`, we get
`3` quarters,
`1` dime,
`1` nickel, and four pennies.There is nothing lower than this, so we have found it! :D This took me very long to do, and even I learned something from doing your super hard question! Thanks for the workout!

EDIT: Oops! I did less than or equal to! But you can use the same logic to do it again!