This is a continuation of the question A balance with three pans, detecting the lightest pan (find the one heavier ball). It was told to me by a friend, Markus Götz, who put it online here: Deviating Ball Puzzles (pdf).
The three-pan balance
Imagine a balance with not two, but three pans. Weightings using the balance follow these rules:
- If there exists a pan that is lighter than each of the other two pans, then this pan goes up and the other two pans go down to a stop. (Note that one cannot see which of the two heavier pans, if any, is the heaviest.)
- If there is no single lightest pan, then nothing happens. (This includes the case of two equally light pans and one heavier pan.)
Let's call this the "lightest-pan-detection-rule" (LPDR).
The problem
You are given n balls, two of which are heavier (not necessarily of the same weight).
1) What is the largest n, so that the heavier balls can be identified with 2 weightings?
2) What is the largest n, so that the heavier balls can be identified with 3 weightings?
The normal (non-heavy) balls are all of the same weight. You are to identify the deviating balls by using the balance a maximum number of weighings stated in the puzzle, weighing only the given balls. You are also to present a method to identify the deviating balls, and explain why the value of n is the largest.
Answer
Updated complete answer
$n=3$ requires 1 weighing.
Put one ball on each pan. The one normal-weight ball will rise and the other two are the heavy ones. There are no other possibilities with $n=3$.
$n=4$ requires 2 weighings.
There are ${4\choose 2} = 6$ possibilities, and each weighing can only distinguish 4 states, so 1 weighing cannot be sufficient for $n=4$.
Put one ball on each pan and keep the 4th ball aside. If one pan rises, then the other two balls are the heavy ones and you are done. Otherwise, you must have weighed 2 light balls and 1 heavy ball, so the 4th ball is the heavy one. Swap it with one of the others. If you swapped it with a light ball, then the other light ball will now rise and you are done. If no ball rises, then you swapped the heavy ball with the other heavy ball. The two balls you swapped are the heavy ones.
$n=5$ cannot be done in two weighings. I could try to prove it, but doing so doesn't answer the question asked, so I won't.
Interestingly, $n=6$ can be done in two weighings. ${6\choose 2} = 15 < 16 = 4^2$, so in theory it could be possible. In practice, it is possible.
Put two balls on each pan, numbering and labeling such that pan A has (1,2), pan B has (3,4), and pan C has (5,6). After noting the result, move the odd balls to the next pan, so now A has (5,2), B has (1,4), and C has (3,6).
If no pan rose on the first weighing, then both heavy balls were on the same pan, making the other two pans of two light balls each weigh the same. On the second weighing, the balls are separated. So if the heavy ones are (1,2), then on the second weghing, pans A and B will each have a heavy and a light ball, and pan C will have two light balls, so pan C will rise. Likewise, (3,4): pan A would rise and (5,6): pan B would rise.
If one of the pans rose on the first weighing, then the two heavy balls were split. So, if pan A rose, then the possibilities are (3,5), (3,6), (4,5), and (4,6). On the second weighing, the results of those would be: (3,5): pan B rises, (3,6): no pan rises, (4,5): pan C rises, (4,6): pan A rises again.
Of the 16 possible pan rising combinations, the one one that cannot occur is no pan rising either time.
Since ${7\choose 2} = 21 > 16$, it clearly is not possible to differentiate $n=7$ in two weighings.
Update
For three weighings, I note that ${11\choose 2} = 55 < 64 = 4^3 < 66 = {12\choose 2}$, so the theoretical maximum for three weighings is 11 balls. This maximum cannot be achieved.
Proof that it is possible to find the heaviest two balls out of $n=9$ balls with three weighings:
First weigh (1,2,3) vs (4,5,6) vs (7,8,9).
Then weigh (1,8,6) vs (4,2,9) vs (7,5,3).
Then weigh (1,2,6) vs (4,5,9) vs (7,8,3).
Each of the ${9\choose 2} = 36$ possibilities gives a different set of answers. Here's a partial enumeration:
(1,2): NCN (1,3) NBB (2,3) NAB
(1,4) CCC (1,5) CBC (1,6) CNN (1,7) BBB (1,8) BNB (1,9) BCC
(2,4) CNC (2,5) CAC (2,6) CCN (2,7) BAB (2,8) BCB (2,9) BNC
(3,4) CAA (3,5) CNA (3,6) CBB (3,7) BNN (3,8) BBN (3,9) BAA
Any other combination is a rotation of one of the above and would also yield a unique pattern.
For $n=10$, if you put 3 balls on each pan, there are $18 > 16$ possibilities where no pan rises, 9 where both heavy balls are on one pan, and 9 where one heavy ball is left out and the other is unknown.
If you put 3 balls on pans A & B and 4 balls on pan C, then if pan A rises, you have 24 possibilities: 12 where one heavy is on B and one on C, 3 where both are on B, and 9 where one heavy is on A and one on B, but the one on B is heavier than the one on A (and the one on A weighs less than 2 normal ones). Note there are also 24 possibilities where pan B will rise, but 9 of those are overlap, but with the relative weights of the heavy balls switched. There are likewise 15 possibilities where no pan rises: 6 for both on pan C and 9 where one is on A and one is on B and the two heavy ones weigh the same. There are even 9 possibilities where pan C rises: one heavy ball on each of A & B, and both weigh more than two normal balls.
If you put 2 balls on each pan, there are 33 cases where no pan rises; 3 where both heavy balls are on the same pan, 6 where neither heavy ball is weighed at all, and 24 where one heavy ball is weighed and the other is not.
If you put 2, 2, and 3 balls, and pan A rises, then you have 17 possibilities: 1 where both heavy ones are on pan B, and 16 possibilities where the heaviest one is on pan B and the other heavy one is any of the other eight.
In summary, you cannot solve for $n=10$ with three weighings. Since the difficulties lie with not being able to distribute all the balls equally, adding an 11th ball will not make it easier. And, as stated above ${12 \choose 2} = 66 > 64 = 4^3$, so you cannot possibly weigh 12 or more in three weighings.
Thus $n=9$ must be the maximum for three weighings.
No comments:
Post a Comment