How many different ways can ten dollars be made from five dollar bills, one dollar bills, half-dollars, and...

combinatorics/coinage/ten.dollars New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

How many different ways can ten dollars be made from five dollar bills,
one dollar bills, half-dollars, and quarters?

[ Editor: posted by Mitesh P. Laconi <danconia@aol.com>. ]

Show solution

First consider the breakdowns into $5/$1/0.50, then consider that any
breakdown involving quarters can be derived by replacing at least one
0.50 with two quarters:

$5 + $5            -> 1
$5 + 5x$1          -> 1
$5 + 4x$1 + 2x0.50 -> 3 (2x0.50, 0.50+2x0.25, 4x0.25)
$5 + 3x$1 + 4x0.50 -> 5
$5 + 2x$1 + 6x0.50 -> 7
$5 +   $1 + 8x0.50 -> 9
$5         10x0.50 -> 11

Similarly, 10x$1 breaks down into 1+3+5+7+9+11+13+15+17+19+21 = 121,
which added to 1+1+3+5+7+9+11 = 37 gives us a total of 158 ways.

-- Ed Murphy <zvyezda@ix.netcom.com>