Twelve Golden Balls
by Tom Temple
26 April 2005
Most of you have seen this one but maybe not the version that I am about to give. The solution to this one is so much more asthetically pleasing than the standard version.
There are 12 seemingly identical golden balls, one of which weighs slightly more or slightly less than the other 11. I have a ballance and want to determine which of the 12 balls is the odd one and also determine whether that ball is heavier or lighter thean the rest.
We only get to use the scale 3 times due to a callibration issue.
The part that is different than you’ve heard before is this: Before I weigh anything, you will tell me which balls go on which side of the scale for all three weighings. Then I will perform those three weighings. Then I will tell you the outcomes. Then you will tell me which ball and whether it is heavy or light. In that order.
In other words, your method cannot be adaptive.
Answer is in the comments
Apr 27, 05:31 PM
You need unique combinations of appearance in your weighings for each ball. That is, each ball’s path across the three weighings must not be the same (or a mirror) of any other ball’s.
You have two variables you can manipulate about the ball’s path. Its number/order of appearances (relative to the other balls) and the side of the scale (relative within a ball).
For balls 1-12: X means it appears, O means it appears on the opposite side, _ means it doesn’t appear. The first one is the first weighing, second etc etc
1: X X O
2: X O X
3: O X X
4: X X _
5: _ X X
6: X _ X
7: X O _
8: _ X O
9: X _ O
10: X _ _
11: _ X _
12: _ _ X
Each ball has a unique pattern of movement through the three trials, such that when you do weighings, the results will point to only one ball.
Now this is the part where I just ended up kind of crunching this stuff together until I got groups of 4 on either side for all 3 weighing trials (since there are 8 balls present for each weighing, and you need to have equal numbers on each side of the scale). The restraint is just the relative position of each ball to its own pathway, and the fact that you must have 4 on each side for each turn.
I came to:
1 2 3 4 – 6 7 9 10
1 4 5 7 – 2 3 8 11
2 5 8 9 – 1 3 6 12
you can take one of the three-appearance balls (balls 1, 2, or 3 in this case) and make it all on the same side if you want, and switch over one of the single balls (10, 11, or 12) to make another solution.
This doesn’t feel particularly elegant. Is there a cleaner way to solve this?
Apr 27, 09:30 PM
Well done Pete and good to hear from you! The elegant part was the first step before you mashed them into slots. There is almost a really beautiful solution to be had there.
Let me consider your X, 0, _ to be ballanced base 3 number written with least significant tit first (i.e. backwards) Let X be 1, O be -1 and _ be zero. That way we can look at the outcomes as if it were a number between -13 and +13 inclusive. Rather than assign balls willy-nilly, lets try to make it correspond to these outcomes.
Let’s see if we can make it so the “number” the scale reads out is the number of the odd ball and that number’s sign tells us if it is positive or negative.
Don’t forget that the number is written backwards: ones place, threes place, nines place.
1 = X _ _
2 = 0 X _
3 = _ X _
4 = X X _
5 = 0 0 X
6 = _ 0 X
7 = X 0 X
8 = 0 _ X
9 = _ _ X
10= X _ X
11= 0 X X
12= _ X X
13 unused
The negatives are the same with Xs and Os flipped.
So now we have to see if we can fit these on the scale. Sadly, the RHS of the third weighing is completely empty. We can fill it by negating any four of 5-12 and still maintain most of our elegance. If we choose 8,9,10,12 we have 4 balls on each side for each weighing.
So we have:
1 = X _ _
2 = 0 X _
3 = _ X _
4 = X X _
5 = 0 0 X
6 = _ 0 X
7 = X 0 X
-8 = X _ 0
-9 = _ _ 0
-10= 0 _ 0
11 = 0 X X
-12= _ 0 0
Which in scale notation is
1 4 7 (8) – 2 5 (10) 11
2 3 4 (9) – 5 6 7 (12)
5 6 7 11 – (8)(9)(10)(12)
So you can just read off the number from the base-three representation of the outcome and the heavy or light corresponds with the sign unless it was 8,9,10 or 12 in which case, the sign is reversed.