weighing - A balance with three pans, detecting the lightest pan (find the one heavier ball)

This is a continuation of the question A balance with three pans, detecting the lightest pan (find the one lighter 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).

You are given n balls, one of which is heavier. What is the largest n, so that the heavier ball can be identified with at most k weightings? (k >= 1)

The "normal" balls are all of the same weight. You are to identify the deviating ball 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 ball.

Answer

If all three pans have the same number of balls, at most one will be heavier and the other two the same, so the pans will never move. However, if there are $x$ balls on two pans and $x+1$ on the third, then the scale works like a normal 2-pan scale, comparing the two pans with $x$ balls. If the heavier ball is one one of the two pans with $x$ balls, the other one will rise. If it is on the third pan (or anywhere else), then no pan will rise. This matches the behavior of a normal 2-pan scale.

If you have three candidate heavy balls and one or more balls that have been eliminated (I'll call these "ringers"), then you can put one candidate on each pan and also one ringer on the third pan. If one pan goes up, then the other pan with 1 ball holds the heavy one. If neither goes up, then the one with the ringer is the heavy one.

So, with a ringer, you can differentiate up to 3 balls in one weighing. Similarly, if you put $x$ candidate balls on each pan and add a ringer to one pan, then you can determine which pan contains the heavy ball. Iterating, you can differentiate $3^k$ balls in $k$ weighings, if you have a ringer to start with.

• $k=1$: $n=1$

Without a ringer, you can't differentiate anything in 1 weighing.

• $k=2$: $n=7$

Put 2 balls on A and B; put 3 balls on C. After the first weighing you have at most 3 candidates and at least one ringer. The second weighing will suffice. So for k=2, n=7 is the maximum.

• General $k$: $n=3^k-2$.

Put $3^{k-1}-1$ balls on A and B, and $3^{k-1}$ on C. This weighing leaves you with at most $3^{k-1}$ balls and at least one ringer. Iterate through k weighings.

Since the maximum number of balls that you can differentiate in $k-1$ steps is $3^{k-1}$, pan C cannot have more than that number, and the other two pans cannot have more than $3^{k-1}-1$, so the total cannot be more than $3^k-2$.