Solution to Puzzle No. 7
Submitted by plusadmin on May 1, 1999For the question see Puzzle No 7  The Great Weights Puzzle in issue 7.
A solution in 4 moves?
When presented with this problem, many people decide that the minimum number of weighings is 4. There is certainly a simple process that will give the answer in 4 weighings.
First of all, divide the weights into three groups. Let group A be weights {1,2,3,4}, group B be weights {5,6,7,8} and group C be weights {9,10,11,12}.
Now use the following algorithm:
Step 1:
First, weigh group A (left) against group B (right).
Now, the left hand side of the scale might be heavier (H), or the left hand might be lighter (L), or they might have the same weight (S), giving the following information:
Outcome  Implication 
H  A heavier or B lighter; C normal 
L  A lighter or B heaver; C normal 
S  C lighter or heavier; A and B normal 
Step 2:
Now weigh group A (left) against group C (right), giving the following information:
Outcome  Implication 
HH  A heavier 
HL  (impossible) 
HS  B lighter 
LH  (impossible) 
LL  A lighter 
LS  B heavier 
SH  C lighter 
SL  C heavier 
SS  (impossible) 
So, after two weighings, we know which group of 4 the different weight is in, and whether it is heavier or lighter. Now things are easy:
Step 3:
Choose the group of 4 that has the different weight in it. Put two weights from this group on either side of the scale. From step 2, you know whether the different weight is heavier or lighter. If it is heavier, choose the two weights on the heavier side; if you know it is lighter, choose the two weights on the lighter side.
Step 4:
Take the two weights from step 3, and put one on either side of the scale. If you know the different weight is heavier, choose the heavier weight; if it's lighter, choose the lighter weight. You're done! You've found the oddweightout, and whether it is heavier or lighter, in 4 steps.
Doing it in 3!
The 4step solution is quite elegant (and if you found it, well done!), but it's not the best solution! In fact, it's possible to solve the weights puzzle in only three weighings.
There are 24 possible configurations for this puzzle: for each of the 12 weights, there is a configuration where it is heavier than the others, and a configuration where it is lighter than the others.
Now, there are three possible outcomes of any particular weighing (where a weighing is defined as a measurement where both sides of the scales have the same number of weights on them): the left side of the balance is heavier (L), the right side of the balance is heavier (R), or both sides are the same (S). If we perform a number of weighings one after the other, then we will have a list of outcomes  for example, we might have a "left heavier" outcome followed by a "right heavier" outcome, giving LR.
So, how many different possible lists of outcomes are there for a given number of weighings, in principle? The number of outcomes obviously goes as 3 to the power of n (where n is the number of weighings), since for every weighing there are three possible outcomes:
Weighings  Outcomes 
1  3 ( L, R, S ) 
2  9 ( LL, LR, LS, RL, RR, RS, SL, SR, SS ) 
3  27 ( LLL, LLR, LLS, LRL , ...) 
4  81 (LLLL, LLLR, LLLS, LLRL , ...) 
Now, as the above table shows, there are 27 possible outcomes for a sequence of three weighings. Since there are only 24 configurations for the puzzle, if we can map a different weighing outcome to each configuration (with three leftover outcomes not used), we can solve the puzzle in only three weighings!
Mapping a configuration to a particular weighings outcome gives us information about how to load up the scales at each step. For example, let's say we were to map the configuration where weight number 1 is heavier than the rest  call it configuration 1,H  to the weighing outcome HLS.
For outcome HLS to be produced for configuration 1,H, weight 1 would have to be on the left hand side of the scales in the first weighing, on the right hand side in the second weighing, and not on the scales at all in the third weighing.
Now, observe that if weight 1 were actually lighter than the rest, the mirror outcome, LHS, would be produced. In other words, the weighings outcomes are not independent of each other: each outcome (excepting SSS, of course) has a "mirror pair", like HLS and LHS in the above example. These related pairs are shown in the table below, which contains all 27 possible threeweighing outcomes.
Outcome  Mirror outcome 
HHH  LLL 
HHL  LLH 
HLH  LHL 
HLL  LHH 
HHS  LLS 
HSH  LSL 
HSS  LSS 
SHS  SLS 
SHH  SLL 
SSH  SSL 
SLH  SHL 
HSL  LSH 
HLS  LHS 
SSS   
Therefore, when arranging our mappings, we need to map a particular pair of configurations n,H and n,L (n = fixed, range 112) to a particular mirror pair of outcomes.
Now, we need to leave out three of the 27 possible weighings outcomes, since we only need 24. Let's omit SSS since it's not useful  if we got outcome SSS, all we'd know is that the different weight was one of the weights we hadn't used in the weighings. Let's also omit the mirror pair HHH /LLL. This leaves twelve remaining outcome pairs, to be assigned to the twelve configuration pairs.
Let's try the obvious thing first, and assign the first of each outcome pair to the configuration where the different weight is heavier, and the second of each outcome pair to the configuration where the different weight is lighter:
Outcome / configuration  Mirror outcome / configuration 
HHL / 1,H  LLH / 1,L 
HLH / 2,H  LHL / 2,L 
HLL / 3,H  LHH / 3,L 
HHS / 4,H  LLS / 4,L 
HSH / 5,H  LSL / 5,L 
HSS / 6,H  LSS / 6,L 
SHS / 7,H  SLS / 7,L 
SHH / 8,H  SLL / 8,L 
SSH / 9,H  SSL / 9,L 
SLH / 10,H  SHL / 10,L 
HSL / 11,H  LSH / 11,L 
HLS / 12,H  LHS / 12,L 
If we use these mappings to work out which weights go on which side of the scale for each mapping, we have the following:
Weighing Left side Right side    1. 1 2 3 4 5 6 11 12  2. 1 4 7 8 2 3 10 12 3. 2 5 8 9 10 1 3 11
Oops! As you can see, the scales are unbalanced in the first and third weighings: there are different numbers of weights on the left and right sides. Let's try to fix the balance by swapping mappings within the pairs.
Configuration pair 5 is currently mapped like this:
{HSH / 5,H} and {LSL / 5,L}.Let's reverse it:
{HSH / 5,L} and {LSL / 5,H}.
In practice, this means that weight 5 moves to the opposite side of the scales in every weighing it appears in:
Weighing Left side Right side    1. 1 2 3 4 6 11 12 5 2. 1 4 7 8 2 3 10 12 3. 2 8 9 10 1 3 5 11
We're still unbalanced  let's try reversing configuration pair 2, from
{HLH / 2,H} and {LHL / 2,L}to
{HLH / 2,L} and {LHL / 2,H}.
This gives us:
Weighing Left side Right side    1. 1 3 4 6 11 12 2 5 2. 1 2 4 7 8 3 10 12 3. 8 9 10 1 2 3 5 11
Still unbalanced. Let's reverse pair 4, from
{HHS / 4,H} and {LLS / 4,L}to
{HHS / 4,L} and {LLS / 4,H}.
This gives us:
Weighing Left side Right side    1. 1 3 6 11 12 2 4 5 2. 1 2 7 8 3 4 10 12 3. 8 9 10 1 2 3 5 11
Getting close now! Let's reverse pair 11, from
{HSL / 11,H} and {LSH / 11,L}to
{HSL / 11,L} and {LSH / 11,H}
This gives us:
Weighing Left side Right side    1. 1 3 6 12 2 4 5 11 2. 1 2 7 8 3 4 10 12 3. 8 9 10 11 1 2 3 5
Great! The scales are now balanced, with each weighing involving four weights on the left and four weights on the right. Because of our mappings, we know what weighings outcome relates to what problem configuration:


Voila! We can now reliably ascertain which weight is different, and whether it is heavier or lighter, in 3 weighings!
If you got this one out, congratulations! If you got it out using a very different line of reasoning to the one shown here, do let us know how you did it.