Skip to main content
Home
plus.maths.org

Secondary menu

  • My list
  • About Plus
  • Sponsors
  • Subscribe
  • Contact Us
  • Log in
  • Main navigation

  • Home
  • Articles
  • Collections
  • Podcasts
  • Maths in a minute
  • Puzzles
  • Videos
  • Topics and tags
  • For

    • cat icon
      Curiosity
    • newspaper icon
      Media
    • graduation icon
      Education
    • briefcase icon
      Policy

      Popular topics and tags

      Shapes

      • Geometry
      • Vectors and matrices
      • Topology
      • Networks and graph theory
      • Fractals

      Numbers

      • Number theory
      • Arithmetic
      • Prime numbers
      • Fermat's last theorem
      • Cryptography

      Computing and information

      • Quantum computing
      • Complexity
      • Information theory
      • Artificial intelligence and machine learning
      • Algorithm

      Data and probability

      • Statistics
      • Probability and uncertainty
      • Randomness

      Abstract structures

      • Symmetry
      • Algebra and group theory
      • Vectors and matrices

      Physics

      • Fluid dynamics
      • Quantum physics
      • General relativity, gravity and black holes
      • Entropy and thermodynamics
      • String theory and quantum gravity

      Arts, humanities and sport

      • History and philosophy of mathematics
      • Art and Music
      • Language
      • Sport

      Logic, proof and strategy

      • Logic
      • Proof
      • Game theory

      Calculus and analysis

      • Differential equations
      • Calculus

      Towards applications

      • Mathematical modelling
      • Dynamical systems and Chaos

      Applications

      • Medicine and health
      • Epidemiology
      • Biology
      • Economics and finance
      • Engineering and architecture
      • Weather forecasting
      • Climate change

      Understanding of mathematics

      • Public understanding of mathematics
      • Education

      Get your maths quickly

      • Maths in a minute

      Main menu

    • Home
    • Articles
    • Collections
    • Podcasts
    • Maths in a minute
    • Puzzles
    • Videos
    • Topics and tags
    • Audiences

      • cat icon
        Curiosity
      • newspaper icon
        Media
      • graduation icon
        Education
      • briefcase icon
        Policy

      Secondary menu

    • My list
    • About Plus
    • Sponsors
    • Subscribe
    • Contact Us
    • Log in
    • Solution to Puzzle No. 7

      1 May, 1999
      May 1999

      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.

      • Log in or register to post comments

      Anonymous

      3 December 2013

      Permalink
      Comment

      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

      • Log in or register to post comments
      University of Cambridge logo

      Plus Magazine is part of the family of activities in the Millennium Mathematics Project.
      Copyright © 1997 - 2025. University of Cambridge. All rights reserved.

      Terms