7
$\begingroup$

You are given 14(*) scales that look and feel identical.

  • The scales are 2-pan scales. When you put stuff on each pan, the scale indicates whether both sides balance, and if not, which side is heavier.

  • The scales are light and foldable. You could fit any subset of them on either pan, should you want to do so. You cannot put a scale on its own pan.

  • All scales are identical and work well. Except for one scale that is fake. The fake scale is slightly heavier or lighter than the others, and its readings are unreliable.

  • Your mission is to identify the fake scale in 4 weighings.

  • I am sure someone here would come up with this kind of twisted scenario, so: there is no simultaneous multi-level weighing with one or multiple scales being weighted while at the same time weighing other scales. You operate one scale at a time.

  • I just made up this problem. If you can do more than 14(*) scales, it is even better.

(*) Update: the current record is 39.

$\endgroup$
1

1 Answer 1

4
$\begingroup$

I think it is possible with this many scales:

39

Procedure:

Label 26 of the other scales using the letters A to Z, and label the remaining 13 scales from 0 to 12. For the first test, use scale 0 to test A through M against N through Z. If the scale is balanced, then the fake scale is either scale 0 or one of the other numbered scales. If the scale is unbalanced, the fake scale is either scale 0 or one of the lettered scales. Either way, we have identified a bunch scales that we know must be good.

If the first test was balanced, this reduces to a well known balance puzzle (e.g. "Twelve balls and a scale") where we can use a reliable (lettered) scale to find the outlier from a set of 13 objects. (If we like, we can also use one of the other known good scales, e.g. scale A in the solution.) For example, our additional tests can be A, 0, 3, 4, 5 vs 6, 9, 10, 11, 12; A, 1, 3, 9, 10 against 4, 7, 8, 11, 12; and A, 2, 7, 9, 11 against 5, 6, 8, 10, 12. The construction of such a solution can be undertaken in a manner analogous to the construction outlined below (but I've just taken this example from Wikipedia).

If the first test was unbalanced, things are slightly more complicated. We don't want to simply reduce to a known solution, because we already have some information about the lettered scales from the first test; but we will proceed along the same lines as well-known solutions. For each possible outcome among our tests, we will design the tests so that a particular object is the outlier for that outcome. But; since we don't known if the fake scale is heavier or lighter, and in any outcome where we have tested and identified the fake scale we have also determined whether it is heavier or lighter; if all the outcomes of the tests are reversed, it must be that the same scale is fake but of opposite weight. (There is no case where all tests are balanced because our first test was already unbalanced.) We can also have one object that is not included in any test and for this object, we won't be able to tell (assuming it's fake) if it is heavier or lighter, but by process of elimination, we will know that it must be fake. Since we have already included all the lettered scales in our first test, we will choose scale 0 to be the object that is excluded from all tests.

So, e.g., we can assign results to object as follows (where < indicates the left side is lighter, > indicates the right side is lighter, and = indicates the scale is balanced for each test) (the first test is always < here, because a test where the first is > is the reverse of some test where the first is <):

 <<<< : A
 <<<= : B
 <<<> : C
 <<=< : D
 <<== : V
 <<=> : W
 <<>< : X
 <<>= : Y
 <<>> : Z
 <=<< : J
 <=<= : K
 <=<> : L
 <==< : M
 <==> : N
 <=>< : O
 <=>= : P
 <=>> : Q
 <><< : R
 <><= : S
 <><> : T
 <>=< : U
 <>== : E
 <>=> : F
 <>>< : G
 <>>= : H
 <>>> : I 
Then, our tests would be ABCDRSTU vs VWXYZEFGHI, ABCXYZJKLOPQ vs RSTGHI, and ADWZJMNQTG vs CXLORUFI. (We have no flexibility as we've already specified the first test.) Normally, we'd have to make sure we have the same number of objects on each side of each test (by more intelligently assigning outcomes to objects), but here we can be sloppy and just say we'll fix this by including the appropriate number of known good scales on the deficient side. (None of these tests are so unbalanced that we'll run out of good scales.)

$\endgroup$
3
  • 1
    $\begingroup$ Looks like my solution was a bit naive and far from optimal. But I will wait a while, see if someone can improve on it. $\endgroup$
    – Florian F
    Jul 8 at 7:47
  • 1
    $\begingroup$ I think this is the best you can do. I almost posted that if you would specify either heavy or light (since your post never asks us to find out whether the odd scale is heavier or lighter), that we could do 81 scales, but the "one scale being fake and not weighing things correctly" restriction still makes 39 the best (Someone correct that statement if it is wrong). $\endgroup$
    – JLee
    Jul 8 at 12:45
  • 1
    $\begingroup$ Well, if JLee tried and didn't find a better solution, then it is probably optimal. :-) $\endgroup$
    – Florian F
    Jul 10 at 20:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.