This week's giveaway is in the Testing forum.We're giving away four copies of TDD for a Shopping Website LiveProject and have Steven Solomon on-line!See this thread for details.
Win a copy of TDD for a Shopping Website LiveProject this week in the Testing forum!
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Paul Clapham
• Ron McLeod
• Jeanne Boyarsky
• Tim Cooke
Sheriffs:
• Liutauras Vilda
• paul wheaton
• Henry Wong
Saloon Keepers:
• Tim Moores
• Tim Holloway
• Stephan van Hulst
• Carey Brown
• Frits Walraven
Bartenders:
• Piet Souris
• Himai Minh

# A puzzle...

author
Posts: 9034
21
• Number of slices to send:
Optional 'thank-you' note:
Actually three puzzles, rated medium, hard, really, really hard!
1) Given a balance scale and eight numbered balls, state the stategy to determine which one of the balls is either heavier or lighter than the others, given three chances to use the balance scale. Also determine whether the odd ball is heavier or lighter.
2) Same deal, with 10 balls.
3) Same deal, with 12 balls.

Sheriff
Posts: 6920
• Number of slices to send:
Optional 'thank-you' note:
Ah yes.
Strangely enough, the 12-ball version of this was used as a sort of "are you smart enough" test by my Father-in-Law. He set the puzzle both to me, and to the chap who eventually married his other daughter. We both solved it (although apparently I was quicker ), so we got the girls!
I wonder what happened to the poor guys who failed

Ranch Hand
Posts: 156
• Number of slices to send:
Optional 'thank-you' note:
Given three balls a,b,c if u know a is not the odd ball, you can weigh a against b and find out if
a > b, then b is the odd and is lighter
a < b, then b is the odd and is heavier
a == b, then c is the odd. to find out lighter of heavier, we have to weigh a and c once more. in this case it is a 2-step process.
Let's call this process as 3-by-1 rule or Rule31.
---------------------------------------
Let the balls be numbered as 1,2,3...8.
Divide them in three groups as 123 456 78
chance #1123 against 456 (keep 78 aside for now)
if they are equal, then one of the 7 or 8 is odd.
find out which by using balls 1,7,8 and Rule31
In this case Rule31 may use two chances.
chance #2weigh 1 against 7
chance #3weigh 1 against 8
(if 1 and 7 are equal, then we know 8 is the odd, but we still have to find out if 8 is lighter or heavier)
So atmost three chances.
or
if they are not equal then one of the 123456 is odd.
But we also know two more points
1. Which group 123 or 456 is ligher and which is heavier based on the shift of the balance.
2. 7 and 8 are ok.
Chance #212 against 34 (kkep 56 aside for now)
if they are equal, then one of 56 is odd.
chance#3 Use Rule31 with 1,5,6 to find out odd. We already know light or heavy
if the balance between 12 against 34 shifts the other way, then the culprit was 3. Because we moved 3 from one side to other. In this case we solved it in two chances only.
If the balance shifts the same way, then the culprit is one of 124, but 3 is ok
chance #31 against 2
if balance still shifts the same way, 1 is odd
if balance still shifts the other same way, 2 is odd
if equal, 4 is odd

Did I miss anything ?
Still trying with 10 and 12 version

Melvin Menezes
Ranch Hand
Posts: 156
• Number of slices to send:
Optional 'thank-you' note:
For 10 balls, divide in three groups as 123 456 789A
Chance#1 as above. 123 against 456
if they are not equal, then one of 123456 is odd. Proceed as Chance #2 that we did in the 8-ball example.

If they are equal, that is if 123 == 456, then one of 789A is odd. In that case, proceed as follows
Chance #2, 123 against 789
If equal, A was odd.
Use chance #3, 1 against A to find out of A is light or heavy

If not equal, then A is ok. One of 789 is odd. And based on the shift in balance, we know whether it is heavy or light.
Chance #3, 7 aganst 8.
If the balance shifts as before (the way in 123 and 789), 8 is odd.
If the balance shifts in oppsoite direction 7 is odd.
I equal, 9 is odd.

Is that right Bert?

Melvin Menezes
Ranch Hand
Posts: 156
• Number of slices to send:
Optional 'thank-you' note:
For 12 balls, divide them in three groups as 1234 5678 9abc
chance #1,1234 against 5678 (keep 9abc aside)
if 1234 == 5678, then proceed with 9abc as in 10-balls from chance #2

if 1234 != 5678, then one of 12345678 is odd and 9abc are ok.
Note the balance(B) shift.
Chance #2129 against 345 (keep 678 unknowns aside, we know abc are ok)
if the balance shifts as before, then one of 125 is odd. proceed as 3.1 below
if the balance shifts other way, 3 or 4 is odd. proceed as 3.2
if the balance is equal, then one of 678 is odd. Proceed as 3.3

Chance #3.1, weigh 1 against 2 (kkep 5 aside)
if shifts as before (that we noted when we did 1234 against 5678), then 1 is odd.
if shifts opposite (that we noted when we did 1234 against 5678), then 2 is odd.
if balanced, then 5 is odd.
We already know whether the odd ball is light or heavy based on the previously noted shift in balance(B).

Chance #3.2, use Rule31, with balls 3,4, and 9
Chance #3.3, weigh 6 against 7 (keep 8 aside)
if shifts as before (that we noted when we did 1234 against 5678), then 7 is odd.
if shifts opposite (that we noted when we did 1234 against 5678), then 6 is odd.
if balanced, then 8 is odd
We already know whether the odd ball is light or heavy based on the previously noted shift in balance(B).

You there Bert, Frank?
[ March 24, 2003: Message edited by: Melvin Menezes ]

tumbleweed
Posts: 5089
• Number of slices to send:
Optional 'thank-you' note:

Originally posted by Frank Carver:
Ah yes.
Strangely enough, the 12-ball version of this was used as a sort of "are you smart enough" test by my Father-in-Law. He set the puzzle both to me, and to the chap who eventually married his other daughter. We both solved it (although apparently I was quicker ), so we got the girls!
I wonder what happened to the poor guys who failed

Does that mean you got the # 1 daugther Frank
[ March 24, 2003: Message edited by: Johannes de Jong ]

Greenhorn
Posts: 21
• Number of slices to send:
Optional 'thank-you' note:

Xi Xi ..........

Melvin Menezes
Ranch Hand
Posts: 156
• Number of slices to send:
Optional 'thank-you' note:
You there Bert, Frank?
Is the method correct? What's your version? Any shortcuts?

Frank Carver
Sheriff
Posts: 6920
• Number of slices to send:
Optional 'thank-you' note:
Does that mean you got the # 1 daugther Frank?
I like to think so.

Melvin Menezes
Ranch Hand
Posts: 156
• Number of slices to send:
Optional 'thank-you' note:
You there, Bert? What's your version, Frank? Whaat shortcut did ya use to get yur garl?

Cowgirl and Author
Posts: 1589
5
• Number of slices to send:
Optional 'thank-you' note:
Sorry -
Just out of town - in an internet cafe... will review the answer on Saturday!!
-Bert - yes it's really Bert

Bert Bates
author
Posts: 9034
21
• Number of slices to send:
Optional 'thank-you' note:
Melvin -
Sorry for the delay! We had to go to the Software Developer's convention - to pick up JAVARANCH's PRODUCTIVITY AWARD !!!
YEAH!
Anyway, we're back now - I looked over your answer and it seems to match with mine...
To me, the key to cracking this is the following step from your post, on weighing #2...
===================
Chance #2129 against 345 (keep 678 unknowns aside, we know abc are ok)
===================
Once you've made that breakthrough the rest falls into place pretty easily.
I'm not even going to tell you how long it took me to solve that puzzle - Melvin my hat's off to you!
-Bert
[ March 30, 2003: Message edited by: Bert Bates ]

Melvin Menezes
Ranch Hand
Posts: 156
• Number of slices to send:
Optional 'thank-you' note:
BB: We had to go to the Software Developer's convention - to pick up JAVARANCH's PRODUCTIVITY AWARD !!!
YEAH!

congratulations!

BB: Melvin my hat's off to you!
:grinning-ear-to-ear:

 bacon. tiny ad: free, earth-friendly heat - a kickstarter for putting coin in your pocket while saving the earth https://coderanch.com/t/751654/free-earth-friendly-heat-kickstarter