I had one of those awesome experiences this week where a student thinks of a better question.

I had been playing around with this issue of what money costs to make. (Get the lesson here.) Not a pretty picture, by the way. Rounding only a little for simplicity and age appropriateness, we had this chart of costs:

Penny: 2.5 cents

Nickel: 11 cents

Dime: 6 cents

Quarter: 11 cents

My question was, **what coin makes the cheapest dollar, and what coin makes the most expensive dollar?** (For example, a dollar in dimes would cost 60 cents to make.) There was some controversy as kids staked some initial claims, and then everyone set to work.

But one girl ignored my question in favor of her own, which I have to say, is straight up better: **can you make a dollar in coins that also costs a dollar to make?** The dollar in dimes costs only 60 cents. What about eight dimes, two nickels, and ten pennies? As you can check, that costs 95 cents to make. So close!

And here’s the even better sequel to the story. This same girl worked with incredible focus for the next thirty-five minutes, and answered her own question. Can you find how she did it? Is there more than one answer?

I am embarrassed to say that I worked on this for quite a while when I should have been doing real work. I found one exact solution: 6 nickels, 2 dimes, and 2 quarters. I’m pretty sure that is the only solution, but I can’t prove it (yet).

This is the one the student came up with too. If you can prove it is unique, please post your proof!

I can probably prove it by exhaustion (examine every combination), but I haven’t listed out all the combinations.

Pennies and nickels cost more to make than their value; dimes and quarters less. Therefore, there must be coins from each of these two groups for balance.

Nickels, dimes, and quarters all have value 1 when taken modulo 5. That means that the total number of these three coin types must be a multiple of 5. (It was 10 in the solution I found.)

The number of pennies must be a multiple of 10. I figured this out because the total number of pennies must be divisible by 5 (since all the other coins are divisible by 5, and so is the total). Furthermore, the number of pennies must be even to avoid having a fraction of a penny in the total cost. Therefore the number of pennies must be divisible by 10. Since 40 pennies would constitute the entire allotted cost but less than the allotted value, there must be 0, 10, 20, or 30 pennies.

Working by trial and error at this point, for 10 pennies, the closest I can get it is $1.03 (4 nickels, 2 dimes, 2 quarters). For 20 pennies, the closest I can get it is $1.02 (1 nickel, 5 dimes, 1 quarter). For 30 pennies, the best I can do is $1.09 (2 dimes, 2 quarters).

Is there an elegant solution (that you know of)?

Let’s see. What if we look mod 11? Then we need the final amount to be 1 mod 11, but nickels and quarters don’t affect the total. This means we have either 0, 10, 20, or 30 pennies, which gives us a cost of 0, 25 (= 3 mod 11), 50 (= 6 mod 11), or 75 (= 9 mod 11) cents in just pennies.

For each of these, we can consider the corresponding number of dimes we need to make us come out to 1 mod 11. Each dime adds 6 cents, so that means with 10 pennies, we’ll need 5 dimes to obtain the right value mod 11 (since 25 + 30 = 55 = 0 mod 11). Similarly, with 20 pennies we would need 1 dime, and with 30 pennies we would need 6 dimes. This eliminates the possibility of 30 pennies immediately.

As you mentioned, the nickels, dime, and quarters must sum to a multiple of 5. For the case of 10 pennies and 5 dimes, we must have at least five more coins in nickels and quarters, and since they must have value adding up to forty cents, it can’t be more than that either. But look mod 2, and we immediately have a situation that can’t work, since we’ll be ending with an odd number.

For the case of 20 pennies and 1 dime, We can see that we must have exactly four nickels and quarters that have value 70 cents (the mod 2 argument prevents 9 nickels and dimes). But that clearly can’t work–four nickels and quarters won’t make 70 cents. So there is no solution for 20 pennies.

Thus, there must be 0 pennies. Looking mod 11, we must have 2 dimes to end at 1 mod 11. Looking mod 2, we must have a total of 8 nickels and quarters (18 would be too great a value). The solution follows, and it must be unique.

That’s the best I’ve got for the moment!

@Elizabeth: “Is there an elegant solution (that you know of)?”

This isn’t elegant, but with the below approach I reduced the possible combinations to try from over 200(?) to nine, and then got the answer. Consider it a “semi-exhaustive” approach

Glenn Laniewski

Blog:

autismplusmath

Latest post:

Math teachers, start baking your Pi Day pies early

http://autismplusmath.blogspot.com/2014/02/math-teachers-start-baking-your-pi-day.html

PROOF (SORTA)

Let A= # of pennies, B= # of nickels, C = # of dimes and D= # of quarters

Using the face values of the coins,

1A + 5B + 10C + 25D = 100

Using the metal value of the coins,

2.5A + 11B + 6C + 11D=100

By substitution, set the expressions equal to each other:

1A + 5B + 10C + 25D = 2.5A + 11B + 6C + 11D

Subtract the metal values from each side:

1A + 5B + 10C + 25D – (2.5A + 11B + 6C + 11D) = 2.5A + 11B + 6C + 11D – (2.5A + 11B + 6C + 11D)

-1.5A – 6B + 4C + 14D = 0

Add 1.5A and 6B to both sides:

-1.5A – 6B + 4C + 14D + (1.5A + 6B) = 0 + (1.5A + 6B)

14D + 4C = 6B + 1.5A

Factor out the GCF for each binomial:

2(7D + 2C) = 1.5(4B + 1A)

Multiply both sides by 2 to eliminate the decimal:

2[2(7D + 2C) = 1.5(4B + 1A)]

4(7D + 2C) = 3(4B + 1A)

Divide both sides by 3:

[4(7D + 2C) = 3(4B + 1A)] / 3

(4/3)(7D + 2C) = 4B + 1A

GIVEN:

7D + 2C must be a multiple of 3 since 4B + 1A equals a whole number

GIVEN:

D must equal 1, 2 or 3 because D is the number of quarters

Combinations of (D,C) that result in a multiple of 3 for 7D + 2C:

(1,1), (1,4), (1,7),

(2,2), (2,5), (2,8)

(3,0), (3,3), (3,6)

Calculate the face value dollar amount for each combination and eliminate 4 combinations for equaling or exceeding a dollar:

(2,5) 2(25) + 5(10) = 100

(2,8) 2(25) + 8(10) = 130

(3,3) 3(25) + 3(10) = 105

(3,6) 3(25) + 6(10) = 135

For the remaining 5 combinations, use (4/3)(7D + 2C) = 4B + 1A and

I. Calculate the value of (4/3)(7D + 2C) for each remaining combination

II. Set that value equal to 4B + 1A

III. For each combination of B and A that works, plug A,B,C, and D into

1A + 5B + 10C + 25D

and hope that it equals 100!

From here, working through the combinations one by one, it took about ten minutes or less to find a solution as the (D,C) combination of (2,2) gave

(4/3)(7D + 2C) = 4B + 1A

(4/3)(7(2) + 2(2)) = 4B + 1A

(4/3)(14 + 4) = 4B + 1A

(4/3)(18) = 4B + 1A

24 = 4B + 1A

From the previous calculation of face value dollar amounts, I knew that the (D,C) combination of (2,2) gave a face value dollar amount of 70 cents (2*25 + 2*10), meaning that I needed some combination of nickels and pennies to equal a face value of 30 cents.

24 = 4B + 1A

B = 6 A = 0

CHECK: 6*5 = 30 cents.

Final answer: 2 quarters, 2 dimes, 6 nickels, 0 pennies.

This is a clever approach, Glenn. I’ve got one additional argument from it.

From 4(7D + 2C) = 3(4B + 1A), divide both sides by 4. Then we have:

(7D + 2C) = 3(4B + 1A)/4.

Since the left side is integer valued, so is the right side, which means 4B+1A is a multiple of 4… which means that A is a multiple of 4, as well as a multiple of 10! But this means that the smallest positive value of A is 20.

Not sure if that can help your proof at all, but thought I’d mention it.

Dan,

Thanks for the compliment: it was a fun puzzle, and THANK YOU for sharing it.

Re: the right hand argument. Yeah, I actually started out with the fraction on the right side of the equation. But after trying a couple combinations, I realized that it was easier to solve the problem if the fraction was on the left side of the equation.

Why? Because then there were only three possibilities for quarter (1, 2, 3), resulting in only 9 combinations to have to evaluate.

By comparison, if you start with the fraction on the right side, you have eight possibilities for nickel (1,2,3,4,5,6,7,8), based on a metal value of 11 cents. You can also have up to a value of 36 for A, based on (1) a metal value of 2.5 cents per penny and (2) 4A is a multiple of 4 (so 37,38, or 39 for A would not work).

Taking into account that 4B + 1A must be a multiple of 4, the possible combinations to evaluate are

(1,0), (1,4), (1,8), (1,12), (1,16)

(1,20), (1,24), (1,28), (1, 32), (1,36)

(2,0), (2,4), (2,8), (2,12), (2,16)

(2,20), (2,24), (2,28), (2, 32), (2,36)

(3,0), (3,4), (3,8), (3,12), (3,16)

(3,20), (3,24), (3,28), (3, 32), (3,36)

(4,0), (4,4), (4,8), (4,12), (4,16)

(4,20), (4,24), (4,28), (4, 32), (4,36)

(5,0), (5,4), (5,8), (5,12), (5,16)

(5,20), (5,24), (5,28), (5, 32), (5,36)

(6,0), (6,4), (6,8), (6,12), (6,16)

(6,20), (6,24), (6,28), (6, 32), (6,36)

(7,0), (7,4), (7,8), (7,12), (7,16)

(7,20), (7,24), (7,28), (7, 32), (7,36)

(8,0), (8,4), (8,8), (8,12), (8,16)

(8,20), (8,24), (8,28), (8, 32), (8,36)

Unfortunately, *none* of these 80 possibilities can be eliminated by calculating the face value dollar amount:

(8,36) 8(5) + 36(1) = 76

And staring at that many combinations to have to try, I think I would’ve curled up under a rock rather than attempt it

Glenn Laniewski

Blog:

autismplusmath

Latest post:

Math Video Challenge Registration Now Open!

http://autismplusmath.blogspot.com/2014/02/math-video-challenge-registration-now.html

How many ways are there to make 5 cents?

5 pennies = 12.5

1 nickel = 11

With these, how many ways are there to make 10 cents?

1 dime = 6

2 nickels = 22

1 nickel + 5 pennies = 23.5

10 pennies = 25

and so on. Enumerating all combinations for 25 cents, you can make

11, 23, 24.5, 39, 40.5, 42, 43.5, 55, 56.5, 58, 59.5, 61, 62.5

Then you can save some time making 50 cents: since the cheapest 50-cent combinatinos are 22, 34, 35.5, 46, 47.5, 49, and then 50, we only have to look for combinations that add up to 78, 66, 64.5, 54, 52.5 or 51. Here’s the complete list:

78=39+39

78=55+23

66=55+11

64.5, 54, 52.5, and 51 have no solutions.

Then we just backsolve for all 25-cent combinations that give us 39, 55, 23, and 11. 39 is D + 3N, 55 is 5N, 23 is 2D + N, and 11 is Q. All the solutions end up being the same, 2Q + 2D + 6N.

Dan,

“Since the left side is integer valued, so is the right side, which means 4B+1A is a multiple of 4… which means that A is a multiple of 4, as well as a multiple of 10! But this means that the smallest positive value of A is 20.”

This would mean we could cut the possible solutions in half from 80 to 40: eliminate all of the possible solutions with A less than 20. But my brain is drawing a blank as to why we know that A must be a multiple of 10. (I’m sure it’s something patently obvious to a four year old, but it’s been one of those days–or at least that’s my excuse!

Glenn Laniewski

Blog:

autismplusmath

Latest post:

Math Video Challenge Registration Now Open!

http://autismplusmath.blogspot.com/2014/02/math-video-challenge-registration-now.html

Isn’t this a version of the Knapsack problem? If so, I think that means there’s no easy way to get solutions except by exhaustion.