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. ]