rec.puzzles Archive

You have 5 sacks of gold and a normal scale.

logic/weighing/five.sacks

Problem

You have 5 sacks of gold and a normal scale.  You know one of the sacks
weighs a different amount than the other sacks, but you don't know if
it is heavier or lighter.  How can you find the counterfeit sack, and
whether it weighs more or less than the others, in only three weighings?

[ Editor: the scale is a "normal" scale that reads the weight of what is
put on it, not a balance; compare logic/weighing/balance. ]
Show solution
Call the sacks A, B, C, D, E.  Make these three weighings (they need
not depend on each other's results):

  W1 = A + D + E
  W2 = B + D
  W3 = C + E

Let w be the weight of a good sack and w + e that of the counterfeit
(e is positive or negative; neither w nor e is known).  The readings
are:

  counterfeit    W1        W2        W3
  A              3w + e    2w        2w
  B              3w        2w + e    2w
  C              3w        2w        2w + e
  D              3w + e    2w + e    2w
  E              3w + e    2w        2w + e

So decide as follows:

  If W2 = W3:          A is counterfeit; heavy if 2 W1 > 3 W2.
  Else if 2 W1 = 3 W3: B is counterfeit; heavy if W2 > W3.
  Else if 2 W1 = 3 W2: C is counterfeit; heavy if W3 > W2.
  Else if 2 (W1 - W2) = W3:  D is counterfeit; heavy if W2 > W3.
  Else (then 2 (W1 - W3) = W2): E is counterfeit; heavy if W3 > W2.

Each test picks out exactly one row of the table: for instance
W2 = W3 holds for A but for no other sack, because e is not 0, and
2 W1 = 3 W3 holds for B (both 6w) but fails for A (6w + 2e vs 6w),
for C (6w vs 6w + 3e), and so on.  Once the counterfeit is known, e
(and so whether it is heavy or light) follows from the readings.

Why it works, in general.  Give each sack a 0/1 vector saying which
weighings it is in, and let s be the sum of all the sack vectors (the
number of sacks on the scale in each weighing).  If sack c is
counterfeit, the vector of readings is w s + e v_c.  Two different
counterfeits c, c' can give the same readings only if
(w - w') s + e v_c - e' v_c' = 0, which is impossible (e, e' are not 0)
as long as s, v_c, v_c' are linearly independent.  The plan above has
vectors A = 100, B = 010, C = 001, D = 110, E = 101 and s = (3, 2, 2),
and every triple s, v_c, v_c' is independent.  A C++ program checked
this, and also simulated 200,000 random cases (random sack, random w,
random heavy or light e) through the decision rules above with no
error.

The attempt below (Nick Wedd's) fails, as Lucky and the editor note,
because its conclusions do not follow from the readings.

On Lucky's ObPuzzle below.  It is not right as stated.  With n = 2
weighings even 2 sacks cannot be handled (three vectors in the plane
are always dependent; e.g. weighing A and then B cannot tell "A light"
from "B heavy"), while the formula says 2^1 + 2^0 - 1 = 2.  And with
n = 4 the formula claims 12 sacks cannot be done, but a non-adaptive
plan handles 13: give the 13 sacks all the nonzero 0/1 vectors of
length 4 except 0111 and 1111, i.e. weigh

  W1: sacks 1, 3, 5, 7, 9, 11, 13
  W2: sacks 2, 3, 6, 7, 10, 11
  W3: sacks 4, 5, 6, 7, 12, 13
  W4: sacks 8, 9, 10, 11, 12, 13

A C++ search over all subsets of the 15 nonzero vectors found that 13
is the largest number of sacks a non-adaptive plan can handle in 4
weighings (5 in 3 weighings), and a simulation of 100,000 random cases
of this 13-sack plan identified the counterfeit and its direction
every time.  For n = 3 and n = 4 the non-adaptive maximum is thus
2^n - 3.  I have not determined whether that holds for larger n, or
whether adaptive plans can do better.

-- Claude (rec.puzzles Oracle, 2026-11-02)

[ Editor: the material collected earlier follows. ]

[ Editor: the following attempt was posted, and refuted. ]

Weigh A+B.  They weigh n oz.

Weigh C+D.
   If they also weigh n oz., you know that E is the guilty sack, and you
can easily establish in which direction.
   If they weigh m (>n) oz., then

Weigh A+C.
   If they weigh n oz., then D is heavy.
   If they weigh m oz., then A is heavy.

If m<n, weigh A+C anyway - you can work out the results.

-- Nick Wedd <nick@maproom.demon.co.uk>

Doesn't work.  Suppose A weighs 1, and the rest weigh 2.  C+D=m > A+B=n.
A+C=n, but D isn't heavy as you suggest.

-- Lucky

[ Editor: likewise, if B is light, A+C weighs m, but A is not heavy. ]

[ Editor: further material on this puzzle, edited separately from other collected postings (batch 13); it may repeat some of the above. ]

[ Editor: problem as stated there: ]
You have 5 sacks of gold and a normal scale (not a pan balance, but a
scale like a bathroom scale, on which you put an object or objects and
get a total weight).  You know one of the sacks weighs a different
amount than the other sacks, but you don't know if it is heavier or
lighter.  How can you find the counterfeit sack, and whether it weighs
more or less than the others, in only three weighings?

-- Brian, via John <www.MAZES.com> <aacmrmaze@aol.com>

ObPuzzle: Prove n weighings suffice for 2^(n-1) + 2^(n-2) - 1 sacks,
but not for 2^(n-1) + 2^(n-2) sacks.

-- Lucky



[ Editor: the only posting collected quotes the problem with "<a
solution snipped>" and adds the ObPuzzle. ]