weighing - Two heaps each with a heavy ball, and a 3-pan balance

The three-pan balance

Imagine a balance with not two, but three pans. Weighings 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, one after the other, three heaps of n identical looking balls. (3n balls in total.) The first two heaps each contain one heavier ball. The third heap only contains normal balls. Your task is to find the two heavy balls using a 3-pan balance. How many weighings are required to identify the two heavy balls without needing to guess?

The normal (non-heavy) balls are all of the same weight. The heavy balls may or may not have the same weight. You should not assume that they are only slightly heavier, i.e. your solution should work even if one heavy ball is twice as heavy as a normal ball.

You may weigh only the given balls, and you may put an arbitrary and possibly different number of balls on each pan. Please present a method to identify the heavy balls, and explain why the number of weighings is minimal.

Note

This problem arises when you try to identify two heavy balls among 3n balls, and put n balls on each pan, and find that one pan is the lightest.

As we saw in a previous puzzle, when you want to find the one heavy ball in one of our n-ball heaps alone, for n > 3, you can do it in no more than $\lceil\log_3(n+2)+1\rceil$ weighings. So naively, you can solve the problem in twice that many weighings. Can you do better, by utilizing balls from both heaps, and the extra normal-only heap?

Answer

The number of weighings required is $\lceil{\log_2 n}\rceil$.

Label the heaps as red, blue, and green, with the green heap being the normal ones. Put $k = \lceil {n\over 2}\rceil$ red balls on pan A, and the rest of the red on pan B. Put $k$ blue on pan B, the rest on pan C. Put $k$ green balls on pan C, the rest on pan A. All the pans have the same number of balls on them, so the only weight differences will be due to the heavy balls.

If no pan rises, both heavy balls are on the same pan. The two heavy balls are one red, one blue, and only pan B holds balls of both those colors. If pan A rises, then the red heavy ball must be on pan B and the blue heavy ball must be on pan C. No matter what happens, you have divided the heaps in half (possibly rounding up if $n$ was odd).

Repeat the process with the smaller heaps until each heap is size 1. This takes at most $\lceil \log_2 n\rceil$ weighings.

Note that for $n=1$ we get $\log_2 1 = 0$, which is correct; we don't need to do any weighing to identify which ball in each heap is heavy, since each heap has only one ball.

Proof of minimality The number of different results of a weighing is 4, so the number that can be differentiated in $k$ weighings is $4^k$. If $n = 2^k$, then the number of possible starting states is $n^2 = {(2^k)}^2 = {(2^2)}^k = 4^k$. The algorithm above meets that limit.