Saturday, August 06, 2005

12-Ball Challenge!

I love these puzzles that have shown up recently in the blogsphere. Ben Wright has had several “Guess the author” games over at Paleoevangelical and Larry Rogier has a logic riddle online now at his blog, Stuff Out Loud. These games are great fun, especially when you can figure out the answer. :)

My favorite puzzle is the one that my father-in-law posed one Thanksgiving dinner prior to my engagement and marriage to his daughter. Somehow we got on the subject of riddles and puzzles, everyone throwing out their own little puzzle when finally my future father-in-law challenged us with his puzzle and claimed that no one would be able to solve it without a hint from him! At the time, I was working as a cryptomathematician for the National Security Agency and I took it as somewhat of a professional challenge. I certainly wasn't going to ask for a hint without giving it a decent try on my own. Daphne and I worked on it together over Christmas as we flew out to California for her to meet my parents but we really didn’t get very far. It was indeed a tough puzzle. I don’t remember how or when but I finally figured out the trick that unlocked the solution. After our trip, I presented the puzzle to several of my colleagues at work, some of them PhD mathematicians. One said it was impossible to solve because it violated Shannon’s law of information theory. This particular individual was not happy when I showed him the solution.

At any rate, then next time I visited Daphne at her home, I sat down with her father and told him I had a solution to his puzzle. With a bit of skepticism, he listened to me as I not only solved the 12-ball problem but showed how it could be extended and solved up to 15 balls. He was both impressed and pleased, I think, that someone was able to solve his riddle. I wasn’t finished, though. I told him that I wanted a reward for solving his impossible puzzle – his daughter’s hand in marriage! Alright, I’m a geek. I admit it. But that is the story of how I secured my father-in-law’s permission to marry his daughter. By the way, his 6-year old grandson, JD, is pretty good at solving puzzles himself now, too.

Oh, here is the puzzle:

You have 12 balls. They are all the same in color and size. They all weigh the same except for one ball. The challenge – find the odd-weighted ball in 3 or less weighings using a balance scale.

You can probably find this on the Internet so no fair using Google!

12 Comments:

At 1:32 PM, Anonymous Anonymous said...

Okay Andy, I will try it. You divide them into three even groups of 4 balls each. Lets call them group A, B, C. Place Group A on one side of the balance, Group B on the other side. If they are equal, then Group C has the weighted ball. If one side is heavier on the balance scale, then the group on that side has the heavier ball.

Pick one of those groups. Lets call it Group D now. Divide Group D into two sets of balls. Let's call them Group E and F now. Place Group E (containing 2 balls) on one side. And Place Group F (containing 2 balls)on the other side. The scale will lean to the group containing the heaviest ball.

Now take that group of two balls and separate them and place each ball on each side of the scale. The scale will lean to the heaviest ball. That was done in three weighings.

No I did not look for an answer. This took about 3 minutes, so hopefully it is right.

 
At 1:43 PM, Blogger Andy Efting said...

That is a good guess but not quite right. You are assuming something that was not stated in the problem statment -- that the odd weighted ball is heavier than the others. The correct solution must take into account the possibility of the odd-weighted ball being lighter as well.

 
At 2:04 PM, Anonymous David Szweda said...

Hmmm! There goes me and my assumptions. I will have to think about this just a little more.

 
At 8:24 PM, Anonymous dgszweda said...

OK getting more difficult now. I had some time in the car to think about this. I still think I am on the right track to start with three groups of 4 balls. I think this track will solve it. At this point, I have invested about an hour into the solution. I have figured out this much so far. I found the solution if group a and group b match. I am still working out when they don't match, but I don't have a lot of time tonight, so I may have to pick it up in the morning.

You take 12 balls and separate them into three groups. Each group is A, B, C. You place Group A and Group B on either side of the balance.

1.1 – if Group A and B are balanced, then Group C has the weighted ball.
1.1.1 – You now know that Group A and Group B have equal weighted balls (they can now be a control group) and Group C has a weighted ball. Place two of the balls from Group C on the right side of the scale, and two balls from Group A on the scale. If They are equal than you know the two remaining balls from group C are the weighted ball.
1.1.1.1 Take the two remaining balls from group C, and place one of them on the right side of the scale, and place a ball from Group B on the other side. If they are equal, the weighted ball is in your hand. If they are unbalanced, then the ball on the right side from group C is the weighted ball.
1.1.2 If they are unbalanced in 1.1.1, then you know the balls on the right side of the scale from Group C contained the weighted ball. Follow step 1.1.1.1, to find the offending ball.
1.2 If they are unbalanced from 1.1, then

 
At 9:21 PM, Anonymous dgszweda said...

Okay, getting closer:

You take 12 balls and separate them into three groups. Each group is A, B, C. You place Group A and Group B on either side of the balance.

1.1 – if Group A and B are balanced, then Group C has the weighted ball.
1.1.1 – You now know that Group A and Group B have equal weighted balls (they can now be a control group) and Group C has a weighted ball. Place two of the balls from Group C on the right side of the scale, and two balls from Group A on the scale. If They are equal than you know the two remaining balls from group C are the weighted ball.
1.1.1.1 Take the two remaining balls from group C, and place one of them on the right side of the scale, and place a ball from Group B on the other side. If they are equal, the weighted ball is in your hand. If they are unbalanced, then the ball on the right side from group C is the weighted ball.
1.1.2 If they are unbalanced in 1.1.1, then you know the balls on the right side of the scale from Group C contained the weighted ball. Follow step 1.1.1.1, to find the offending ball.
1.2 If they are unbalanced from 1.1, then you know for sure that Group C now has equal weights and therefore it can be a controlled group. One of the balls from Group A or Group B is weighted. Then take one ball away from the balls in Group A and one away from Group B and replace them with 2 balls from Group C. If they balance out, then follow 1.1.1.1 with the two in your hand. If they are unbalanced then:
1.3

 
At 7:30 AM, Blogger Andy Efting said...

David,

You are very close. It only reamins for you to discover the final trick. The final trick, of course, is the hard part.

 
At 10:30 AM, Anonymous dgszweda said...

I need about another hour of uninterrupted peace to figure it out. I have to switch balls from either side along with replacing them with a controlled ball, and whether the balance moves in order to get it, but I don't have the sequence figured out. Not sure if I will have any time to think about it today, or at least not the thinking I need to do. But I feel that I am close.

 
At 4:55 PM, Blogger Frank Sansone said...

Andy,

Here is my attempt at a solution. I believe that it works, but I might be missing something. (David, don't look if you don't want it ruined for you.)

1. Divide into three groups of four. (A, B, C)

2. Weigh two groups (A & B)

3. IF A & B are equal, skip down.

4. If A & B are unequal, your ball is in one of those two groups. Note which balls are in the lighter bag (number them 1-4, for instance) and which balls are in the heavier bag (5-6).

5. Take two balls from each bag (1,2,5,6) and put into a bag (bag D) and weigh them against bag C (the control group from earlier).

6. If bag D is lighter than bag C, your ball is going to be ball 1 or 2 (set them aside for the next step). If bag D is heavier than bag C, your ball is going to be ball 5 or 6 (use them for the next step).

7. Take one of the two balls set aside and weigh it against a control ball. If it is the same, your ball is the other ball that you just took out. If it is different, your ball is the one you just weighed.

8. If your bag A & B were equal, then your ball is in bag C. Use one of the other bags as your control balls. Weigh two of them against two in that bag and break it down as before.

I think I got it.

Frank Sansone

 
At 6:54 AM, Blogger Andy Efting said...

Ding! Ding! Ding! Yes, Frank, I believe that you have figured it out. Well Done.

 
At 10:16 AM, Blogger Marco! said...

Hey Andy, i was looking for puzzles on people's blogs and i came across your 12 ball puzzle, i really liked it but i was wondering about extending it to 15-balls and still using 3 weighs..
I would love to know the solution for that one.
Thanks in advance.

 
At 10:22 AM, Blogger Andy Efting said...

I will see if I can remember how to do that and then post an answer. I know it can be done...

 
At 9:23 AM, Anonymous David Nash said...

I know this is late (and I hate to throw cold water on Frank), but I beleive his proposed solution is deficient. In step 6 if bags D and C balance, then you're stuck. You know that (3,4,7,8) contains the odd ball, but you can't pick it out with just one weighing remaining.

It's a great problem, with an elegant (though not simple) solution.

 

Post a Comment

<< Home