25 Coins in a Dollar

Date: 08/16/2001 at 10:58:46
From: Sheila Williams
Subject: How to get a dollar using 25 coins.

My son's 6th grade teacher gave him a puzzle to try in the classroom 
and he was very discouraged when several of the students got the 
answer right away. His teacher told him to try it at home. The 
question was, "How can you get a dollar using 25 coins?"  

She told him that there were many different combinations but to find 
only five of them. 

Is it just trial and error or is there a formula that can be worked 
out like (ax1) + (bx5) + (cx10) + (dx25) = one dollar? 

Thank you.
Sheila Williams

Date: 08/16/2001 at 15:53:23
From: Doctor Rob
Subject: Re: How to get a dollar using 25 coins.

Thanks for writing to Ask Dr. Math, Sheila.

If you have Q quarters, D dimes, N nickels, and P pennies, then you
want nonnegative integer values of these variables that satisfy

   25*Q + 10*D + 5*N + P = 100  (total value of coins),
      Q +    D +   N + P =  25  (total number of coins).

Subtracting one from the other, you have

   24*Q + 9*D + 4*N = 75.

Since 3 is a divisor of 24, 9, and 75, it must be a divisor of N.
Put N = 3*X.  Then, substituting and dividing by 3, you get

   8*Q + 3*D + 4*X = 25 = 16 + 9.

Now since 8 and 4 and 16 are divisible by 4, 3*D - 9 = 3*(D-3) must 
also be divisible by 4. That means that D - 3 must be divisible by 4, 
so D = 4*Y + 3. Substituting, combining like terms, and dividing by 4, 
you get

   2*Q + 3*Y + X = 4.

Now you can explicitly write down all the nonnegative integer 
solutions to this equation, and then calculate the values of
D = 4*Y + 3, N = 3*X, and P = 25 - Q - D - N:

   Q   Y   X   D   N   P
   0   0   4   3  12  10
   1   0   2   3   6  15
   2   0   0   3   0  20
   0   1   1   7   3  15

You can always trade 1 quarter and 5 pennies for 6 nickels and vice 
versa, also 4 dimes and 5 pennies for 9 nickels.

That gives you four solutions. To get more than four, you need
half-dollars. Then if you have one half-dollar, the equations become

   25*Q + 10*D + 5*N + P = 50,
      Q +    D +   N + P = 24,
   24*Q +  9*D + 4*N     = 26 = 8 + 18.

Then 9*(D-2), and so D - 2, must be divisible by 4, so D must be of 
the form 4*Y + 2, so that

    6*Q + 9*Y + N = 2.

The only solution to this is Q = Y = 0, N = 2, so D = 2 and P = 20.  
This means one half-dollar, no quarters, two dimes, two nickels, and 
20 pennies.

You can always trade a half-dollar and 5 pennies for 5 dimes and a 
nickel. That is the fifth solution. There are only five.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/   

Date: 08/16/2001 at 18:20:19
From: Doctor Greenie
Subject: Re: How to get a dollar using 25 coins.
Hi, Sheila --

Dr. Rob has written a detailed response to your question, but while 
it's fine for a talented high school student, it may not help a 
6th-grader work through the problem.

Here is how I would do this problem with a 6th-grader:

There are two keys to my approach to this type of problem:

(*) Nickels, dimes, quarters, and half dollars together can only make 
total numbers of cents that are multiples of 5. If the total of 25 
coins is to be exactly  one dollar (100 cents), then the number of 
pennies must be a multiple of 5.

(**) With "n" coins, all of which are either nickels or dimes, you can 
make any total number of cents that is between 5n (all nickels) and 
10n (all dimes). For example, suppose you have 4 coins that are all 
either nickels or dimes. The smallest amount you can make happens if 
all four coins are nickels; the total is 20 cents. Now trade one of 
those nickels for a dime. You lose the 5 cents from the nickel and 
gain 10 cents from the dime, for a net gain of 5 cents, so now your 
total is 25 cents. Trade a second nickel for a second dime, and you 
increase your total amount by another 5 cents, to 30 cents. Trade a 
third nickel for a third dime and you have a total of 35 cents; and 
trade the last nickel for a dime and you have a total of 40 cents.

With (*) and (**) above in mind, the approach to solving a problem 
like this is the following:

(1) Choose a number of half dollars and/or quarters that keeps the 
total amount in half dollars and quarters under 100 cents.

(2) For each combination of numbers of half dollars and quarters, 
determine what numbers of pennies you can have (the number of pennies 
must be a multiple of 5; and the total number of coins among half 
dollars, quarters, and pennies must be less than 25).

(3) For each combination of half dollars, quarters, and pennies, 
determine the number of coins remaining to make 25 coins and the 
number of cents remaining to make 100 cents. According to (**) above, 
there is a solution to the problem using this combination of half 
dollars, quarters, and pennies if (and only if) the number of cents 
remaining to be made is between 5 and 10 times the number of coins 
remaining.

The process is much easier to use than it is to explain.  Here is the 
analysis for this particular problem that shows the five possible 
solutions.

                    # coins    # cents
  50c  25c   1c    remaining  remaining    solution?
 ---------------   --------------------    ------------------------

   1    1    20         3          5         no
   1    1    15         8         10         no
   1    1    10        13         15         no
   1    1     5        18         20         no
   1    1     0        23         25         no

   1    0    20         4         30        yes  (2 dimes, 2 nickels)
   1    0    15         9         35         no
   1    0    10        14         40         no
   1    0     5        19         45         no
   1    0     0        24         50         no

   0    3    20         2          5         no
   0    3    15         7         10         no
   0    3    10        12         15         no
   0    3     5        17         20         no
   0    3     0        22         25         no

   0    2    20         3         30        yes  (3 dimes)
   0    2    15         8         35         no
   0    2    10        13         40         no
   0    2     5        18         45         no
   0    2     0        23         50         no

   0    1    20         4         55         no
   0    1    15         9         60        yes  (3 dimes, 6 nickels)
   0    1    10        14         65         no
   0    1     5        19         70         no
   0    1     0        24         75         no

   0    0    20         5         80         no
   0    0    15        10         85        yes  (7 dimes, 3 nickels)
   0    0    10        15         90        yes  (3 dimes, 12 nickels)
   0    0     5        20         95         no
   0    0     0        25        100         no

- Doctor Greenie, The Math Forum
  http://mathforum.org/dr.math/