Tuesday, January 2, 2007

Hey Buddy..You Got Change For A Dollar?

Another math problem:

Using just pennies, nickels, dimes, and quarters, how many distinct ways are there to get $1 (order does not matter).

3 comments:

Kimota94 aka Matt said...

You're really good at making me doubt my ability to do math!

Anyway, I can't see how to solve this algebraically. I can see that the equation:

25Q + 10D + 5N + P = 100,

where Q = # of quarters, D = # of dimes, N = # of nickels and P = # of pennies

represents the set of answers, as long as we limit the variables to being greater than or equal to 0 and integer only.

I then end up looking at brute force approaches, such as:

Consider looking for ways to get a total of 25, and then calculate the product of those combos in getting 100.

One way to get 25 is with Q alone. All other combos assume no Q's.

If D = 2 (its highest possible value), then your only choices are N = 1 & P = 0, or N = 0 & P = 5. So that's 2 more combinations for getting to 25, bringing us to 3 so far.

If D = 1, then your choices are N = 3 & P = 0, N = 2 & P = 5, N = 1 & P = 15, and N = 0 & P = 15. That's 4 more combinations, for a total of 7 so far in getting to 25.

If D = 0, then your choices are N = 5 & P = 0, N = 4 & P = 5, N = 3 & P = 10, N = 2 & P = 15, N = 1 & P = 20, and N = 0 & P = 25. That's 6 more combinations, for a total of 13 so far.

So now we know there are 13 combinations of Q, D, N & P that uniquely add up to 25.

To get to 50, each combination of the 13 options would be represented by 13 * 13, or 169. However, that misses one combination that wouldn't have been arrived at from combining the original 13 with itself, which is D = 5. So the adjusted total is 170.

To get from 50 to 100, do the same cross-combining of the answer for 50, or 170 * 170, for a total of 28,900 combinations of Q, D, N & P to get to 100.

No idea if this is right, but I can't see anything that I've missed, so that's my answer!

Kimota94 aka Matt said...

One of my "& P = 15" should have been "& P = 25", of course. But it didn't affect the answer (just my notes on how I got to it)!

Kimota94 aka Matt said...

Hey Math Geek, how come you didn't celebrate the fact that this was your 64th blog entry? That's 2 to the power 6, you know!