Skip to main content.

Solution to puzzle 12: Making $1

Suppose we have x coins, comprised of: a pennies, b nickels, c dimes, d quarters, e half dollars, and f dollars, with a, b, c, d, e, f greater than or equal to 0.

Then a + 5b + 10c + 25d + 50e + 100f = 100 and x = a + b + c + d + e + f.

Therefore 4b + 9c + 24d + 49e + 99f = 100 − x.

We seek the smallest value of x such that the above equation has no solution.
In other words, we seek the largest value of 100 − x with no solution.
That is, the largest value that cannot be obtained by substituting non-negative integers into 4b + 9c + 24d + 49e + 99f.

This is not as intractable, and it's quite easy to verify that 23 is the highest such value.  In particular, this approach simplifies the checking process for small values of x, i.e., for large numbers of coins.

Therefore the smallest number of coins with which it is impossible to make a dollar is 77.

Source: Traditional

Back to top