** Bio ** Resume **
All | Computers | Exercise | General | Humor | Personal | Puzzles
« SUPerG 2005 Paper | Main | Rocket Science &... »

20050223 Wednesday February 23, 2005

HARD: 12 Balls and a Scale Puzzles

I found it! This logic puzzle appears simple. But when I was challenged with this about 12 years ago (by my good friend Scott Bardsley - now a chip designer at Analog Devices) it took me two days to figure it out! There are no tricks. Yes, there is a solution... I do really mean three (3) moves. And the solution must work in the general case (every time). Don't start this unless you have some time (eg: flying across the pond).

You are given 12 billiard balls that all appear identical in color, size, weight, texture, composition, etc.  But one of the balls is either slightly lighter or slightly heavier than the other 11. You have a simple balance scale. Describe the process that will allow you to determine which ball is different, and if it is heavier or lighter. Oh... you can only use the scale THREE times.

In case you give up, here is the solution:
http://blogs.sun.com/roller/resources/dcb/SOLUTION_12_Balls.html


February 23, 2005 06:28 AM EST Permalink

Comments:

I just came across your site while surfing blogs. There is a second method for determining the odd ball - no labelling required. Place 6 balls on either side of the scale. Remove the six with less mass. Take the remaining six and place three on each side of the scale. Again remove the three of lower mass. Last, place one ball on each side of the scale, leaving one ball separate. If the scales balance, then the ball remaining has the greater mass. If the scale does not balance then the heavier ball is obvious.

Posted by Rob Windrim on February 12, 2006 at 04:51 PM EST #

OK, my bad, smack me upside the head. I assumed only a heavier ball - gotta read those instructions more carefully. - Homer

Posted by Rob Windrim on February 12, 2006 at 04:53 PM EST #

There is in fact another, maybe more elegant way of solving the riddle. Label the balle 1-12 Weigh then like this: 1,2,3,4 against 5,6,7,8 1,3,5,6 against 2,9,10,11 1,4,7,9 against 2,5,11,12 Acording to the various outcomes the odd ball can be determines. Example: right, left, right gives ball 5 heavy. If left, right, left ball 5 is light.

Posted by Nicolai Bork on March 02, 2006 at 09:12 AM EST #

To avoid misunderstanding. 1,2,3,4 against 5,6,7,8. Then 1,3,5,6 against 2,9,10,11. Then 1,4,7,9 against 2,5,11,12.

Posted by N on March 02, 2006 at 09:15 AM EST #

eh--nicolai your solve doesnt work.too few permutations.

Posted by limbo on April 15, 2006 at 01:49 AM EDT #

I think the solve works. You can even add an extra ball, 13 balls and a scale, and the solve would still work. You have 3^3=27 perlutations and 24 or 26 different situations. If you doesn´t agree please give me an example of where the solve fails.

Posted by Nicolai Bork on April 16, 2006 at 05:13 AM EDT #

At coser examination it is clear that a 13´th ball can´t be added. I belive that the solve works for 12 balls. Any counter example is wellcome.

Posted by Nicolai on April 16, 2006 at 12:36 PM EDT #

well, you only have 2x2x2 permutations, which allots for 8 different permutations, not 27. The scale gives a binary answer when you weigh it.

Posted by Andy on June 26, 2006 at 01:50 PM EDT #

The scale can also be even so you have 27 permutations. Test the method and you will see that it works.

Posted by Nicolai on July 02, 2006 at 12:52 PM EDT #

that works to me nicolai, and actually contains many of the details of the other proof in a more general package.

Posted by Simon on July 06, 2006 at 07:18 PM EDT #

Nicolai, your answer does not work BECAUSE if the original scales tilt toward 1, 2, 3, 4 then then the odd ball is in 1, 2, 3, 4(Heavy) or, 5, 6, 7, 8(Light). If 1, 3, 5, 6 balance with 2, 9, 10, 11 then the odd ball is either 4, 7, or 8. Your last step involves two possible unknowns so if the scale tilts either way then 4, 7 is the odd ball and you failed to answer the question.

Posted by Justin on November 17, 2006 at 08:21 PM EST #

The Solution Is (Others may exist) ---------------------------------------------- Set 1,2,3,4 agaisnt 5,6,7,8 if not balanced we know the odd ball is in 1,2,3,4,5,6,7,8 Set 1,2,3,5 against 4 and three knowns (9,10,11) if balanced the odd ball is in 6,7,8 and depending on how first set tilted is weight Set 6 against 7 if balanced the odd ball is 8 if not balanced then with the knowledge of whether the odd ball is light or heavy and direction of tilt it can be determined which ball is odd ----------------------------------------------- Set 1,2,3,4 agaisnt 5,6,7,8 if not balanced we know the odd ball is in 1,2,3,4,5,6,7,8 Set 1,2,3,5 against 4 and three knowns (9,10,11) 1.if not balanced and tilt changes, odd is 4,5 2.if no balance and tilt stays, odd is 1,2,3 and depending on first set tilt is weight 1. Set 4 against a known ball (1) if balanced odd is 5 if not balanced odd is 4 tilt of first set will determine light/heavy 2.Set 1 against 2 if balanced the odd ball is 3 if not balanced then with the knowledge of whether the odd ball is light or heavy and direction of tilt it can be determined which ball is odd ----------------------------------------------- Set 1,2,3,4 agaisnt 5,6,7,8 if balanced we know the odd ball is in 9,10,11,12. Set 9,10,11 against three known balls (1,2,3) 1. If balanced the odd ball is 12 2. If not balanced the odd ball is 9,10,11 and this set's tilt shows weight 1.Set 12 against anyother ball Direction of tilt determines weight 2.Set 9 against 10 if balanced the odd ball is 11 if not balanced then with the knowledge of whether the odd ball is light or heavy and direction of tilt it can be determined which ball is odd

Posted by Justin on November 17, 2006 at 09:11 PM EST #

Sorry for the format of my last post

Posted by 216.98.91.152 on November 17, 2006 at 09:14 PM EST #

I did this in about 45 minutes, except there were 13 balls instead of 12. The solution is pretty much unchanged though... Does anyone know of more good questions like this?

Posted by Dave on December 12, 2006 at 07:56 PM EST #

To Justin It accually still works. If the scale tilts left on first weigh and even on second you have 2(heavy),7(light) or 8(light) as the odd ball as you correctly says. On the last weigh you weigh 2 and 7 on the same (left) side and ball 8 is not weighed at all. So if the third weigh is even -> ball 8 light. If left-> ball 2 heavy. If right-> ball 7 light. Check this table: 1 H (LLL) 1 L (RRR) 2 H (LRR) 2 L (RLL) 3 H (LLE) 3 L (RRE) 4 H (LEL) 4 L (RER) 5 H (RLR) 5 L (LRL) 6 H (RLE) 6 L (LRE) 7 H (REL) 7 L (LER) 8 H (REE) 8 L (LEE) 9 H (ERL) 9 L (ELR) 10 H (ERE) 10 L (ELE) 11 H (ERR) 11 L (ELL) 12 H (EER) 12 L (EEL) ALL WEIGH PATTERNS ARE DIFFERENT. I belive this is the easiest way to do it. Any counterexample is still wellcome.

Posted by nicolai on January 18, 2007 at 05:44 PM EST #

To justin (and Dave) Check the table and you will see that it works. It will take no longer than 5 minutes.

Posted by nicolai on January 18, 2007 at 05:51 PM EST #

Post a Comment:

Comments are closed for this entry.

Valid HTML! Valid CSS!

This is a personal weblog, I do not speak for my employer.