Monday, June 12, 2006

Riddle

How many different ways are there to make $7.65 using only Dimes, Quarters and Half Dollars? You can use a coin more than once or not at all. Got any ideas? I have a guess but I worked it out in my head and I don’t have a lot of confidence in it. I’ll use excel to brute force it after work. Bonus points if you can provide a general solution.

11 Comments:

Blogger Jim Brannick said...

For the life of me, I can't figure out how to get $7.65 without using pennies!

Riddles suck.

12/6/06 10:56  
Blogger Matt McMinn said...

14 half dollars = $7.00
- plus -
1 quarter = $7.25
- plus -
4 dimes = $7.65

There's only one way to make $0.65 with that money (one quarter and four dimes), so the question comes down to the number of ways you can make $7.
1) 14 half dollars
2) Replacing one (two, three, etc to 14) half dollars with two quarters)
3) Replacing one (two, three, etc to 14) half dollars with 5 dimes
4) Combinations of the two (two quarters + 5 dimes + 12 half dollars, four quarters + 5 dimes + 11 half dollars, two quarters + 10 dimes + 12 half dollars, etc)

Combinations
1) 1
2) 14
3) 14
4) 13!

Total is 13! + 29

Am I even close? Took about ten minutes to think this through, no need to brute force.

12/6/06 13:03  
Blogger Jim Brannick said...

McMinn, this reminds me of the time you tried to drill a hole in your head...

But seriously, I think you're wrong. 13 shriek = 6227020800. So your final answer was that, plus 29.
I think you are on the right track. Instead of a factorial, you need to sum all the integers 0 thru 15.
I did that quickly by punching 5! into my TI-82, and I came up with 120.

Although, you're much smrter than me, so you might be more righter.

12/6/06 14:02  
Blogger Garble said...

I got 21. But I’m really not sure it’s right.

There’s only one way to get .65$ with those coins. That means that it’s how many ways to make 7.00$. Those coins only sum in intervals of .50$ so if you use 1 dime you have to use 5. So it’s how many ways you can make .50$ with each coin. So there are 3 ways to make 0.50$ and 7/0.5 is 14
So 3*14 = 42 (insert hitchhikers guide to the galaxy joke here).
Then I assumed that this would be symmetrical and divided by 2 to get rid of the duplicates. The final step is where I’m pretty sure that I screwed up.

I like Matt’s solution better, except for the 13! That would give you the number of permutations. 13 half dollars and 2 quarters is the same combination as 2 quarters and 13 half dollars. But now all we have to do is look up the formula for combinations and we’re there. (I think)

12/6/06 14:17  
Blogger Matt McMinn said...

You are correct sir. My original was wrong: it's not 13 factorial, it's sum(0..13). I even wrote that down on my scrap paper, but got it in my head that I was doing a factorial.

Let Q = 2 quarters, D = 5 dimes, and H = 1 half dollar. There are 14 total positions, as it takes 14 half dollars to make $7.00. Consider the situation where you have 5 dimes replacing one of the half dollars. You have the following combinations of quarters.
Q D H H H H H H H H H H H H
Q Q D H H H H H H H H H H H
...
Q Q Q Q Q Q Q Q Q Q Q Q Q D
There are 13 such combinations. Now, you move to two half dollars replaced by dimes.
Q D D H H H H H H H H H H H
Q Q D D H H H H H H H H H H
...
Q Q Q Q Q Q Q Q Q Q Q Q D D
There's only 12 of these combinations.
The last one is
Q D D D D D D D D D D D D D

So, 13 + 12 + 11 + ... + 1 = 91. We already counted the cases where it's all quarters or all dimes, so we now have 91 + 29 = 120. Same as your answer. Question though: where did you get the number 15 from?

12/6/06 14:17  
Blogger Jim Brannick said...

okay. I can explain where I got "15" from. Basically, the way I started was to do what you did in your first step 1) and step 2) (14+1=15). Then, I got "14" the same way you got step 3). That's how I started my sum (15+14+... 0).

Suffice to say, we both got the same answer, just slightly different methods.

12/6/06 14:32  
Blogger Jim Brannick said...

A quick question:

Is this even a riddle??? Seems more like some mensa math puzzle to me.

12/6/06 14:34  
Blogger Garble said...

The 15 was a screw up. It should have been 2 and 12, not 2 and 13.

This is a mensa math problem. Sort of. The actual question was how many coins will you use if you use the same number of quarters, dimes and half dollars to sum to 7.65$

Than I got curious about this, didn't know the answer so I posted it. Any ideas about a general solution?

12/6/06 14:58  
Blogger Jim Brannick said...

I don't have a general solution, but I do have an answer to your other question "how many coins will you use to total 7.65 (if you use the same # of quarters/dimes/halfdollars)... you'll use 27 coins- 9 dimes, 9 quarters, 9 halfdollars.

Still, that was way easier than any Mensa math prob I've ever worked on.
Are you sure you haven't been reading lil' Garble's Baby Einstein math books?

12/6/06 15:27  
Blogger Garble said...

Yeah, the original question was way too easy. It's from a question a day desk calender. Most of the questions are pretty easy.

13/6/06 03:26  
Blogger Cohort Mandibles said...

Solution = Garble + gay / way too much time on hands.

13/6/06 05:15  

Post a Comment

Links to this post:

Create a Link

<< Home