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

Question

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 1

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.

Answer 2

The third if the three original heaps contains only normal balls. Place these balls in a "normal ball" discard pile, but add either zero, one or two of these balls to each of the remaining heaps so that (n+x)/3 has a remainder of 1.

Take one of these slightly increased original heaps and divide it into three smaller piles, each equal to (n+x-1)/3 with the single remainder in any of the piles. One of these piles must contain one heavy ball.

Re-weigh these and either 1. The heavy ball is in the largest pile, so the scales do not move, or 2. The heavy ball is in one of the smaller piles, so the other smaller pile rises. In case 1, both the small piles can be added to the discard pile. In case 2 (the worst case) the lighter of the smaller piles can be added to the discard.

Again top up the remaining balls from the discard pile to give a number divisible by 3 with a remainder of 1 and repeat the process until you get down to piles of size 1.

Find the heavy ball by weighing two normal balls in one pan against two pans each containing one of the unclassified balls. If nothing moves, then all balls are normal and can be discarded. If one pan moves, the other single pan contains the heavy ball.

Repeat these steps for the other original heap.

Given the arbitrary weight of the heavier balls, I don't believe anything can be gained by combining any of the balls from the two unprocessed original heaps as there will always be the risk of discarding a k-sized pile containing the lighter of the two heavier balls in a comparison against a k-sized pile including the heavier of the two heavy balls and a k+1 sized pile of normal balls.

Answer 3

I have a solution where the total number of weighings is equal to the sum of the squares of the prime factors of n.

Divide each n-ball heap into equal-sized piles. The number of piles should be as small as possible. Of the piles, we need to which two contain the heavy balls. For each pair of piles, place them on separate pans of the balance. The third pan should be filled with normal balls. If we have both heavy balls on the scales, then they will tip, otherwise they will not.

Once we know which piles contain the heavy balls, we can use these for the next iteration. We repeat the process until our piles are of size 1, and we know which balls are heavy.