See animated solver
My sister likes to send me puzzle emails every once in a while. One day I found this little e-mail in my inbox.
Hi Rich,
Can you solve this problem?
There are 12 stones, 11 of equal weight, 1 of unequal weight (either heavier or
lighter).
Use 3 weighings on a balance scale to tell what stone has a different weight and if it is heavier or lighter.
I figured this must be a very old puzzle, but it was one I hadn't remembered seeing before. So I think to myself, I'm a smart guy, I'll send back a quick answer that same day. Needless to say, here was my response a few days and a few dozen sheets of paper later.
Hey Sis:
Here is my solution. It's long because I explain in detail.
Richard
Given:
12 identical looking stones and a balance scale.
1 of the stones is an oddball, and does not weigh the sames as the other 11.
Problem:
Using three weighings on the scale, determine the oddball stone and
whether it is heavier or lighter than the others.
Analysis:
Any solution will require breaking the 12 stones an N piles of equal size.
(I can't prove why, but it seems reasonable.)
Candidate starts:
2 piles of 6
3 piles of 4
4 piles of 3
6 piles of 2
The initial measurement must deliver the most amount of information possible.
2 piles of 6 (divide and conquer) is not a solution:
While a simple divide and conquer appears most obvious, it can only be
applied if the type of the oddball (L or H) is known beforehand.
Divide and Conquer:
Assume the oddball is light.
Make two piles of six and compare
- The oddball must be in the light side
Make two piles of three from the light side and compare
- The oddball must be in the light side
Take two stones from the pile of three on the light side and compare
- If equal, the oddball is the one not on the scale
otherwise, the oddball is the stone on the light side
While the approach above is commendable, it will not bear truth in 3 weighings
if the oddball is in fact heavy.
When the oddball is heavy, the comparison of three will show equal weights
implying the heavy stone is in the heavy pile of 6. Now you are
'one measurement behind'. When you split the heavy side into two piles of 3,
you do not know which one is heavier (the one that would necessarily contain
the heavy stone).
4 piles of 3 is not a solution:
After much empirical doodling I find four piles of three can only be solved
if the initial comparison is unequal.
When the first comparison of piles is equal, the oddball must be in one of the other
two piles. Two more measures is insufficient for determining both which and type
of oddball is amongst the remaining six stones.
3 piles of 4 is the solution
Only initial piles of four offers the most amount of logical inference.
Notation:
W1, W2, W3 mean weighing 1, 2 or 3
The weight of the 11 same stones will be called unit weight
Divide the stones into three piles of four
Compare any two piles (name the piles A and B)
Either they are equal or unequal
W1: A = B
The eight stones on the scale are all the same weight
The oddball must be in the pile C (c1 c2 c3 c4) not on the scales.
Compare any two stones from C (c1 c2) with
one more stone from C and one unit stone (c3 1)
Either the are equal or unequal
W2: (c1 c2) equal (c3 1)
The odd ball must be c4 and it must be heavy or light
Compare c4 to a unit stone
They must be unequal
W3: c4 < 1
The oddball is light and is on the scale.
W3: c4 > 1
The oddball is heavy and is on the scale.
W2: unequal, (c1 c2) < (c3 1)
Either c1 or c2 is a light oddball, or c3 is a heavy oddball.
Compare c1 to c2
Either they are equal or unequal
W3: c1 <> c2
The oddball is light and is on the scale.
W3: c1 = c2
The oddball is heavy and is stone c3.
W2: unequal, (c3 1) < (c1 c2)
Either c1 or c2 is a heavy oddball, or c3 is a light oddball.
Compare c1 to c2
Either they are equal or unequal
W3: c1 <> c2
The oddball is heavy and is on the scale.
W3: c1 = c2
The oddball is light and is stone c3.
W1: A <> B
The oddball is in one of the piles on the scale.
The four stones in C, not on the scale, are all unit weight.
Call the light side pile L and the heavy side pile H.
The piles must contain an oddball in one of the following states
Light Heavy
------- -------
Either 1 1 1 L < 1 1 1 1
Or 1 1 1 1 < H 1 1 1
New information can be obtained by manipulating the states,
changing them from either/or to if/then inferences.
State changes that afford information are:
- scale balance in-equality is reversed on next weighing
- scale balance equal on the next weighing
- scale balance in-equality is the same on next weighing
These state changes are accomplished by moving stones
from one side to another, or replacing stones with stones
of unit weight.
After trying many configurations, the following manipulation
yields inference that guarantees determination.
Let's break the manipulation into steps
s1. Remove two stones from L, call them L-off. Call the other two L-on.
s2. Remove three stones from H, call them H-off. Call the other one H-on.
s3. Move two H-Off stones to L.
s4. Move one stone of L-off to H.
s5. Move two stones of unit to H.
Let look at the possible states after each step.
s1. If oddball is light, L-off either contains it or not. (1 new state)
If oddball is heavy, L-off will never contain it.
L 1 . . 1 1 1 1 1 1
1 1 . . 1 L 1 1 1 1
1 1 . . 1 1 H 1 1 1
s2. If oddball is light, H-off will never contain it.
If oddball is heavy, H-off either contains it or not. (1 new state)
L 1 . . 1 1 1 . . . 1 1 1
1 1 . . 1 L 1 . . . 1 1 1
1 1 . . 1 1 1 . . . 1 1 H
1 1 . . 1 1 H . . . 1 1 1
s3. When moving a stone from H-off (1 1 H) to L
either the possible heavy is or is not moved. (1 new state)
Put a * to the right to indicate stones from H-off
L 1 1* 1* 1 1 1 . . . 1 . .
1 1 1* 1* 1 L 1 . . . 1 . .
1 1 1* H* 1 1 1 . . . 1 . .
1 1 1* 1* 1 1 1 . . . H . .
1 1 1* 1* 1 1 H . . . 1 . .
s4. When moving a stone from L-off (L 1) to H
either the possible light is or is not moved. (1 new state)
Put a * to the left to indicate stones from L-off
. 1 1* 1* 1 1 1 *L . . 1 . .
. L 1* 1* 1 1 1 *1 . . 1 . .
. 1 1* 1* 1 L 1 *1 . . 1 . .
. 1 1* H* 1 1 1 *1 . . 1 . .
. 1 1* 1* 1 1 1 *1 . . H . .
. 1 1* 1* 1 1 H *1 . . 1 . .
s5. Show unit stones as =
Necessary scale balance of next step is also shown
. 1 1* 1* 1 1 > 1 *L = = 1 . .
. L 1* 1* 1 1 = 1 *1 = = 1 . .
. 1 1* 1* 1 L < 1 *1 = = 1 . .
. 1 1* H* 1 1 > 1 *1 = = 1 . .
. 1 1* 1* 1 1 = 1 *1 = = H . .
. 1 1* 1* 1 1 < H *1 = = 1 . .
Now compare the two piles
Either they will be equal or unequal
W2: equal
Only two possible states can be equal
. L 1* 1* 1 1 = 1 *1 = = 1 . .
. 1 1* 1* 1 1 = 1 *1 = = H . .
Note the mutually exclusive states of the remaining L-off and H-off stones.
L
H
Compare the remaining L-off stone to a unit stone
Either they are equal or unequal
W3: unequal
The oddball is light and is on the scale.
W3: equal
The oddball is heavy and is the one remaining H-off.
W2: unequal - L is still the light pile
Only two possible states have L still light
. 1 1* 1* 1 L < 1 *1 = = 1 . .
. 1 1* 1* 1 1 < H *1 = = 1 . .
Note the mutually exclusive states of the remaining L-on and H-on stones.
1 L 1
1 1 H
Compare the two L-on stones
Either they are equal or unequal
W3: unequal
The oddball is light and is on the scale.
W3: equal
The oddball is heavy and is H-on.
W2: unequal - L is now the heavy pile
Only two possible states have a 'sign change'
. 1 1* 1* 1 1 > 1 *L = = 1 . .
. 1 1* H* 1 1 > 1 *1 = = 1 . .
Note the mutually exclusive states of the remaining L-swap and H-swap stones.
1* 1* *L
1* H* *1
Compare the two H-swap stones
Either they are equal or unequal
W3: unequal
The oddball is heavy and is on the scale.
W3: equal
The oddball is light and is L-swap.
QED
Google Show me other problem solving techniques for this puzzle.