For 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)

(HH stands for "H in the first weighing, and then another H in the second weighing", and so on).

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 odd-weight-out, and whether it is heavier or lighter, in 4 steps.

---

Doing it in 3!

The 4-step 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 left-over 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 three-weighing 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 1-12) 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:

Outcome Configuration HHL 1 heavier LHL 2 heavier HLL 3 heavier LLS 4 heavier LSL 5 heavier HSS 6 heavier SHS 7 heavier SHH 8 heavier SSH 9 heavier SLH 10 heavier LSH 11 heavier HLS 12 heavier

Outcome Configuration LLH 1 lighter HLH 2 lighter LHH 3 lighter HHS 4 lighter HSH 5 lighter LSS 6 lighter SLS 7 lighter SLL 8 lighter SSL 9 lighter SHL 10 lighter HSL 11 lighter LHS 12 lighter

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.