perplexus.info :: Just Math : A Change of Mind

A Change of Mind (Posted on 2003-06-18)

I went into the bank to get change for a dollar. The teller said, "How do you want the change, buddy? I mean, there are 292 ways involving pennies, nickels, dimes, quarters, and half-dollars to give change for a dollar!"

Since I didn't like her attitude, I didn't answer her question. I simply said, "Well, I certainly don't want any pennies."

How many ways are there for her to give me change now?

(Note: Americans, always shunning simplicity have chosen to name their coins in the following easy-to-remember manner: Penny=1 cent, Nickel=5 cents, Dime=10 cents, Quarter=25 cents, Half Dollar=50 cents)

Submitted by DJ

Rating: 4.4615 (13 votes)

Solution: (Hide)

There are four ways to make 25¢ without pennies: 5x5¢
3x5¢ + 1x10¢
1x5¢ + 2x10¢
1x25¢

To make fifty cents, you can either use one 50¢ piece, or take any combination of two of the above ways to make a quarter. The number of ways you can do this is 4C2, or 4+3+2+1=10, for a total of 11 ways to make fifty cents.

Similarly, to make a dollar (dollar coins were not included in the problem), it is necessary to take any combination of two of the above 11 ways to make 50¢. The number of ways this can be done is 11C2, or equal to 11+10+9+8+7+6+5+4+3+2+1=66.

However, these are not necessarily unique, due to the fact that the different combinations of different 25¢ values use more than one of the same coin.
Each of the 11 ways to make fifty cents is unique, but when a dollar is made by pairing these, the total number of each type of coin is the same for certain different arrangements.

There are actually 40 distinct ways to do this, which can be found systematically relatively easily (Charlie wrote a program here to find them all):
5*20 10*1 + 5*18 10*2 + 5*16 10*3 + 5*14 10*4 + 5*12 10*5 + 5*10 10*6 + 5*8 10*7 + 5*6 10*8 + 5*4 10*9 + 5*2 10*10 25*1 + 5*15 25*1 + 10*1 + 5*13 25*1 + 10*2 + 5*11 25*1 + 10*3 + 5*9 25*1 + 10*4 + 5*7 25*1 + 10*5 + 5*5 25*1 + 10*6 + 5*3 25*1 + 10*7 + 5*1 25*2 + 5*10 25*2 + 10*1 + 5*8 25*2 + 10*2 + 5*6 25*2 + 10*3 + 5*4 25*2 + 10*4 + 5*2 25*2 + 10*5 25*3 + 5*5 25*3 + 10*1 + 5*3 25*3 + 10*2 + 5*1 25*4 50*1 + 5*10 50*1 + 10*1 + 5*8 50*1 + 10*2 + 5*6 50*1 + 10*3 + 5*4 50*1 + 10*4 + 5*2 50*1 + 10*5 50*1 + 25*1 + 5*5 50*1 + 25*1 + 10*1 + 5*3 50*1 + 25*1 + 10*2 + 5*1 50*1 + 25*2 50*2
So far, however, no one has been able to explain why the number is exactly 40 (sorry!).

Comments: ( You must be logged in to post comments.)

Subject	Author	Date
re: Challenge Accepted (Solution)	Brian Smith	2022-10-22 16:27:45
Answer	K Sengupta	2008-10-29 00:00:12
just did it	Billy Bob	2004-03-31 21:53:40
Here is one take on this.	Dan Erickson	2003-08-23 05:01:05
re: Challenge	derek	2003-07-03 10:24:19
Challenge	DJ	2003-06-26 04:15:29
official soluiton	levik	2003-06-22 17:23:32
re: Solution (After all that)	Charlie	2003-06-20 08:55:20
The list	Charlie	2003-06-18 09:39:45
Solution	Jonny Doe	2003-06-18 08:00:46
Solution (After all that)	Lewis	2003-06-18 07:06:19
re: Nickel? (Never mind, I know now)	Lewis	2003-06-18 06:54:54
Nickel?	Lewis	2003-06-18 06:49:07

Please log in:

Login:
Password:
Remember me:

Sign up! \| Forgot password

Search:

Search body:

Forums (1)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (16)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info