# Divide one dollar into 14 coins.

March 14, 2006 5:47 PM Subscribe

What's the easiest way to figure out this fourth-grade math question? Divide one dollar into 14 U.S. coins.

Trial and error would seem to be the fastest way. Configuring an equation would take much longer.

posted by billysumday at 5:51 PM on March 14, 2006

posted by billysumday at 5:51 PM on March 14, 2006

10 pennies, 1 nickel, 1 dime, 1 quarter, and 1 half dollar = $1

posted by keep it tight at 5:54 PM on March 14, 2006

posted by keep it tight at 5:54 PM on March 14, 2006

I just figured it out by working backwards, starting with the smallest denomination. Figure out if using one particular coin won't work no matter what. Then do trial and error, converging on the answer.

posted by deadfather at 5:54 PM on March 14, 2006

posted by deadfather at 5:54 PM on March 14, 2006

There's another answer besides keep it tight's.

posted by deadfather at 5:55 PM on March 14, 2006

posted by deadfather at 5:55 PM on March 14, 2006

I did it in 10 seconds just by dividing the dollar into dimes, then replacing as many dimes as needed with nickels to make the number 14 instead of 10 coins.

So 6 dimes and 8 nickels.

But if you want an equation, no idea.

posted by meerkatty at 5:55 PM on March 14, 2006

So 6 dimes and 8 nickels.

But if you want an equation, no idea.

posted by meerkatty at 5:55 PM on March 14, 2006

I don't think this sort of problem is presented so that you can come up with some sort of complex equation. I think, rather, it's to teach you to think quickly about how to make change, to prepare you for your thankless minimum-wage cashier job when you're in high school. :)

posted by jozxyqk at 5:57 PM on March 14, 2006

posted by jozxyqk at 5:57 PM on March 14, 2006

Response by poster: I was wondering if there was an equation to do this, but I guess, as billysumday said, trial and error is the easiest way.

posted by soiled cowboy at 5:58 PM on March 14, 2006

posted by soiled cowboy at 5:58 PM on March 14, 2006

One obvious rule is you are either going to use 0, 5, or 10 pennies.

I came up with:

5 pennies, 2 nickes, 6 dimes, 1 quarter

Basically trial and error.

posted by knave at 5:58 PM on March 14, 2006

I came up with:

5 pennies, 2 nickes, 6 dimes, 1 quarter

Basically trial and error.

posted by knave at 5:58 PM on March 14, 2006

Well, the easiest way is probably to start trying plausible combinations. I see three answers above already.

A more sophisticated way would be to write out the equations and solve them:

50a + 25b + 10c + 5d + 1e = 100

a+ b + c + d + e = 14

Two equations, five variables = multiple solutions.

posted by jellicle at 6:01 PM on March 14, 2006

A more sophisticated way would be to write out the equations and solve them:

50a + 25b + 10c + 5d + 1e = 100

a+ b + c + d + e = 14

Two equations, five variables = multiple solutions.

posted by jellicle at 6:01 PM on March 14, 2006

Response by poster:

Unless, as meerkatty pointed out, you don't use pennies. So that's not really a rule, but another way to go about it.

posted by soiled cowboy at 6:01 PM on March 14, 2006

*One obvious rule is you are either going to use 0, 5, or 10 pennies.*Unless, as meerkatty pointed out, you don't use pennies. So that's not really a rule, but another way to go about it.

posted by soiled cowboy at 6:01 PM on March 14, 2006

2 dimes 11 nickels, 1 quarter

6 dimes 8 nickels

5 pennies, 2 dimes, 5 nickels, 2 quarters

5 pennies, 6 dimes, 2 nickels, 1 quarter

posted by mto at 6:08 PM on March 14, 2006

6 dimes 8 nickels

5 pennies, 2 dimes, 5 nickels, 2 quarters

5 pennies, 6 dimes, 2 nickels, 1 quarter

posted by mto at 6:08 PM on March 14, 2006

this is very similar to a packing problem. in general, these tend to be "hard" (more exactly, there's no simple formula for finding the answer, but once you have the answer it's easy to check). the most famous is probably the knapsack problem.

however, having said that, it's not exactly the same as the packing problems i know - it has a fixed number of components for example - so it may be that in this case there is a simple solution.

posted by andrew cooke at 6:10 PM on March 14, 2006

however, having said that, it's not exactly the same as the packing problems i know - it has a fixed number of components for example - so it may be that in this case there is a simple solution.

posted by andrew cooke at 6:10 PM on March 14, 2006

*Unless, as meerkatty pointed out, you don't use pennies. So that's not really a rule, but another way to go about it.*

0, 5, or 10.

posted by knave at 6:11 PM on March 14, 2006

oh, I forgot to post my "solution". I just cheated and used code, which I knew would be possible because the values involved were tiny. Even the dumb algorithm I used only loops 537824 times, which is nothing for a modern computer.

Ruby:

for p in 0..14

for n in 0..14

for d in 0..14

for q in 0..14

next unless p+n+d+q == 14

next unless p+5*n+10*d+25*q == 100

puts "#{p} pennies, #{n} nickels, #{d} dimes, #{q} quarters\n"

end

end

end

end

posted by mto at 6:16 PM on March 14, 2006

Ruby:

for p in 0..14

for n in 0..14

for d in 0..14

for q in 0..14

next unless p+n+d+q == 14

next unless p+5*n+10*d+25*q == 100

puts "#{p} pennies, #{n} nickels, #{d} dimes, #{q} quarters\n"

end

end

end

end

posted by mto at 6:16 PM on March 14, 2006

Response by poster:

Oh. uh... Right.

posted by soiled cowboy at 6:18 PM on March 14, 2006

*0, 5, or 10.*Oh. uh... Right.

posted by soiled cowboy at 6:18 PM on March 14, 2006

Mathforum addressed this problem, except it was dividing the dollar into 25 coins.

posted by neda at 6:22 PM on March 14, 2006

posted by neda at 6:22 PM on March 14, 2006

Five pennies and nine nickels make one Barbados dollar.

Didn't say the

posted by weapons-grade pandemonium at 6:25 PM on March 14, 2006

Didn't say the

*dollar*had to be American.posted by weapons-grade pandemonium at 6:25 PM on March 14, 2006

It would appear that the easiest way to figure it out is to post it to AskMefi.

posted by flod at 7:00 PM on March 14, 2006

posted by flod at 7:00 PM on March 14, 2006

Start with jellicle's equations:

50H + 25Q + 10D + 5N + P = 100, H + Q + D + N + P = 14

List all possible values of each coin:

H: 0 1

Q: 0 1 2 3

D: 0 1 2 3 4 5 6 7 8 9

N: 0 1 2 3 4 5 6 7 8 9 10 11 12 13

P: 0 5 10

Since the nickel, quarter and penny represent odd values, the sum of the nickels, quarters and pennies must be even.

The trick is to choose values, either arbitrarily or by elimination, and to reduce the number of unknowns in jellicle's equations to 2 unknowns.

A quick look at the table above eliminates several values (e.g., 13 nickels is 65 cents and there's no such thing as a 35 cent coin, so 13 nickels is impossible), and the new table is:

H: 0 1

Q: 0 1 2

D: 0 1 2 3 4 5 6

N: 0 1 2 3 4 5 6 7 8 9 10 11

P: 0 5 10

There are only two cases for H: none or one. If we choose the case where H=1, jellicle's equations become:

25Q + 10D + 5N + P = 50, Q + D + N + P = 13

and the table becomes:

H=1:

Q: 0 1

D: 0 1 2 3 4

N: 0 1 2 3 4 5 6 7 8 9

P: 0 5 10

On this branch, the choices for Q are none or one. In the case where Q = 1, the equations reduce to:

10D + 5N + P = 25, D + N + P = 12 and the sum of N + P must now be odd. The new table is:

H=1, Q=1:

D: 0 1 2

N: 0 1 2 3 4 5

P: 0 5 10

The solutions can now be found by inspection. With zero dimes, there is only one combination of nickels (2) and pennies (10) that adds to 12 coins, but that doesn't add up to 25 cents. With two diimes, there are no combinations of nickels and pennies that produce 10 coins adding up to 5 cents. With one dime, there is only one combination of nickels (1) and pennies (10) that produce 12 coins that add up to 25 cents. From this branch, we get one solution of one half-dollar, one quarter, one dime, one nickel, and 10 pennies, which time is tight has already found.

Repeated traverses down the branches of the tree, eliminating possible choices and using jellicle's equations should produce all the solutions for this problem. Not as elegant as a set of equations, but not quite brute force, either.

posted by forrest at 8:06 PM on March 14, 2006

50H + 25Q + 10D + 5N + P = 100, H + Q + D + N + P = 14

List all possible values of each coin:

H: 0 1

Q: 0 1 2 3

D: 0 1 2 3 4 5 6 7 8 9

N: 0 1 2 3 4 5 6 7 8 9 10 11 12 13

P: 0 5 10

Since the nickel, quarter and penny represent odd values, the sum of the nickels, quarters and pennies must be even.

The trick is to choose values, either arbitrarily or by elimination, and to reduce the number of unknowns in jellicle's equations to 2 unknowns.

A quick look at the table above eliminates several values (e.g., 13 nickels is 65 cents and there's no such thing as a 35 cent coin, so 13 nickels is impossible), and the new table is:

H: 0 1

Q: 0 1 2

D: 0 1 2 3 4 5 6

N: 0 1 2 3 4 5 6 7 8 9 10 11

P: 0 5 10

There are only two cases for H: none or one. If we choose the case where H=1, jellicle's equations become:

25Q + 10D + 5N + P = 50, Q + D + N + P = 13

and the table becomes:

H=1:

Q: 0 1

D: 0 1 2 3 4

N: 0 1 2 3 4 5 6 7 8 9

P: 0 5 10

On this branch, the choices for Q are none or one. In the case where Q = 1, the equations reduce to:

10D + 5N + P = 25, D + N + P = 12 and the sum of N + P must now be odd. The new table is:

H=1, Q=1:

D: 0 1 2

N: 0 1 2 3 4 5

P: 0 5 10

The solutions can now be found by inspection. With zero dimes, there is only one combination of nickels (2) and pennies (10) that adds to 12 coins, but that doesn't add up to 25 cents. With two diimes, there are no combinations of nickels and pennies that produce 10 coins adding up to 5 cents. With one dime, there is only one combination of nickels (1) and pennies (10) that produce 12 coins that add up to 25 cents. From this branch, we get one solution of one half-dollar, one quarter, one dime, one nickel, and 10 pennies, which time is tight has already found.

Repeated traverses down the branches of the tree, eliminating possible choices and using jellicle's equations should produce all the solutions for this problem. Not as elegant as a set of equations, but not quite brute force, either.

posted by forrest at 8:06 PM on March 14, 2006

forrest may very well have been my data structures professor. His tree-structured algorithm's the best way to hit all possible combinations in the most efficient manner.

posted by middleclasstool at 8:22 PM on March 14, 2006

posted by middleclasstool at 8:22 PM on March 14, 2006

I did it the way a fourth-grader would do it -- I went to the drug store and asked change for a dollar while picking my nose.

"Here you go."

"NOOOOO! FOURTEEN!"

So the cashier took it back and gave me a quarter and started putting nickels on the conveyor belt and I counted them as I picked them up.

"twelve, thirteen, fourteen, fiveteen, sixteen ..."

So I gave back the last four nickels and got two dimes instead. Then I stopped picking my nose and left.

posted by user92371 at 8:52 PM on March 14, 2006

"Here you go."

"NOOOOO! FOURTEEN!"

So the cashier took it back and gave me a quarter and started putting nickels on the conveyor belt and I counted them as I picked them up.

"twelve, thirteen, fourteen, fiveteen, sixteen ..."

So I gave back the last four nickels and got two dimes instead. Then I stopped picking my nose and left.

posted by user92371 at 8:52 PM on March 14, 2006

> this is very similar to a packing problem. in general, these

> tend to be "hard" (more exactly, there's no simple formula

> for finding the answer, but once you have the answer it's

> easy to check). the most famous is probably the

> knapsack problem.

Yep, I'd call this a packing problem. However, since, in this particular problem, each element in the set is larger than the sum of all smaller items in the set, this becomes a "superincreasing" packing problem. These tend to be much easier to solve. (google for "superincreasing knapsack problem")

If the nickel were, say 7 cents, the dime 11, and the quarter 15, this could be a lot more challenging!

posted by blenderfish at 11:09 PM on March 14, 2006

> tend to be "hard" (more exactly, there's no simple formula

> for finding the answer, but once you have the answer it's

> easy to check). the most famous is probably the

> knapsack problem.

Yep, I'd call this a packing problem. However, since, in this particular problem, each element in the set is larger than the sum of all smaller items in the set, this becomes a "superincreasing" packing problem. These tend to be much easier to solve. (google for "superincreasing knapsack problem")

If the nickel were, say 7 cents, the dime 11, and the quarter 15, this could be a lot more challenging!

posted by blenderfish at 11:09 PM on March 14, 2006

eight nickels and six dimes. fourteen coins. The average coin is seven cents. Try to deviate from that as little as possible.

posted by faceonmars at 11:46 PM on March 14, 2006

posted by faceonmars at 11:46 PM on March 14, 2006

This thread is closed to new comments.

Or did you want the answer?

posted by deadfather at 5:50 PM on March 14, 2006