On Friday I posted this puzzle…..

How can you use 50 American coins to add up to a dollar? The coins available are a penny (1 cent), a nickel (5 cents), a dime (10 cents), a quarter (25 cents), and a half-dollar (50 cents).

If you have not tried to solve it, have a go now.  For everyone else, the answer is after the break.
You need to use is 40 pennies, 8 nickels (40 cents) and 2 dimes (20 cents).  Did you solve it? Any other answers?

I have produced an ebook containing 101 of the previous Friday Puzzles! It is called PUZZLED and is available for the Kindle (UK here and USA here) and on the iBookstore (UK here in the USA here). You can try 101 of the puzzles for free here.

1. I did solve it, but only through trial and error. Feels like there should be a tidy formula to reach the result

2. tibo says:

1 quarter, 2 dimes, 2 nickels and 45 pennies

1. Chris Emerson says:

I did this too

2. Julia says:

same

3. Anonymous says:

Same

Ed

4. Anonymous says:

Thank you, you saved me lots of time.

3. DiscoveredJoys says:

I hit the ‘official’ answer first. I realised that
a) the bulk of the coins had to be pennies to get the 50 coin total
b) the totals of odd coins had to add up to an even amount (pennies and quarters)
c) the pennies must be in multiples of 5
d) therefore the maximum number of pennies must be 45 and the minimum 40
e) half dollars were ‘too big’

and at least one answer then became simply selecting a total of 60 cents using 10 coins from nickels, dimes and quarters.

4. Eddie says:

It’s a bit crap of Richard not to give both answers. Not very rigorous, is it.

1. Calgacus says:

Some people are never happy.

2. Eddie says:

Is this a complaint?

5. Smylers says:

I wrote a quick Perl program to find all the ways of making \$1 out of those coins, then display just those which consist of 50 coins.

There’s hardly anything to the algorithm: most of it it just splitting it down into simpler cases that can be solved trivially — see the comments for details.

Running it finds both solutions:

\$ ./50_coins
50 coins: 45 × 1¢ + 2 × 10¢ + 1 × 25¢ + 2 × 5¢
50 coins: 40 × 1¢ + 2 × 10¢ + 8 × 5¢

Here’s the program, heavily commented:

#! /usr/bin/perl

# 50_coins
#
# Make \$1 out of 50 coins: https://richardwiseman.wordpress.com/blog-2/

use v5.10;
use warnings;
use strict;

use List::AllUtils qw;

# Find all the ways 100 can be broken down into the available coins:
foreach my \$count (breakdown(100, (50, 25, 10, 5, 1)))
{

# Count the total coins used, and display if there’s 50:
my \$coins = sum values %\$count;
say qq[\$coins coins: ],
join q[ + ], map { qq[\$count->{\$_} × \${_}¢] } sort keys %\$count
if \$coins == 50;
}

sub breakdown
# returns all the ways of making \$target using @coin values
{
my (\$target, @coin) = @_;

# If the target is zero, then we can make it (using no coins):
return {} if \$target == 0;

# Otherwise if there are no coins we can’t make anything:
return if !@coin;

# If the target has gone below zero then it’s impossible to do anything:
return if \$target < 0;

# If we reach this far then there's a non-zero target and some coins (well,
# at least one). Of the possible ways of making \$target, they either involve
# the first coin or they don't — for example ways of making \$1 can be split
# into those that use at least one 25¢ and those that don't use 25¢ at all.
# Work out each of those sets separately, and return the combined list.
#
# Use this function again to solve each of the smaller problems — which may
# in turn involve invoking it again, and so on, until it reaches one of the
# simple cases above. Avoid Perl worrying that it'll never end:
no warnings qw;

(

# The ways of making \$1 using at least one 25¢ coin is the same as adding
# one 25¢ coin to each of the ways of making 75¢ using those coins
# (including potentionally further 25¢ coins). So find all the ways of
# making that smaller target using the same coins, and add one count of the
# first coin into each of the breakdowns:
map { \$_->{\$coin[0]}++; \$_ } breakdown(\$target – \$coin[0], @coin)),

# The ways of making \$1 without using any 25¢ coins is just like that coin
# had never been included in the list of allowed coins in the first place.
# So find all the ways of making the same target but without using the
# first coin:
breakdown(\$target, @coin[1 .. \$#coin],
);
}

1. Calgacus says:

First prize for longest post of the day……so far.

6. Anders says:

I have heard a similar puzzle, have a go if you want: You have 100 dollars, and your task is to buy 100 animals. Exactly. the chickens costs 50 cents, the hens costs 3 dollars, and the rooster costs 10 dollars. You have to use all the money, and you have to buy at least one of each animal.

7. Sue McAllister says:

45 pennies 2 nickels 2 dimes 1 quarter

8. Anne Elk says:

I got the answer given (the one with three different kinds of coins) by trial and error, with a biro and a post-it note.
Someone on Friday mentioned solving this with two equations. I don’t know if this meant simultaneous equations, but if anyone could show me how I could have done it more ‘scientifically’ I’d be grateful.

9. foolonthehill says:

Without need for any code, the solution (coin initials for unknowns) fulfils
p+n+d+q+h=50 and p+5n+10d+25q+50h=100.
Eliminating the pennies leaves:
4n+9d+24q+49h=50.
Constraining to positive integers that sum to 50 in this way, we must have h=0, q={0,1}, d<=4 and n<=10.
It's easy enough to test with q=0 (4n+9d=50 only has solution n=8, d=2) and q=1 (4n+9d=26 only has solution n=2, d=2) so we have two answers: 40p, 8n, 2d, 0q, 0h and 45p, 2n, 2d, 1q, 0h

1. Anne Elk says:

Dear foolonthehill: That’s very kind of you. Thanks. I surprise myself by being able to follow your explanation. I must be getting better at this stuff.

10. foolonthehill says:

Ooops – obviously, that should say “we must have h=0, q={0,1}, d<=5 and n 50 and 4×13 > 50.
For completeness, the other step I missed is to say that q<=2, but for q=2, 4n+9d=2 has no solution, leaving just q={0,1}

I think that DiscoveredJoys identification that 'p' must be a multiple of 5 is interesting, and might lead to a simpler proof. Though as I don't use the pennies in mine, it would need another approach….

1. foolonthehill says:

Weird – now my reply has been mangled too. Let’s try again….
“we must have h=0, q={0,1}, d<=5 and n 50 and 4×13 > 50.”

2. Anne Elk says:

Ha ha. Obviously I’m _not_ getting better at this stuff in that case! I managed to understand it and you’d made a mistake! Thanks for the clarification. I’ll see if I can follow this one instead. Anne

11. foolonthehill says:

Nope. Still broken – it keeps removing a line of text! Last try:
“We must have h=0, q={0,1}, d less or equal to 5 and n less than or equal to 12.
This is simply because each term must be less than 50: 9 times 6 > 50 and 4 times 13 > 50.”

12. Séan Donnellan says:

45 pennies
2 Nickels
2 Dimes
1 Quarter

1. Anonymous says:

Is there another way

13. Scott says:

45 pennies, 2 nickels, 2 dimes, 1 quarter

14. foolonthehill says:

So, I think I can also formalise DiscoveredJoys theory a bit, by saying p=5x with 1 <= x <= 9:
n + d + q + h = 50-5x and 5n + 10d + 25q + 10h = 100-5x
Removing n this time, we get:
d + 4q + 10h = 4x – 30
but 4p-30 must be positive, so x={8,9} (hence pennies is 40 or 45 as DiscoveredJoys pointed out)
so, d + 4q + 10h = 2 or 6, and the two solutions follow…

15. ChrisR says:

I realised that the pennies must be a multiple of 5, but less than 50.
So 45 pennies leaves 5 coins to add up to 55.
Assuming I was on the right track, one must be a quarter leaving 4 coins for 30 cents and it dropped out from there. (I could have started again with 40 pennies but didn’t). I do like foolonthehill’s approach. (Apart from the typo about “4p – 30 must be positive” which should be “4x – 30” 🙂 )
And why can’t I type more than 3 lines into this box and see what I’m typing?

16. Anonymous says:

And some just over think-too much time on your hands.. Whew..

17. Mick says:

Got both 🙂

18. John says:

I approached it a bit differently. If you start with 50 pennies, you have the correct number of coins, but a 50 cent deficit. Keeping the number of coins constant, swapping out one of the pennies for a nickel raises the total value by 4 cents. A dime adds 9 cents, a quarter adds 24. Then the problem becomes a simpler matter of finding a way to add some number of 4s, 9s, and 24s together to add up to 50.

19. Jim says:

Not to be left out, but I was busy visiting my sick mother (really), so:

1 Quarter
2 Dimes
2 Nickels
45 Pennies

1. I did it like that too.

20. I used DiscoveredJoys approach, math sense, you might say. Too easy to pull out codes, formulas, etc.Took about 5 minutes.

21. I took about a minute or so to find the 40 + 8*5 + 2*10 solution, and then I just assumed there would be loads of other solutions. Then I was surprised to read comments on Friday from several people saying there were only 2 solutions, so I worked out the 45 + 2*5 + 2*10 + 25 solution as well.

I started with 100 1-cent coins, and repeatedly replaced groups of five with nickels until the number of coins got down to 50. I realised I needed to have dimes as well, otherwise the number of 1-cent coins wouldn’t fit.

22. issahamati says:

i did it

23. Very nice post. I just stumbled upon your weblog and
wanted to say that I’ve truly enjoyed browsing your blog posts. After all I will be subscribing to your rss feed and I hope you write again very soon!

24. This design is steller! You certainly know how to keep a reader entertained. Between your wit and your videos, I was almost moved to start my own blog (well, almost…HaHa!) Excellent job. I really enjoyed what you had to say, and more than that, how you presented it. Too cool!|

25. Anonymous says:

50 Philippine 1 peso coins

26. Anonymous says:

The only actual correct answer is 40 pennies, 2 dimes, 8 nickles, and 0 quarters.