Solution to Puzzle No. 7

May 1999

For the question see Puzzle No 7 - The Great Weights Puzzle in issue 7.

Once you've read the solution below, you can also try out our interactive checker to prove to yourself that it works.


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!

Are you still unconvinced? Why not try it out for yourself?

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.

Comments

Balance scale puzzle

I was offered this puzzle verbally by a Captain I was flying with on a trip (I'm a copilot, it was a 2 man crew on a domestic trip). I was told to find the solution in three moves, so never deliberately sought a 4 move solution. And I had to do it without any props, as it was a verbal challenge.

I set out with crazy diagrams that looked nothing like yours so I'm not sure if my solution is entirely different or not! I can say, my mindset was totally different. It quickly dawned on my that I had to garner AS MUCH AS POSSIBLE per weighing. That meant finding a grouping that eliminated as many pieces as possible per move. Grouping them into three groups meant an equal weighing eliminated eight, or an unequal weighing eliminated four.

That spawned two new challenges. Finding and determining in two moves, the odd piece from four. Or, find and determine in two, the odd piece from eight...

The first was easy, the second then starts to look like your reasoning... I need to find my notes and try to diagram them digitally to be sure, it's been a while, I just found this site!

A fantastic puzzle, I intend to build one to put on my coffee table.

Thanks,

Mike Danford
n0kkj@yahoo.com