Still the best...

[Kevin O'Gorman]

On Sat, Jun 22, 2002 at 07:41:58PM -0500, David A. Bandel wrote:
> On Sat, 22 Jun 2002 16:32:21 +0000
> begin  Terence McCarthy <saki.uk at ntlworld.com> spewed forth:
> 
> > On Sat, 22 Jun 2002 10:12:15 -0400
> > Bruce Marshall <bmarsh at bmarsh.com> wrote:
> > 
> > > "There are 293 ways to make change for a dollar."
> > 
> > Go on, list them.....
> 
> Actually, there's a lot more than that.
> 
> 4 quarters
> each quarter has 12 ways to make change for it, starting with 2 dimes and
> a nickel, 2 dimes and 5 pennies, then 1 dime and 4 different mixes of
> nickels and pennies, then all nickels, then mixes of nickels and pennies
> (3 more), then all pennies.
> 
> since each $0.25 can have 13 different values, you actually have 13^4
> (13*13*13*13), plus all dimes (not in the above mix anywhere).
> 
> So listing _only_ 293 should be a piece of cake.
> 
> Ciao,
> 
> David A. Bandel

Wow, David, that's the very first time I've caught you in a mistake!
Not that I'm particularly trying to do that, but your remarks just didn't
make sense.  You can't combine the different ways to change a quarter
that way; they're not independent.

In fact, I calculate (this the help of my local friendly Linux machine)
that there are exactly 240 ways to do it.  It's very simple to do; just
try 0-4 quarters, then 0 to some number of dimes (depending on how many
quarters), 0 to some number of nickels, and pennies to fill out the buck.
Here's what it looks like in Python:

#!/usr/bin/python
w = 0
for q in range(0,5):
    for d in range(0,10):
        if q*25+d*10>100: break
        for n in range (0,20):
            if q*25 + d*10 + n*5 > 100: break
            w = w + 1
            print \
   "%2.2d quarters, %2.2d dimes, %2.2d nickels, %3.3d pennies: %d ways" \
               % (q, d, n, 100- q*25 - d*10 - n*5, w)


The head and tail of the output look like this:


00 quarters, 00 dimes, 00 nickels, 100 pennies: 1 ways
00 quarters, 00 dimes, 01 nickels, 095 pennies: 2 ways
00 quarters, 00 dimes, 02 nickels, 090 pennies: 3 ways
00 quarters, 00 dimes, 03 nickels, 085 pennies: 4 ways
00 quarters, 00 dimes, 04 nickels, 080 pennies: 5 ways
00 quarters, 00 dimes, 05 nickels, 075 pennies: 6 ways
00 quarters, 00 dimes, 06 nickels, 070 pennies: 7 ways
00 quarters, 00 dimes, 07 nickels, 065 pennies: 8 ways
00 quarters, 00 dimes, 08 nickels, 060 pennies: 9 ways
00 quarters, 00 dimes, 09 nickels, 055 pennies: 10 ways



03 quarters, 00 dimes, 02 nickels, 015 pennies: 230 ways
03 quarters, 00 dimes, 03 nickels, 010 pennies: 231 ways
03 quarters, 00 dimes, 04 nickels, 005 pennies: 232 ways
03 quarters, 00 dimes, 05 nickels, 000 pennies: 233 ways
03 quarters, 01 dimes, 00 nickels, 015 pennies: 234 ways
03 quarters, 01 dimes, 01 nickels, 010 pennies: 235 ways
03 quarters, 01 dimes, 02 nickels, 005 pennies: 236 ways
03 quarters, 01 dimes, 03 nickels, 000 pennies: 237 ways
03 quarters, 02 dimes, 00 nickels, 005 pennies: 238 ways
03 quarters, 02 dimes, 01 nickels, 000 pennies: 239 ways
04 quarters, 00 dimes, 00 nickels, 000 pennies: 240 ways

I guess somebody needs to change their quotations.  :o)

++ kevin

-- 
Kevin O'Gorman  (805) 650-6274  mailto:kevin at kosmanor.com
Permanent e-mail f rwarder:  mailto:Kevin.O'Gorman.64 at Alum.Dartmouth.org
At school: mailto:kogorman at cs.ucsb.edu
Web: http://www.cs.ucsb.edu/~kogorman/index.html
Web: http://kosmanor.com/~kevin/index.html

"Life is short; eat dessert first!"