3 Weighings ProblemDate: 12/09/97 at 12:34:20 From: Paul Midkiff Subject: 3 weighings problem Dear Dr. Math, Here is the problem I've been challenged with: You have 12 balls that all look and weigh the same except one. You have a balance scale to weigh them on. You get three weighings and you must tell which ball is different and whether it is heavier or lighter than the other 11. I see how I can determine which is the odd ball (no pun intended) in three weighings but I don't see how to tell whether it's heavier or lighter. My challenger swears to me it is solvable. I'm beginning to have my doubts. Can you help? Date: 12/09/97 at 14:49:06 From: Doctor Tom Subject: Re: 3 weighings problem Hi Paul, It's a tough problem. Here's how to solve it in the general case (i.e. for 4 weighings, 5 weighings, et cetera): Here's the algorithm for solving the 12 balls in three weighings problem. It also happens to solve the 3 balls in two weighings or 39 balls in 4 weighings, or 120 balls in 5 weighings or ..., problems. First, list all 3 digit combinations of 0, 1, and 2: 000 100 200 001 101 201 002 102 202 010 110 210 011 111 211 012 112 212 020 120 220 021 121 221 022 122 222 For the 4 weighing problem, list all 4 digit combinations, and so on. Next, cross out all sets with identical digits (000, 111, 222), and also throw out all whose first digit change (reading from left to right) is not 01, 12, or 20. In other words, 112 is left in because the first change is from 1 to 2, but 212 is eliminated, since the first change is from 2 to 1. This leaves: (a) 001 (b) 010 (c) 011 (d) 012 (e) 112 (f) 120 (g) 121 (h) 122 (i) 200 (j) 201 (k) 202 (l) 220 where a, b, ..., l are the balls. Now, for the first weighing, weigh all the balls with a 0 in their first position against all the balls with a 2 in the first position, in other words, (a, b, c, d) are weighed against (i, j, k, l). If the balls with the 0 are heavier, write down 0; if the balls balance, write 1, otherwise; write 2. Next, weigh all balls with a 0 in the second position against all balls with a 2 in the second position (a, i, j, k) against (f, g, h, l), and write down the digit corresponding to the result of the weighing, and do it again for the third position in the third weighing. As an example, suppose ball f (120) is heavy. In the first weighing, f is not involved, so write down 1. Next, (f, g, h, l) -- the "2" balls are heavier than (a, i, j, k) so write down 2. Finally, in the weighing (b, f, i, l) versus (d, e, h, k), the "0" side (b, f, i, l) is heavier, so write down a 0. You have written "120" - the code for ball f - so f is the heavy ball. If you find that the combination you write down is not in the list, say 211, then change the 2s to 0s, the 0s to 2s, and leave the 1s alone, giving 011. This is ball c, but since you had to flip the digits, ball c is lighter. With N weighings, there are 3^N combinations, of which we eliminate 3 and cut the remainder in half, so for 4 weighings, one can distinguish among (3*3*3*3-3)/2 = 39 balls, etc. -Doctor Tom, The Math Forum Check out our web site! http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/