How many ways to make change for a Dollar?
Don Detweiler
which essentially turned into a challenge in tedium.
The question was simple enough: How many different ways are there to
make change for a dollar.
Presuming that we could use a silver dollar, half dollars, quarters,
dimes, nickels, and pennies, we counted 547 different ways to make change
for a dollar. Of course teachers workbook answer was off by a few
hundred.
Is there any mathematical formula that could be used to definitively
determine the correct answer?
Don
David Karr
>My fourth grade child recently came home with a "math challenge" problem,
>which essentially turned into a challenge in tedium.
Hmm. You can do a lot better than the tedious way, but I wouldn't
expect a fourth grader to think of it; I wonder what the purpose of
this exercise was.
>Presuming that we could use a silver dollar, half dollars, quarters,
>dimes, nickels, and pennies, we counted 547 different ways to make change
>for a dollar. Of course teachers workbook answer was off by a few
>hundred.
I get 292 ways, or 293 if you count giving a dollar back (albeit a
dollar coin) as "giving change."
I don't count different orders in which you can give the same coins.
So a half dollar and two quarters are the same as two quarters and a
half dollar.
>Is there any mathematical formula that could be used to definitively
>determine the correct answer?
I don't know a complete formula, but there are simple formulas
for the small change:
10n cents can be made in (n + 1)^2 ways using only pennies, nickels,
and dimes.
10n + 5 cents can be made in (n + 1)*(n + 2) ways using only
pennies, nickels, and dimes.
Now combine this with quarters and half-dollars:
A dollar using only quarters and half-dollars: total 3 ways
75 cents in quarters and half-dollars (2 ways)
and 25 cents in small change (12 ways): total 24 ways
50 cents in quarters and half-dollars (2 ways)
and 50 cents in small change (36 ways): total 72 ways
1 quarter, and 75 cents in small change (72 ways): 72 ways
100 cents in small change (121 ways): 121 ways
Add them all up, the total is 292.
-- David A. Karr (ka...@cs.cornell.edu)
Tom Turcich
<detw...@world.std.com> wrote:
> My fourth grade child recently came home with a "math challenge" problem,
> which essentially turned into a challenge in tedium.
>
> The question was simple enough: How many different ways are there to
> make change for a dollar.
>
> Presuming that we could use a silver dollar, half dollars, quarters,
> dimes, nickels, and pennies, we counted 547 different ways to make change
> for a dollar. Of course teachers workbook answer was off by a few
> hundred.
>
> Is there any mathematical formula that could be used to definitively
> determine the correct answer?
>
> Don
I don't have an answer for you but I remember being fascinated by this
puzzle in about the fourth grade (I'm 50 now). I lived in NYC and subway
tokens were so well accepted as change that we also had a $.15 coin in our
version of the puzzle. I remember getting my dadto save cigarette packs
(Marlboro Box) for me and I saved up a different way to change a dollar in
each box. Made for a full dresser drawer and a two year hobby that had me
out doing odd jobs to get another buck to save.
No puzzle value -- just nostalgia.
--
As a matter of fact - I do speak for the company
Tom Turcich
TATCOM, Macintosh consulting in the Houston area since 1988
Voice (713) 597-9596 FAX (713) 597-9597
Matthew A Blum
>Don Detweiler <detw...@world.std.com> writes:
>>Presuming that we could use a silver dollar, half dollars, quarters,
>>dimes, nickels, and pennies, we counted 547 different ways to make change
>>for a dollar. Of course teachers workbook answer was off by a few
>>hundred.
>Try this one:
>Using your choice of dollars, half-dollars, quarters, dimes, nickels
>and pennies, what is the smallest number of coins for which there is
>no combination totalling exactly one dollar?
>Here's a start:
>1 coin = 1 silver dollar
>2 coins = 2 half-dollars
>3 coins = 1 half-dollar and 2 quarters
>4 coins = 4 quarters
>5 coins = 1 half-dollar, 1 quarter, 2 dimes, and 1 nickel
6 coins = 1 half-dollar, 1 quarter, 1 dimes, 3 nickels
7 coins = 1 half-dollar, 1 quarter, 5 nickels
8 coins = 3 quarters, 5 nickels
9 coins = impossible!
It's easy enough to get 6-8 without any trouble, by realizing that as
long as there's at least one coin in the previous combination that can
be split into two coins (i.e, dime, half-dollar), you can make the
next one easily.
However, once we reach 8 coins, we only have quarters and nickels,
neither of which can be split into only two coins.
--Matt
Larry Troxler
>d012...@dcfreenet.seflin.lib.fl.us (Mike Taylor) writes:
>>Here's a start:
>--Matt
9 coins = 1 Quarter, 7 dimes, 1 nickel
Larry
l...@cloud9.net
Mike Taylor
>Presuming that we could use a silver dollar, half dollars, quarters,
>dimes, nickels, and pennies, we counted 547 different ways to make change
>for a dollar. Of course teachers workbook answer was off by a few
>hundred.
Try this one:
Using your choice of dollars, half-dollars, quarters, dimes, nickels
and pennies, what is the smallest number of coins for which there is
no combination totalling exactly one dollar?
Here's a start:
1 coin = 1 silver dollar
2 coins = 2 half-dollars
3 coins = 1 half-dollar and 2 quarters
4 coins = 4 quarters
5 coins = 1 half-dollar, 1 quarter, 2 dimes, and 1 nickel
...
Mike Taylor
--
(No email please.)
Matthew A Blum
>Here's a start:
Please *disregard* my previous follow to this post.
I forgot that 9 coins is possible:
1 half-dollar, 1 quarter, 2 dimes, 5 pennies
In fact, thinking about it, I'm not at all sure what the lowest number
is, only that it isn't particularly low.
If I have time later, I'll work on it.
In the meantime, please don't email me about my previous post.
--Matt
Timothy E Vaughan
>>Presuming that we could use a silver dollar, half dollars, quarters,
>>dimes, nickels, and pennies, we counted 547 different ways to make change
>>for a dollar. Of course teachers workbook answer was off by a few
>>hundred.
I got 343 ways. I tried briefly to find a clever method, but I found that
brute-force counting (with shorthand notation) to be OK. I am willing to
check your list, but not to type in mine!
Cheers,
Tim
David Karr
Apparently you have at least 50 duplicates in your list. Check the
"brute force" list below (generated by computer), and see if there
are any entries in your list that aren't on my list. Note that I
always list the biggest coins first: H = half dollar, Q = quarter,
D = dime, N = nickel, and P = penny.
1 dollar
2H
1H, 2Q
1H, 1Q, 2D, 1N
1H, 1Q, 2D, 5P
1H, 1Q, 1D, 3N
1H, 1Q, 1D, 2N, 5P
1H, 1Q, 1D, 1N, 10P
1H, 1Q, 1D, 15P
1H, 1Q, 5N
1H, 1Q, 4N, 5P
1H, 1Q, 3N, 10P
1H, 1Q, 2N, 15P
1H, 1Q, 1N, 20P
1H, 1Q, 25P
1H, 5D
1H, 4D, 2N
1H, 4D, 1N, 5P
1H, 4D, 10P
1H, 3D, 4N
1H, 3D, 3N, 5P
1H, 3D, 2N, 10P
1H, 3D, 1N, 15P
1H, 3D, 20P
1H, 2D, 6N
1H, 2D, 5N, 5P
1H, 2D, 4N, 10P
1H, 2D, 3N, 15P
1H, 2D, 2N, 20P
1H, 2D, 1N, 25P
1H, 2D, 30P
1H, 1D, 8N
1H, 1D, 7N, 5P
1H, 1D, 6N, 10P
1H, 1D, 5N, 15P
1H, 1D, 4N, 20P
1H, 1D, 3N, 25P
1H, 1D, 2N, 30P
1H, 1D, 1N, 35P
1H, 1D, 40P
1H, 10N
1H, 9N, 5P
1H, 8N, 10P
1H, 7N, 15P
1H, 6N, 20P
1H, 5N, 25P
1H, 4N, 30P
1H, 3N, 35P
1H, 2N, 40P
1H, 1N, 45P
1H, 50P
4Q
3Q, 2D, 1N
3Q, 2D, 5P
3Q, 1D, 3N
3Q, 1D, 2N, 5P
3Q, 1D, 1N, 10P
3Q, 1D, 15P
3Q, 5N
3Q, 4N, 5P
3Q, 3N, 10P
3Q, 2N, 15P
3Q, 1N, 20P
3Q, 25P
2Q, 5D
2Q, 4D, 2N
2Q, 4D, 1N, 5P
2Q, 4D, 10P
2Q, 3D, 4N
2Q, 3D, 3N, 5P
2Q, 3D, 2N, 10P
2Q, 3D, 1N, 15P
2Q, 3D, 20P
2Q, 2D, 6N
2Q, 2D, 5N, 5P
2Q, 2D, 4N, 10P
2Q, 2D, 3N, 15P
2Q, 2D, 2N, 20P
2Q, 2D, 1N, 25P
2Q, 2D, 30P
2Q, 1D, 8N
2Q, 1D, 7N, 5P
2Q, 1D, 6N, 10P
2Q, 1D, 5N, 15P
2Q, 1D, 4N, 20P
2Q, 1D, 3N, 25P
2Q, 1D, 2N, 30P
2Q, 1D, 1N, 35P
2Q, 1D, 40P
2Q, 10N
2Q, 9N, 5P
2Q, 8N, 10P
2Q, 7N, 15P
2Q, 6N, 20P
2Q, 5N, 25P
2Q, 4N, 30P
2Q, 3N, 35P
2Q, 2N, 40P
2Q, 1N, 45P
2Q, 50P
1Q, 7D, 1N
1Q, 7D, 5P
1Q, 6D, 3N
1Q, 6D, 2N, 5P
1Q, 6D, 1N, 10P
1Q, 6D, 15P
1Q, 5D, 5N
1Q, 5D, 4N, 5P
1Q, 5D, 3N, 10P
1Q, 5D, 2N, 15P
1Q, 5D, 1N, 20P
1Q, 5D, 25P
1Q, 4D, 7N
1Q, 4D, 6N, 5P
1Q, 4D, 5N, 10P
1Q, 4D, 4N, 15P
1Q, 4D, 3N, 20P
1Q, 4D, 2N, 25P
1Q, 4D, 1N, 30P
1Q, 4D, 35P
1Q, 3D, 9N
1Q, 3D, 8N, 5P
1Q, 3D, 7N, 10P
1Q, 3D, 6N, 15P
1Q, 3D, 5N, 20P
1Q, 3D, 4N, 25P
1Q, 3D, 3N, 30P
1Q, 3D, 2N, 35P
1Q, 3D, 1N, 40P
1Q, 3D, 45P
1Q, 2D, 11N
1Q, 2D, 10N, 5P
1Q, 2D, 9N, 10P
1Q, 2D, 8N, 15P
1Q, 2D, 7N, 20P
1Q, 2D, 6N, 25P
1Q, 2D, 5N, 30P
1Q, 2D, 4N, 35P
1Q, 2D, 3N, 40P
1Q, 2D, 2N, 45P
1Q, 2D, 1N, 50P
1Q, 2D, 55P
1Q, 1D, 13N
1Q, 1D, 12N, 5P
1Q, 1D, 11N, 10P
1Q, 1D, 10N, 15P
1Q, 1D, 9N, 20P
1Q, 1D, 8N, 25P
1Q, 1D, 7N, 30P
1Q, 1D, 6N, 35P
1Q, 1D, 5N, 40P
1Q, 1D, 4N, 45P
1Q, 1D, 3N, 50P
1Q, 1D, 2N, 55P
1Q, 1D, 1N, 60P
1Q, 1D, 65P
1Q, 15N
1Q, 14N, 5P
1Q, 13N, 10P
1Q, 12N, 15P
1Q, 11N, 20P
1Q, 10N, 25P
1Q, 9N, 30P
1Q, 8N, 35P
1Q, 7N, 40P
1Q, 6N, 45P
1Q, 5N, 50P
1Q, 4N, 55P
1Q, 3N, 60P
1Q, 2N, 65P
1Q, 1N, 70P
1Q, 75P
10D
9D, 2N
9D, 1N, 5P
9D, 10P
8D, 4N
8D, 3N, 5P
8D, 2N, 10P
8D, 1N, 15P
8D, 20P
7D, 6N
7D, 5N, 5P
7D, 4N, 10P
7D, 3N, 15P
7D, 2N, 20P
7D, 1N, 25P
7D, 30P
6D, 8N
6D, 7N, 5P
6D, 6N, 10P
6D, 5N, 15P
6D, 4N, 20P
6D, 3N, 25P
6D, 2N, 30P
6D, 1N, 35P
6D, 40P
5D, 10N
5D, 9N, 5P
5D, 8N, 10P
5D, 7N, 15P
5D, 6N, 20P
5D, 5N, 25P
5D, 4N, 30P
5D, 3N, 35P
5D, 2N, 40P
5D, 1N, 45P
5D, 50P
4D, 12N
4D, 11N, 5P
4D, 10N, 10P
4D, 9N, 15P
4D, 8N, 20P
4D, 7N, 25P
4D, 6N, 30P
4D, 5N, 35P
4D, 4N, 40P
4D, 3N, 45P
4D, 2N, 50P
4D, 1N, 55P
4D, 60P
3D, 14N
3D, 13N, 5P
3D, 12N, 10P
3D, 11N, 15P
3D, 10N, 20P
3D, 9N, 25P
3D, 8N, 30P
3D, 7N, 35P
3D, 6N, 40P
3D, 5N, 45P
3D, 4N, 50P
3D, 3N, 55P
3D, 2N, 60P
3D, 1N, 65P
3D, 70P
2D, 16N
2D, 15N, 5P
2D, 14N, 10P
2D, 13N, 15P
2D, 12N, 20P
2D, 11N, 25P
2D, 10N, 30P
2D, 9N, 35P
2D, 8N, 40P
2D, 7N, 45P
2D, 6N, 50P
2D, 5N, 55P
2D, 4N, 60P
2D, 3N, 65P
2D, 2N, 70P
2D, 1N, 75P
2D, 80P
1D, 18N
1D, 17N, 5P
1D, 16N, 10P
1D, 15N, 15P
1D, 14N, 20P
1D, 13N, 25P
1D, 12N, 30P
1D, 11N, 35P
1D, 10N, 40P
1D, 9N, 45P
1D, 8N, 50P
1D, 7N, 55P
1D, 6N, 60P
1D, 5N, 65P
1D, 4N, 70P
1D, 3N, 75P
1D, 2N, 80P
1D, 1N, 85P
1D, 90P
20N
19N, 5P
18N, 10P
17N, 15P
16N, 20P
15N, 25P
14N, 30P
13N, 35P
12N, 40P
11N, 45P
10N, 50P
9N, 55P
8N, 60P
7N, 65P
6N, 70P
5N, 75P
4N, 80P
3N, 85P
2N, 90P
1N, 95P
100P
Here's the Standard ML program I used to generate the list:
val coins = [100, 50, 25, 10, 5, 1] ;
val symbols = [" dollar", "H", "Q", "D", "N", "P"] ;
fun printcoins (sym::rest) 0 prev = printcoins rest 1 sym
| printcoins (sym::rest) n prev =
let
fun purgeif sym prev n =
if sym = prev then
n + 1
else
(print ((makestring n)^prev^", ");
1)
in
printcoins rest (purgeif sym prev n) sym
end
| printcoins [] n prev = print ((makestring n)^prev^"\n");
;
fun g coins symbols used total =
if total < 0 then
()
else
case (coins, symbols, total) of
(first::coins1, sym::symbols1, total) =>
(g coins symbols (sym::used) (total - first);
g coins1 symbols1 used total)
| ([], [], 0) => printcoins (rev used) 0 "none"
| ([], [], _) => ()
| _ => raise Tl
;
fun allchange total = g coins symbols [] total ;
-- David A. Karr (ka...@cs.cornell.edu)
-- <URL:http://www.cs.cornell.edu/Info/People/karr/home.html>
Mark Cramer
>>Don Detweiler <detw...@world.std.com> writes:
>>>Presuming that we could use a silver dollar, half dollars, quarters,
>>>dimes, nickels, and pennies, we counted 547 different ways to make change
>>>for a dollar. Of course teachers workbook answer was off by a few
>>>hundred.
>>Try this one:
>>Using your choice of dollars, half-dollars, quarters, dimes, nickels
>>and pennies, what is the smallest number of coins for which there is
>>no combination totalling exactly one dollar?
>In fact, thinking about it, I'm not at all sure what the lowest number
>is, only that it isn't particularly low.
>If I have time later, I'll work on it.
I worked on it, the minumum number of coins you can't use is 77 and the
maximum number of ways you can make a dollar with n coins is 9 ways with 15 or
19 coins. Using the above denominations (1,5,10,25,50 and 100 cents) I get
293 ways of making change for a dollar, (for 76 coins use 70 pennies and 6
nickels).
The 9 ways with 15 coins are;
50 25 10 5 1
5 10
9 1 5
1 1 13
1 5 4 5
2 1 7 5
3 1 1 5
1 9 5
1 4 10
1 1 3 10
>In the meantime, please don't email me about my previous post.
OK, I'll post instead.
>--Matt
+-----------------------------------------------+
| Mark Cramer. Network Supervisor. | /\_|\ |
| CBE Deptmnt, Queensland University | / QUT>\ |
| of Technology, Qld. Australia. | ( __ | |
| M.Cr...@Qut.Edu.Au Ph. 07 38642073| -- \/ |
| Intl Ph Code 617 Fax 07 38641525| v |
+-----------------------------------------------+
Stephen H. Landrum
>
> My fourth grade child recently came home with a "math challenge" problem,
> which essentially turned into a challenge in tedium.
>
> make change for a dollar.
>
> Presuming that we could use a silver dollar, half dollars, quarters,
> dimes, nickels, and pennies, we counted 547 different ways to make change
> for a dollar. Of course teachers workbook answer was off by a few
> hundred.
Well, I certainly don't get 547. I get 293.
> Is there any mathematical formula that could be used to definitively
> determine the correct answer?
You don't have to enumerate every single case.
You can break it into patterns, and notice some equations that develop.
For instance, the number of ways that pennies and nickles can be used
to make change for 5n cents is n+1. So, you have 21 ways that you can
make change for a dollar with pennies and nickels, 19 ways with one
dime and pennies and nickels, 17 ways with two dimes and pennies
and nickels, and so one.
When you break it down, and notice some more patterns, there really
aren't that many different cases to count.
--
Stephen H. Landrum voice: (415)261-2626 email: slan...@3do.com
System software programmer, M2 graphics division.
For general 3DO questions email customer...@3do.com
Mark Cramer
tvau...@athena.mit.edu (Timothy E Vaughan) wrote:
>Don Detweiler <detw...@world.std.com> writes:
>>>Presuming that we could use a silver dollar, half dollars, quarters,
>>>dimes, nickels, and pennies, we counted 547 different ways to make change
>>>for a dollar. Of course teachers workbook answer was off by a few
>>>hundred.
>I got 343 ways. I tried briefly to find a clever method, but I found that
>brute-force counting (with shorthand notation) to be OK. I am willing to
>check your list, but not to type in mine!
>Cheers,
>Tim
And I got 293, and I did mine on the computer so, someone wanna compare my
list with their's? The 293'rd entry is a $1
Cnt 1 0 ( 50 ) 0 ( 25 ) 0 ( 10 ) 0 ( 5 ) 100 ( 1 )
Cnt 2 0 ( 50 ) 0 ( 25 ) 0 ( 10 ) 1 ( 5 ) 95 ( 1 )
Cnt 3 0 ( 50 ) 0 ( 25 ) 0 ( 10 ) 2 ( 5 ) 90 ( 1 )
Cnt 4 0 ( 50 ) 0 ( 25 ) 0 ( 10 ) 3 ( 5 ) 85 ( 1 )
Cnt 5 0 ( 50 ) 0 ( 25 ) 0 ( 10 ) 4 ( 5 ) 80 ( 1 )
Cnt 6 0 ( 50 ) 0 ( 25 ) 0 ( 10 ) 5 ( 5 ) 75 ( 1 )
Cnt 7 0 ( 50 ) 0 ( 25 ) 0 ( 10 ) 6 ( 5 ) 70 ( 1 )
Cnt 8 0 ( 50 ) 0 ( 25 ) 0 ( 10 ) 7 ( 5 ) 65 ( 1 )
Cnt 9 0 ( 50 ) 0 ( 25 ) 0 ( 10 ) 8 ( 5 ) 60 ( 1 )
Cnt 10 0 ( 50 ) 0 ( 25 ) 0 ( 10 ) 9 ( 5 ) 55 ( 1 )
Cnt 11 0 ( 50 ) 0 ( 25 ) 0 ( 10 ) 10 ( 5 ) 50 ( 1 )
Cnt 12 0 ( 50 ) 0 ( 25 ) 0 ( 10 ) 11 ( 5 ) 45 ( 1 )
Cnt 13 0 ( 50 ) 0 ( 25 ) 0 ( 10 ) 12 ( 5 ) 40 ( 1 )
Cnt 14 0 ( 50 ) 0 ( 25 ) 0 ( 10 ) 13 ( 5 ) 35 ( 1 )
Cnt 15 0 ( 50 ) 0 ( 25 ) 0 ( 10 ) 14 ( 5 ) 30 ( 1 )
Cnt 16 0 ( 50 ) 0 ( 25 ) 0 ( 10 ) 15 ( 5 ) 25 ( 1 )
Cnt 17 0 ( 50 ) 0 ( 25 ) 0 ( 10 ) 16 ( 5 ) 20 ( 1 )
Cnt 18 0 ( 50 ) 0 ( 25 ) 0 ( 10 ) 17 ( 5 ) 15 ( 1 )
Cnt 19 0 ( 50 ) 0 ( 25 ) 0 ( 10 ) 18 ( 5 ) 10 ( 1 )
Cnt 20 0 ( 50 ) 0 ( 25 ) 0 ( 10 ) 19 ( 5 ) 5 ( 1 )
Cnt 21 0 ( 50 ) 0 ( 25 ) 0 ( 10 ) 20 ( 5 ) 0 ( 1 )
Cnt 22 0 ( 50 ) 0 ( 25 ) 1 ( 10 ) 0 ( 5 ) 90 ( 1 )
Cnt 23 0 ( 50 ) 0 ( 25 ) 1 ( 10 ) 1 ( 5 ) 85 ( 1 )
Cnt 24 0 ( 50 ) 0 ( 25 ) 1 ( 10 ) 2 ( 5 ) 80 ( 1 )
Cnt 25 0 ( 50 ) 0 ( 25 ) 1 ( 10 ) 3 ( 5 ) 75 ( 1 )
Cnt 26 0 ( 50 ) 0 ( 25 ) 1 ( 10 ) 4 ( 5 ) 70 ( 1 )
Cnt 27 0 ( 50 ) 0 ( 25 ) 1 ( 10 ) 5 ( 5 ) 65 ( 1 )
Cnt 28 0 ( 50 ) 0 ( 25 ) 1 ( 10 ) 6 ( 5 ) 60 ( 1 )
Cnt 29 0 ( 50 ) 0 ( 25 ) 1 ( 10 ) 7 ( 5 ) 55 ( 1 )
Cnt 30 0 ( 50 ) 0 ( 25 ) 1 ( 10 ) 8 ( 5 ) 50 ( 1 )
Cnt 31 0 ( 50 ) 0 ( 25 ) 1 ( 10 ) 9 ( 5 ) 45 ( 1 )
Cnt 32 0 ( 50 ) 0 ( 25 ) 1 ( 10 ) 10 ( 5 ) 40 ( 1 )
Cnt 33 0 ( 50 ) 0 ( 25 ) 1 ( 10 ) 11 ( 5 ) 35 ( 1 )
Cnt 34 0 ( 50 ) 0 ( 25 ) 1 ( 10 ) 12 ( 5 ) 30 ( 1 )
Cnt 35 0 ( 50 ) 0 ( 25 ) 1 ( 10 ) 13 ( 5 ) 25 ( 1 )
Cnt 36 0 ( 50 ) 0 ( 25 ) 1 ( 10 ) 14 ( 5 ) 20 ( 1 )
Cnt 37 0 ( 50 ) 0 ( 25 ) 1 ( 10 ) 15 ( 5 ) 15 ( 1 )
Cnt 38 0 ( 50 ) 0 ( 25 ) 1 ( 10 ) 16 ( 5 ) 10 ( 1 )
Cnt 39 0 ( 50 ) 0 ( 25 ) 1 ( 10 ) 17 ( 5 ) 5 ( 1 )
Cnt 40 0 ( 50 ) 0 ( 25 ) 1 ( 10 ) 18 ( 5 ) 0 ( 1 )
Cnt 41 0 ( 50 ) 0 ( 25 ) 2 ( 10 ) 0 ( 5 ) 80 ( 1 )
Cnt 42 0 ( 50 ) 0 ( 25 ) 2 ( 10 ) 1 ( 5 ) 75 ( 1 )
Cnt 43 0 ( 50 ) 0 ( 25 ) 2 ( 10 ) 2 ( 5 ) 70 ( 1 )
Cnt 44 0 ( 50 ) 0 ( 25 ) 2 ( 10 ) 3 ( 5 ) 65 ( 1 )
Cnt 45 0 ( 50 ) 0 ( 25 ) 2 ( 10 ) 4 ( 5 ) 60 ( 1 )
Cnt 46 0 ( 50 ) 0 ( 25 ) 2 ( 10 ) 5 ( 5 ) 55 ( 1 )
Cnt 47 0 ( 50 ) 0 ( 25 ) 2 ( 10 ) 6 ( 5 ) 50 ( 1 )
Cnt 48 0 ( 50 ) 0 ( 25 ) 2 ( 10 ) 7 ( 5 ) 45 ( 1 )
Cnt 49 0 ( 50 ) 0 ( 25 ) 2 ( 10 ) 8 ( 5 ) 40 ( 1 )
Cnt 50 0 ( 50 ) 0 ( 25 ) 2 ( 10 ) 9 ( 5 ) 35 ( 1 )
Cnt 51 0 ( 50 ) 0 ( 25 ) 2 ( 10 ) 10 ( 5 ) 30 ( 1 )
Cnt 52 0 ( 50 ) 0 ( 25 ) 2 ( 10 ) 11 ( 5 ) 25 ( 1 )
Cnt 53 0 ( 50 ) 0 ( 25 ) 2 ( 10 ) 12 ( 5 ) 20 ( 1 )
Cnt 54 0 ( 50 ) 0 ( 25 ) 2 ( 10 ) 13 ( 5 ) 15 ( 1 )
Cnt 55 0 ( 50 ) 0 ( 25 ) 2 ( 10 ) 14 ( 5 ) 10 ( 1 )
Cnt 56 0 ( 50 ) 0 ( 25 ) 2 ( 10 ) 15 ( 5 ) 5 ( 1 )
Cnt 57 0 ( 50 ) 0 ( 25 ) 2 ( 10 ) 16 ( 5 ) 0 ( 1 )
Cnt 58 0 ( 50 ) 0 ( 25 ) 3 ( 10 ) 0 ( 5 ) 70 ( 1 )
Cnt 59 0 ( 50 ) 0 ( 25 ) 3 ( 10 ) 1 ( 5 ) 65 ( 1 )
Cnt 60 0 ( 50 ) 0 ( 25 ) 3 ( 10 ) 2 ( 5 ) 60 ( 1 )
Cnt 61 0 ( 50 ) 0 ( 25 ) 3 ( 10 ) 3 ( 5 ) 55 ( 1 )
Cnt 62 0 ( 50 ) 0 ( 25 ) 3 ( 10 ) 4 ( 5 ) 50 ( 1 )
Cnt 63 0 ( 50 ) 0 ( 25 ) 3 ( 10 ) 5 ( 5 ) 45 ( 1 )
Cnt 64 0 ( 50 ) 0 ( 25 ) 3 ( 10 ) 6 ( 5 ) 40 ( 1 )
Cnt 65 0 ( 50 ) 0 ( 25 ) 3 ( 10 ) 7 ( 5 ) 35 ( 1 )
Cnt 66 0 ( 50 ) 0 ( 25 ) 3 ( 10 ) 8 ( 5 ) 30 ( 1 )
Cnt 67 0 ( 50 ) 0 ( 25 ) 3 ( 10 ) 9 ( 5 ) 25 ( 1 )
Cnt 68 0 ( 50 ) 0 ( 25 ) 3 ( 10 ) 10 ( 5 ) 20 ( 1 )
Cnt 69 0 ( 50 ) 0 ( 25 ) 3 ( 10 ) 11 ( 5 ) 15 ( 1 )
Cnt 70 0 ( 50 ) 0 ( 25 ) 3 ( 10 ) 12 ( 5 ) 10 ( 1 )
Cnt 71 0 ( 50 ) 0 ( 25 ) 3 ( 10 ) 13 ( 5 ) 5 ( 1 )
Cnt 72 0 ( 50 ) 0 ( 25 ) 3 ( 10 ) 14 ( 5 ) 0 ( 1 )
Cnt 73 0 ( 50 ) 0 ( 25 ) 4 ( 10 ) 0 ( 5 ) 60 ( 1 )
Cnt 74 0 ( 50 ) 0 ( 25 ) 4 ( 10 ) 1 ( 5 ) 55 ( 1 )
Cnt 75 0 ( 50 ) 0 ( 25 ) 4 ( 10 ) 2 ( 5 ) 50 ( 1 )
Cnt 76 0 ( 50 ) 0 ( 25 ) 4 ( 10 ) 3 ( 5 ) 45 ( 1 )
Cnt 77 0 ( 50 ) 0 ( 25 ) 4 ( 10 ) 4 ( 5 ) 40 ( 1 )
Cnt 78 0 ( 50 ) 0 ( 25 ) 4 ( 10 ) 5 ( 5 ) 35 ( 1 )
Cnt 79 0 ( 50 ) 0 ( 25 ) 4 ( 10 ) 6 ( 5 ) 30 ( 1 )
Cnt 80 0 ( 50 ) 0 ( 25 ) 4 ( 10 ) 7 ( 5 ) 25 ( 1 )
Cnt 81 0 ( 50 ) 0 ( 25 ) 4 ( 10 ) 8 ( 5 ) 20 ( 1 )
Cnt 82 0 ( 50 ) 0 ( 25 ) 4 ( 10 ) 9 ( 5 ) 15 ( 1 )
Cnt 83 0 ( 50 ) 0 ( 25 ) 4 ( 10 ) 10 ( 5 ) 10 ( 1 )
Cnt 84 0 ( 50 ) 0 ( 25 ) 4 ( 10 ) 11 ( 5 ) 5 ( 1 )
Cnt 85 0 ( 50 ) 0 ( 25 ) 4 ( 10 ) 12 ( 5 ) 0 ( 1 )
Cnt 86 0 ( 50 ) 0 ( 25 ) 5 ( 10 ) 0 ( 5 ) 50 ( 1 )
Cnt 87 0 ( 50 ) 0 ( 25 ) 5 ( 10 ) 1 ( 5 ) 45 ( 1 )
Cnt 88 0 ( 50 ) 0 ( 25 ) 5 ( 10 ) 2 ( 5 ) 40 ( 1 )
Cnt 89 0 ( 50 ) 0 ( 25 ) 5 ( 10 ) 3 ( 5 ) 35 ( 1 )
Cnt 90 0 ( 50 ) 0 ( 25 ) 5 ( 10 ) 4 ( 5 ) 30 ( 1 )
Cnt 91 0 ( 50 ) 0 ( 25 ) 5 ( 10 ) 5 ( 5 ) 25 ( 1 )
Cnt 92 0 ( 50 ) 0 ( 25 ) 5 ( 10 ) 6 ( 5 ) 20 ( 1 )
Cnt 93 0 ( 50 ) 0 ( 25 ) 5 ( 10 ) 7 ( 5 ) 15 ( 1 )
Cnt 94 0 ( 50 ) 0 ( 25 ) 5 ( 10 ) 8 ( 5 ) 10 ( 1 )
Cnt 95 0 ( 50 ) 0 ( 25 ) 5 ( 10 ) 9 ( 5 ) 5 ( 1 )
Cnt 96 0 ( 50 ) 0 ( 25 ) 5 ( 10 ) 10 ( 5 ) 0 ( 1 )
Cnt 97 0 ( 50 ) 0 ( 25 ) 6 ( 10 ) 0 ( 5 ) 40 ( 1 )
Cnt 98 0 ( 50 ) 0 ( 25 ) 6 ( 10 ) 1 ( 5 ) 35 ( 1 )
Cnt 99 0 ( 50 ) 0 ( 25 ) 6 ( 10 ) 2 ( 5 ) 30 ( 1 )
Cnt 100 0 ( 50 ) 0 ( 25 ) 6 ( 10 ) 3 ( 5 ) 25 ( 1 )
Cnt 101 0 ( 50 ) 0 ( 25 ) 6 ( 10 ) 4 ( 5 ) 20 ( 1 )
Cnt 102 0 ( 50 ) 0 ( 25 ) 6 ( 10 ) 5 ( 5 ) 15 ( 1 )
Cnt 103 0 ( 50 ) 0 ( 25 ) 6 ( 10 ) 6 ( 5 ) 10 ( 1 )
Cnt 104 0 ( 50 ) 0 ( 25 ) 6 ( 10 ) 7 ( 5 ) 5 ( 1 )
Cnt 105 0 ( 50 ) 0 ( 25 ) 6 ( 10 ) 8 ( 5 ) 0 ( 1 )
Cnt 106 0 ( 50 ) 0 ( 25 ) 7 ( 10 ) 0 ( 5 ) 30 ( 1 )
Cnt 107 0 ( 50 ) 0 ( 25 ) 7 ( 10 ) 1 ( 5 ) 25 ( 1 )
Cnt 108 0 ( 50 ) 0 ( 25 ) 7 ( 10 ) 2 ( 5 ) 20 ( 1 )
Cnt 109 0 ( 50 ) 0 ( 25 ) 7 ( 10 ) 3 ( 5 ) 15 ( 1 )
Cnt 110 0 ( 50 ) 0 ( 25 ) 7 ( 10 ) 4 ( 5 ) 10 ( 1 )
Cnt 111 0 ( 50 ) 0 ( 25 ) 7 ( 10 ) 5 ( 5 ) 5 ( 1 )
Cnt 112 0 ( 50 ) 0 ( 25 ) 7 ( 10 ) 6 ( 5 ) 0 ( 1 )
Cnt 113 0 ( 50 ) 0 ( 25 ) 8 ( 10 ) 0 ( 5 ) 20 ( 1 )
Cnt 114 0 ( 50 ) 0 ( 25 ) 8 ( 10 ) 1 ( 5 ) 15 ( 1 )
Cnt 115 0 ( 50 ) 0 ( 25 ) 8 ( 10 ) 2 ( 5 ) 10 ( 1 )
Cnt 116 0 ( 50 ) 0 ( 25 ) 8 ( 10 ) 3 ( 5 ) 5 ( 1 )
Cnt 117 0 ( 50 ) 0 ( 25 ) 8 ( 10 ) 4 ( 5 ) 0 ( 1 )
Cnt 118 0 ( 50 ) 0 ( 25 ) 9 ( 10 ) 0 ( 5 ) 10 ( 1 )
Cnt 119 0 ( 50 ) 0 ( 25 ) 9 ( 10 ) 1 ( 5 ) 5 ( 1 )
Cnt 120 0 ( 50 ) 0 ( 25 ) 9 ( 10 ) 2 ( 5 ) 0 ( 1 )
Cnt 121 0 ( 50 ) 0 ( 25 ) 10 ( 10 ) 0 ( 5 ) 0 ( 1 )
Cnt 122 0 ( 50 ) 1 ( 25 ) 0 ( 10 ) 0 ( 5 ) 75 ( 1 )
Cnt 123 0 ( 50 ) 1 ( 25 ) 0 ( 10 ) 1 ( 5 ) 70 ( 1 )
Cnt 124 0 ( 50 ) 1 ( 25 ) 0 ( 10 ) 2 ( 5 ) 65 ( 1 )
Cnt 125 0 ( 50 ) 1 ( 25 ) 0 ( 10 ) 3 ( 5 ) 60 ( 1 )
Cnt 126 0 ( 50 ) 1 ( 25 ) 0 ( 10 ) 4 ( 5 ) 55 ( 1 )
Cnt 127 0 ( 50 ) 1 ( 25 ) 0 ( 10 ) 5 ( 5 ) 50 ( 1 )
Cnt 128 0 ( 50 ) 1 ( 25 ) 0 ( 10 ) 6 ( 5 ) 45 ( 1 )
Cnt 129 0 ( 50 ) 1 ( 25 ) 0 ( 10 ) 7 ( 5 ) 40 ( 1 )
Cnt 130 0 ( 50 ) 1 ( 25 ) 0 ( 10 ) 8 ( 5 ) 35 ( 1 )
Cnt 131 0 ( 50 ) 1 ( 25 ) 0 ( 10 ) 9 ( 5 ) 30 ( 1 )
Cnt 132 0 ( 50 ) 1 ( 25 ) 0 ( 10 ) 10 ( 5 ) 25 ( 1 )
Cnt 133 0 ( 50 ) 1 ( 25 ) 0 ( 10 ) 11 ( 5 ) 20 ( 1 )
Cnt 134 0 ( 50 ) 1 ( 25 ) 0 ( 10 ) 12 ( 5 ) 15 ( 1 )
Cnt 135 0 ( 50 ) 1 ( 25 ) 0 ( 10 ) 13 ( 5 ) 10 ( 1 )
Cnt 136 0 ( 50 ) 1 ( 25 ) 0 ( 10 ) 14 ( 5 ) 5 ( 1 )
Cnt 137 0 ( 50 ) 1 ( 25 ) 0 ( 10 ) 15 ( 5 ) 0 ( 1 )
Cnt 138 0 ( 50 ) 1 ( 25 ) 1 ( 10 ) 0 ( 5 ) 65 ( 1 )
Cnt 139 0 ( 50 ) 1 ( 25 ) 1 ( 10 ) 1 ( 5 ) 60 ( 1 )
Cnt 140 0 ( 50 ) 1 ( 25 ) 1 ( 10 ) 2 ( 5 ) 55 ( 1 )
Cnt 141 0 ( 50 ) 1 ( 25 ) 1 ( 10 ) 3 ( 5 ) 50 ( 1 )
Cnt 142 0 ( 50 ) 1 ( 25 ) 1 ( 10 ) 4 ( 5 ) 45 ( 1 )
Cnt 143 0 ( 50 ) 1 ( 25 ) 1 ( 10 ) 5 ( 5 ) 40 ( 1 )
Cnt 144 0 ( 50 ) 1 ( 25 ) 1 ( 10 ) 6 ( 5 ) 35 ( 1 )
Cnt 145 0 ( 50 ) 1 ( 25 ) 1 ( 10 ) 7 ( 5 ) 30 ( 1 )
Cnt 146 0 ( 50 ) 1 ( 25 ) 1 ( 10 ) 8 ( 5 ) 25 ( 1 )
Cnt 147 0 ( 50 ) 1 ( 25 ) 1 ( 10 ) 9 ( 5 ) 20 ( 1 )
Cnt 148 0 ( 50 ) 1 ( 25 ) 1 ( 10 ) 10 ( 5 ) 15 ( 1 )
Cnt 149 0 ( 50 ) 1 ( 25 ) 1 ( 10 ) 11 ( 5 ) 10 ( 1 )
Cnt 150 0 ( 50 ) 1 ( 25 ) 1 ( 10 ) 12 ( 5 ) 5 ( 1 )
Cnt 151 0 ( 50 ) 1 ( 25 ) 1 ( 10 ) 13 ( 5 ) 0 ( 1 )
Cnt 152 0 ( 50 ) 1 ( 25 ) 2 ( 10 ) 0 ( 5 ) 55 ( 1 )
Cnt 153 0 ( 50 ) 1 ( 25 ) 2 ( 10 ) 1 ( 5 ) 50 ( 1 )
Cnt 154 0 ( 50 ) 1 ( 25 ) 2 ( 10 ) 2 ( 5 ) 45 ( 1 )
Cnt 155 0 ( 50 ) 1 ( 25 ) 2 ( 10 ) 3 ( 5 ) 40 ( 1 )
Cnt 156 0 ( 50 ) 1 ( 25 ) 2 ( 10 ) 4 ( 5 ) 35 ( 1 )
Cnt 157 0 ( 50 ) 1 ( 25 ) 2 ( 10 ) 5 ( 5 ) 30 ( 1 )
Cnt 158 0 ( 50 ) 1 ( 25 ) 2 ( 10 ) 6 ( 5 ) 25 ( 1 )
Cnt 159 0 ( 50 ) 1 ( 25 ) 2 ( 10 ) 7 ( 5 ) 20 ( 1 )
Cnt 160 0 ( 50 ) 1 ( 25 ) 2 ( 10 ) 8 ( 5 ) 15 ( 1 )
Cnt 161 0 ( 50 ) 1 ( 25 ) 2 ( 10 ) 9 ( 5 ) 10 ( 1 )
Cnt 162 0 ( 50 ) 1 ( 25 ) 2 ( 10 ) 10 ( 5 ) 5 ( 1 )
Cnt 163 0 ( 50 ) 1 ( 25 ) 2 ( 10 ) 11 ( 5 ) 0 ( 1 )
Cnt 164 0 ( 50 ) 1 ( 25 ) 3 ( 10 ) 0 ( 5 ) 45 ( 1 )
Cnt 165 0 ( 50 ) 1 ( 25 ) 3 ( 10 ) 1 ( 5 ) 40 ( 1 )
Cnt 166 0 ( 50 ) 1 ( 25 ) 3 ( 10 ) 2 ( 5 ) 35 ( 1 )
Cnt 167 0 ( 50 ) 1 ( 25 ) 3 ( 10 ) 3 ( 5 ) 30 ( 1 )
Cnt 168 0 ( 50 ) 1 ( 25 ) 3 ( 10 ) 4 ( 5 ) 25 ( 1 )
Cnt 169 0 ( 50 ) 1 ( 25 ) 3 ( 10 ) 5 ( 5 ) 20 ( 1 )
Cnt 170 0 ( 50 ) 1 ( 25 ) 3 ( 10 ) 6 ( 5 ) 15 ( 1 )
Cnt 171 0 ( 50 ) 1 ( 25 ) 3 ( 10 ) 7 ( 5 ) 10 ( 1 )
Cnt 172 0 ( 50 ) 1 ( 25 ) 3 ( 10 ) 8 ( 5 ) 5 ( 1 )
Cnt 173 0 ( 50 ) 1 ( 25 ) 3 ( 10 ) 9 ( 5 ) 0 ( 1 )
Cnt 174 0 ( 50 ) 1 ( 25 ) 4 ( 10 ) 0 ( 5 ) 35 ( 1 )
Cnt 175 0 ( 50 ) 1 ( 25 ) 4 ( 10 ) 1 ( 5 ) 30 ( 1 )
Cnt 176 0 ( 50 ) 1 ( 25 ) 4 ( 10 ) 2 ( 5 ) 25 ( 1 )
Cnt 177 0 ( 50 ) 1 ( 25 ) 4 ( 10 ) 3 ( 5 ) 20 ( 1 )
Cnt 178 0 ( 50 ) 1 ( 25 ) 4 ( 10 ) 4 ( 5 ) 15 ( 1 )
Cnt 179 0 ( 50 ) 1 ( 25 ) 4 ( 10 ) 5 ( 5 ) 10 ( 1 )
Cnt 180 0 ( 50 ) 1 ( 25 ) 4 ( 10 ) 6 ( 5 ) 5 ( 1 )
Cnt 181 0 ( 50 ) 1 ( 25 ) 4 ( 10 ) 7 ( 5 ) 0 ( 1 )
Cnt 182 0 ( 50 ) 1 ( 25 ) 5 ( 10 ) 0 ( 5 ) 25 ( 1 )
Cnt 183 0 ( 50 ) 1 ( 25 ) 5 ( 10 ) 1 ( 5 ) 20 ( 1 )
Cnt 184 0 ( 50 ) 1 ( 25 ) 5 ( 10 ) 2 ( 5 ) 15 ( 1 )
Cnt 185 0 ( 50 ) 1 ( 25 ) 5 ( 10 ) 3 ( 5 ) 10 ( 1 )
Cnt 186 0 ( 50 ) 1 ( 25 ) 5 ( 10 ) 4 ( 5 ) 5 ( 1 )
Cnt 187 0 ( 50 ) 1 ( 25 ) 5 ( 10 ) 5 ( 5 ) 0 ( 1 )
Cnt 188 0 ( 50 ) 1 ( 25 ) 6 ( 10 ) 0 ( 5 ) 15 ( 1 )
Cnt 189 0 ( 50 ) 1 ( 25 ) 6 ( 10 ) 1 ( 5 ) 10 ( 1 )
Cnt 190 0 ( 50 ) 1 ( 25 ) 6 ( 10 ) 2 ( 5 ) 5 ( 1 )
Cnt 191 0 ( 50 ) 1 ( 25 ) 6 ( 10 ) 3 ( 5 ) 0 ( 1 )
Cnt 192 0 ( 50 ) 1 ( 25 ) 7 ( 10 ) 0 ( 5 ) 5 ( 1 )
Cnt 193 0 ( 50 ) 1 ( 25 ) 7 ( 10 ) 1 ( 5 ) 0 ( 1 )
Cnt 194 0 ( 50 ) 2 ( 25 ) 0 ( 10 ) 0 ( 5 ) 50 ( 1 )
Cnt 195 0 ( 50 ) 2 ( 25 ) 0 ( 10 ) 1 ( 5 ) 45 ( 1 )
Cnt 196 0 ( 50 ) 2 ( 25 ) 0 ( 10 ) 2 ( 5 ) 40 ( 1 )
Cnt 197 0 ( 50 ) 2 ( 25 ) 0 ( 10 ) 3 ( 5 ) 35 ( 1 )
Cnt 198 0 ( 50 ) 2 ( 25 ) 0 ( 10 ) 4 ( 5 ) 30 ( 1 )
Cnt 199 0 ( 50 ) 2 ( 25 ) 0 ( 10 ) 5 ( 5 ) 25 ( 1 )
Cnt 200 0 ( 50 ) 2 ( 25 ) 0 ( 10 ) 6 ( 5 ) 20 ( 1 )
Cnt 201 0 ( 50 ) 2 ( 25 ) 0 ( 10 ) 7 ( 5 ) 15 ( 1 )
Cnt 202 0 ( 50 ) 2 ( 25 ) 0 ( 10 ) 8 ( 5 ) 10 ( 1 )
Cnt 203 0 ( 50 ) 2 ( 25 ) 0 ( 10 ) 9 ( 5 ) 5 ( 1 )
Cnt 204 0 ( 50 ) 2 ( 25 ) 0 ( 10 ) 10 ( 5 ) 0 ( 1 )
Cnt 205 0 ( 50 ) 2 ( 25 ) 1 ( 10 ) 0 ( 5 ) 40 ( 1 )
Cnt 206 0 ( 50 ) 2 ( 25 ) 1 ( 10 ) 1 ( 5 ) 35 ( 1 )
Cnt 207 0 ( 50 ) 2 ( 25 ) 1 ( 10 ) 2 ( 5 ) 30 ( 1 )
Cnt 208 0 ( 50 ) 2 ( 25 ) 1 ( 10 ) 3 ( 5 ) 25 ( 1 )
Cnt 209 0 ( 50 ) 2 ( 25 ) 1 ( 10 ) 4 ( 5 ) 20 ( 1 )
Cnt 210 0 ( 50 ) 2 ( 25 ) 1 ( 10 ) 5 ( 5 ) 15 ( 1 )
Cnt 211 0 ( 50 ) 2 ( 25 ) 1 ( 10 ) 6 ( 5 ) 10 ( 1 )
Cnt 212 0 ( 50 ) 2 ( 25 ) 1 ( 10 ) 7 ( 5 ) 5 ( 1 )
Cnt 213 0 ( 50 ) 2 ( 25 ) 1 ( 10 ) 8 ( 5 ) 0 ( 1 )
Cnt 214 0 ( 50 ) 2 ( 25 ) 2 ( 10 ) 0 ( 5 ) 30 ( 1 )
Cnt 215 0 ( 50 ) 2 ( 25 ) 2 ( 10 ) 1 ( 5 ) 25 ( 1 )
Cnt 216 0 ( 50 ) 2 ( 25 ) 2 ( 10 ) 2 ( 5 ) 20 ( 1 )
Cnt 217 0 ( 50 ) 2 ( 25 ) 2 ( 10 ) 3 ( 5 ) 15 ( 1 )
Cnt 218 0 ( 50 ) 2 ( 25 ) 2 ( 10 ) 4 ( 5 ) 10 ( 1 )
Cnt 219 0 ( 50 ) 2 ( 25 ) 2 ( 10 ) 5 ( 5 ) 5 ( 1 )
Cnt 220 0 ( 50 ) 2 ( 25 ) 2 ( 10 ) 6 ( 5 ) 0 ( 1 )
Cnt 221 0 ( 50 ) 2 ( 25 ) 3 ( 10 ) 0 ( 5 ) 20 ( 1 )
Cnt 222 0 ( 50 ) 2 ( 25 ) 3 ( 10 ) 1 ( 5 ) 15 ( 1 )
Cnt 223 0 ( 50 ) 2 ( 25 ) 3 ( 10 ) 2 ( 5 ) 10 ( 1 )
Cnt 224 0 ( 50 ) 2 ( 25 ) 3 ( 10 ) 3 ( 5 ) 5 ( 1 )
Cnt 225 0 ( 50 ) 2 ( 25 ) 3 ( 10 ) 4 ( 5 ) 0 ( 1 )
Cnt 226 0 ( 50 ) 2 ( 25 ) 4 ( 10 ) 0 ( 5 ) 10 ( 1 )
Cnt 227 0 ( 50 ) 2 ( 25 ) 4 ( 10 ) 1 ( 5 ) 5 ( 1 )
Cnt 228 0 ( 50 ) 2 ( 25 ) 4 ( 10 ) 2 ( 5 ) 0 ( 1 )
Cnt 229 0 ( 50 ) 2 ( 25 ) 5 ( 10 ) 0 ( 5 ) 0 ( 1 )
Cnt 230 0 ( 50 ) 3 ( 25 ) 0 ( 10 ) 0 ( 5 ) 25 ( 1 )
Cnt 231 0 ( 50 ) 3 ( 25 ) 0 ( 10 ) 1 ( 5 ) 20 ( 1 )
Cnt 232 0 ( 50 ) 3 ( 25 ) 0 ( 10 ) 2 ( 5 ) 15 ( 1 )
Cnt 233 0 ( 50 ) 3 ( 25 ) 0 ( 10 ) 3 ( 5 ) 10 ( 1 )
Cnt 234 0 ( 50 ) 3 ( 25 ) 0 ( 10 ) 4 ( 5 ) 5 ( 1 )
Cnt 235 0 ( 50 ) 3 ( 25 ) 0 ( 10 ) 5 ( 5 ) 0 ( 1 )
Cnt 236 0 ( 50 ) 3 ( 25 ) 1 ( 10 ) 0 ( 5 ) 15 ( 1 )
Cnt 237 0 ( 50 ) 3 ( 25 ) 1 ( 10 ) 1 ( 5 ) 10 ( 1 )
Cnt 238 0 ( 50 ) 3 ( 25 ) 1 ( 10 ) 2 ( 5 ) 5 ( 1 )
Cnt 239 0 ( 50 ) 3 ( 25 ) 1 ( 10 ) 3 ( 5 ) 0 ( 1 )
Cnt 240 0 ( 50 ) 3 ( 25 ) 2 ( 10 ) 0 ( 5 ) 5 ( 1 )
Cnt 241 0 ( 50 ) 3 ( 25 ) 2 ( 10 ) 1 ( 5 ) 0 ( 1 )
Cnt 242 0 ( 50 ) 4 ( 25 ) 0 ( 10 ) 0 ( 5 ) 0 ( 1 )
Cnt 243 1 ( 50 ) 0 ( 25 ) 0 ( 10 ) 0 ( 5 ) 50 ( 1 )
Cnt 244 1 ( 50 ) 0 ( 25 ) 0 ( 10 ) 1 ( 5 ) 45 ( 1 )
Cnt 245 1 ( 50 ) 0 ( 25 ) 0 ( 10 ) 2 ( 5 ) 40 ( 1 )
Cnt 246 1 ( 50 ) 0 ( 25 ) 0 ( 10 ) 3 ( 5 ) 35 ( 1 )
Cnt 247 1 ( 50 ) 0 ( 25 ) 0 ( 10 ) 4 ( 5 ) 30 ( 1 )
Cnt 248 1 ( 50 ) 0 ( 25 ) 0 ( 10 ) 5 ( 5 ) 25 ( 1 )
Cnt 249 1 ( 50 ) 0 ( 25 ) 0 ( 10 ) 6 ( 5 ) 20 ( 1 )
Cnt 250 1 ( 50 ) 0 ( 25 ) 0 ( 10 ) 7 ( 5 ) 15 ( 1 )
Cnt 251 1 ( 50 ) 0 ( 25 ) 0 ( 10 ) 8 ( 5 ) 10 ( 1 )
Cnt 252 1 ( 50 ) 0 ( 25 ) 0 ( 10 ) 9 ( 5 ) 5 ( 1 )
Cnt 253 1 ( 50 ) 0 ( 25 ) 0 ( 10 ) 10 ( 5 ) 0 ( 1 )
Cnt 254 1 ( 50 ) 0 ( 25 ) 1 ( 10 ) 0 ( 5 ) 40 ( 1 )
Cnt 255 1 ( 50 ) 0 ( 25 ) 1 ( 10 ) 1 ( 5 ) 35 ( 1 )
Cnt 256 1 ( 50 ) 0 ( 25 ) 1 ( 10 ) 2 ( 5 ) 30 ( 1 )
Cnt 257 1 ( 50 ) 0 ( 25 ) 1 ( 10 ) 3 ( 5 ) 25 ( 1 )
Cnt 258 1 ( 50 ) 0 ( 25 ) 1 ( 10 ) 4 ( 5 ) 20 ( 1 )
Cnt 259 1 ( 50 ) 0 ( 25 ) 1 ( 10 ) 5 ( 5 ) 15 ( 1 )
Cnt 260 1 ( 50 ) 0 ( 25 ) 1 ( 10 ) 6 ( 5 ) 10 ( 1 )
Cnt 261 1 ( 50 ) 0 ( 25 ) 1 ( 10 ) 7 ( 5 ) 5 ( 1 )
Cnt 262 1 ( 50 ) 0 ( 25 ) 1 ( 10 ) 8 ( 5 ) 0 ( 1 )
Cnt 263 1 ( 50 ) 0 ( 25 ) 2 ( 10 ) 0 ( 5 ) 30 ( 1 )
Cnt 264 1 ( 50 ) 0 ( 25 ) 2 ( 10 ) 1 ( 5 ) 25 ( 1 )
Cnt 265 1 ( 50 ) 0 ( 25 ) 2 ( 10 ) 2 ( 5 ) 20 ( 1 )
Cnt 266 1 ( 50 ) 0 ( 25 ) 2 ( 10 ) 3 ( 5 ) 15 ( 1 )
Cnt 267 1 ( 50 ) 0 ( 25 ) 2 ( 10 ) 4 ( 5 ) 10 ( 1 )
Cnt 268 1 ( 50 ) 0 ( 25 ) 2 ( 10 ) 5 ( 5 ) 5 ( 1 )
Cnt 269 1 ( 50 ) 0 ( 25 ) 2 ( 10 ) 6 ( 5 ) 0 ( 1 )
Cnt 270 1 ( 50 ) 0 ( 25 ) 3 ( 10 ) 0 ( 5 ) 20 ( 1 )
Cnt 271 1 ( 50 ) 0 ( 25 ) 3 ( 10 ) 1 ( 5 ) 15 ( 1 )
Cnt 272 1 ( 50 ) 0 ( 25 ) 3 ( 10 ) 2 ( 5 ) 10 ( 1 )
Cnt 273 1 ( 50 ) 0 ( 25 ) 3 ( 10 ) 3 ( 5 ) 5 ( 1 )
Cnt 274 1 ( 50 ) 0 ( 25 ) 3 ( 10 ) 4 ( 5 ) 0 ( 1 )
Cnt 275 1 ( 50 ) 0 ( 25 ) 4 ( 10 ) 0 ( 5 ) 10 ( 1 )
Cnt 276 1 ( 50 ) 0 ( 25 ) 4 ( 10 ) 1 ( 5 ) 5 ( 1 )
Cnt 277 1 ( 50 ) 0 ( 25 ) 4 ( 10 ) 2 ( 5 ) 0 ( 1 )
Cnt 278 1 ( 50 ) 0 ( 25 ) 5 ( 10 ) 0 ( 5 ) 0 ( 1 )
Cnt 279 1 ( 50 ) 1 ( 25 ) 0 ( 10 ) 0 ( 5 ) 25 ( 1 )
Cnt 280 1 ( 50 ) 1 ( 25 ) 0 ( 10 ) 1 ( 5 ) 20 ( 1 )
Cnt 281 1 ( 50 ) 1 ( 25 ) 0 ( 10 ) 2 ( 5 ) 15 ( 1 )
Cnt 282 1 ( 50 ) 1 ( 25 ) 0 ( 10 ) 3 ( 5 ) 10 ( 1 )
Cnt 283 1 ( 50 ) 1 ( 25 ) 0 ( 10 ) 4 ( 5 ) 5 ( 1 )
Cnt 284 1 ( 50 ) 1 ( 25 ) 0 ( 10 ) 5 ( 5 ) 0 ( 1 )
Cnt 285 1 ( 50 ) 1 ( 25 ) 1 ( 10 ) 0 ( 5 ) 15 ( 1 )
Cnt 286 1 ( 50 ) 1 ( 25 ) 1 ( 10 ) 1 ( 5 ) 10 ( 1 )
Cnt 287 1 ( 50 ) 1 ( 25 ) 1 ( 10 ) 2 ( 5 ) 5 ( 1 )
Cnt 288 1 ( 50 ) 1 ( 25 ) 1 ( 10 ) 3 ( 5 ) 0 ( 1 )
Cnt 289 1 ( 50 ) 1 ( 25 ) 2 ( 10 ) 0 ( 5 ) 5 ( 1 )
Cnt 290 1 ( 50 ) 1 ( 25 ) 2 ( 10 ) 1 ( 5 ) 0 ( 1 )
Cnt 291 1 ( 50 ) 2 ( 25 ) 0 ( 10 ) 0 ( 5 ) 0 ( 1 )
Cnt 292 2 ( 50 ) 0 ( 25 ) 0 ( 10 ) 0 ( 5 ) 0 ( 1 )
Tom Maciukenas
Matthew A Blum <mb...@world.std.com> wrote:
>I forgot that 9 coins is possible:
>
>1 half-dollar, 1 quarter, 2 dimes, 5 pennies
>
>is, only that it isn't particularly low.
Taking the exhaustive list of ways to make change for a dollar from David
Karr's post, doing a few vi manipulations, and running it through
cat ... | bc | sort -n -u
to add the number of coins in each line produced the following result:
You can make change using the following numbers of coins:
1-76, 78-80, 82-84, 87, 88, 91, 92, 96, 100
So the lowest number that's impossible is 77 coins.
-tOMM
Timothy E Vaughan
(David Karr) writes:
|> tvau...@athena.mit.edu (Timothy E Vaughan) writes:
|> >Don Detweiler <detw...@world.std.com> writes:
|> >
|> >>>Presuming that we could use a silver dollar, half dollars, quarters,
|> >>>dimes, nickels, and pennies, we counted 547 different ways to make change
|> >>>for a dollar. Of course teachers workbook answer was off by a few
|> >>>hundred.
|> >I got 343 ways. <snip>
|> Apparently you have at least 50 duplicates in your list.
<big snip>
Nope. It's worse! I don't know how to count! I double-checked
my list after Mark Cramer sent me his, and found that I had counted
one of my sheets twice accidentally.
293 is the right answer, found independently by at least three people
now. I wonder what the teacher's workbook said? 8-)
Tim
John McGowan
> In article <4a1u73$j...@senator-bedfellow.MIT.EDU>,
> tvau...@athena.mit.edu (Timothy E Vaughan) wrote:
> >Don Detweiler <detw...@world.std.com> writes:
> >>>Presuming that we could use a silver dollar, half dollars, quarters,
> >>>dimes, nickels, and pennies, we counted 547 different ways to make change
> >>>for a dollar. Of course teachers workbook answer was off by a few
> >>>hundred.
> >I got 343 ways. I tried briefly to find a clever method, but I found that
> >brute-force counting (with shorthand notation) to be OK. I am willing to
> >check your list, but not to type in mine!
> And I got 293, and I did mine on the computer so, someone wanna compare my
> list with their's? The 293'rd entry is a $1
293 (including the dollar itself) is correct. See the post in rec.puzzles
under the title "4th grade math puzzler" (the title under which the
original question was posted to sci.math... I used that title in the
cross post here and to sci.math though the original post here was under a
different title... which is why my answer with the programme and data for
the number of ways of paying out any amount from one cent through one
dollar did not appear in this thread).
Basically, one looks at the coefficient of x^100 in the power series
expansion of 1/[(1-x)(1-x^5)(1-x^10)(1-x^25)(1-x^50)(1-x^100)]
(can replace by the multiplication of the polynomials:
(1+x+x^2+x^3+x^4...+x^100)(1+x^5+x^10+x^15...+x^100)(1+x^10+x^20+x^30..+x^100)
*(1+x^25+x^50+x^75+x^100)(1+x^50+x^100)(1+x^100)
(pennies, nickels, dimes, quarters, half dollars, dollars) (the
polynomials suffice as the power series has other terms, but they
correspond to amounts greater than $1.00... the polynomials simply
restrict to the terms that might influence the x^100 term) which appears
to be 293.
--
John McGowan | jmcg...@inch.com [Internet Channel]
| jmcg...@mail.coin.missouri.edu [COIN]
--------------+-----------------------------------------------------
Patrik Lundin
: Don Detweiler <detw...@world.std.com> writes:
: >Presuming that we could use a silver dollar, half dollars, quarters,
: >dimes, nickels, and pennies, we counted 547 different ways to make change
: >for a dollar. Of course teachers workbook answer was off by a few
: >hundred.
: Try this one:
: Using your choice of dollars, half-dollars, quarters, dimes, nickels
: and pennies, what is the smallest number of coins for which there is
: no combination totalling exactly one dollar?
Well, a quick c prog gives me 77 coins as the first impossible one.
However, it only gives 292 combinations (which is way <547), so maybe
there is something wrong with it... Anyhow, I can't seem to catch it missing
any, so here it is...
--- begin change.c ---
int coins[]={100,50,25,10,5,1};
int didit;
main()
{
int no,us[6];
memset(&us,0,sizeof(us));
for(no=1;no<100;no++)
{
didit=0;
printf("%d coins:\n",no);
doit(0,&us,no);
if(!didit)
puts(" Impossible!");
}
}
int doit(a,u,no)
int a,*u,no;
{
int tot,used[6];
if(no<0) return;
used[0]=u[0]; used[1]=u[1]; used[2]=u[2];
used[3]=u[3]; used[4]=u[4]; used[5]=u[5];
tot=coins[0]*used[0]+coins[1]*used[1]+coins[2]*used[2]+
coins[3]*used[3]+coins[4]*used[4]+coins[5]*used[5];
if(tot>100)
return;
if(!no&&(tot==100))
{
printf(" ");
if(used[0]) printf("%d dollar%s ",used[0],used[0]>1?"s":"");
if(used[1]) printf("%d half-dollar%s ",used[1],used[1]>1?"s":"");
if(used[2]) printf("%d quater%s ",used[2],used[2]>1?"s":"");
if(used[3]) printf("%d dime%s ",used[3],used[3]>1?"s":"");
if(used[4]) printf("%d nickle%s ",used[4],used[4]>1?"s":"");
if(used[5]) printf("%d penn%s ",used[5],used[5]>1?"ies":"y");
puts("");
didit=1;
}
switch(a)
{
case 0: used[0]++; doit(0,&used,no-1); used[0]--;
case 1: used[1]++; doit(1,&used,no-1); used[1]--;
case 2: used[2]++; doit(2,&used,no-1); used[2]--;
case 3: used[3]++; doit(3,&used,no-1); used[3]--;
case 4: used[4]++; doit(4,&used,no-1); used[4]--;
case 5: used[5]++; doit(5,&used,no-1); used[5]--;
}
}
--- end ---
Feal free to comment by news or email if you see it misbehaving.
/PL
---
main(x,y/* Patrik Lundin | lun...@ludd.luth.se */){for(;x++;)
for(y=2/* Docentv. 28 | d94...@sm.luth.se */;x%y;)printf(
++y/x+/* 977 52 Luleaa | http://www.ludd.luth.se/~lundin */"\0%d\n",x);}
Dennis Yelle
>Mike Taylor (d012...@dcfreenet.seflin.lib.fl.us) wrote:
>: Don Detweiler <detw...@world.std.com> writes:
>: >Presuming that we could use a silver dollar, half dollars, quarters,
>: >dimes, nickels, and pennies, we counted 547 different ways to make change
>: >for a dollar. Of course teachers workbook answer was off by a few
>: >hundred.
>
>: Try this one:
>: Using your choice of dollars, half-dollars, quarters, dimes, nickels
>: and pennies, what is the smallest number of coins for which there is
>: no combination totalling exactly one dollar?
>
>Well, a quick c prog gives me 77 coins as the first impossible one.
>However, it only gives 292 combinations (which is way <547), so maybe
I think that others have claimed that 293 is the right answer,
see below for why.
>there is something wrong with it... Anyhow, I can't seem to catch it missing
>any, so here it is...
>
>--- begin change.c ---
>int coins[]={100,50,25,10,5,1};
>int didit;
>
>main()
>{
>int no,us[6];
>
>memset(&us,0,sizeof(us));
>
>for(no=1;no<100;no++)
This looks like it will miss exactly one case.
OB Puzzle: Which case will it miss?
--
den...@netcom.com (Dennis Yelle)
"You must do the thing you think you cannot do." -- Eleanor Roosevelt
Mark Ceulemans
1Dollar=100 won't de calculated.
--
____________________________________________________
' `
| Mark Ceulemans |
| |
| home: Spaarstraat 10 work: K.U.Leuven |
| 3010 Kessel-Lo Celestynenlaan 200F |
| Belgium 3001 Heverlee |
| Belgium |
| |
| tel: 016/35.34.50 016/32.73.93 |
| |
| E-Mail: Mark.Ce...@chem.kuleuven.ac.be |
| |
`____________________________________________________'