2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I do not think that you could find a single heavy ball with such a 3-pan balance. You need at least 2 heavy balls. $\endgroup$ – Moti Jun 24 '15 at 4:34
  • $\begingroup$ @Moti You may put an arbitrary number of balls on each pan. With this, it is possible to find a single heavy ball (in most cases). $\endgroup$ – Christian Semrau Jun 24 '15 at 4:52
  • $\begingroup$ But not in all cases. And this is my point. $\endgroup$ – Moti Jun 24 '15 at 19:29
  • $\begingroup$ Indeed, finding a single heavy ball is not possible when you have 2 or 3 balls. I updated the note in my question to add this restriction. Of course, if you manage to solve this question for n=2 (which is possible), any number of weighings is better than the naive approach. :-) $\endgroup$ – Christian Semrau Jun 25 '15 at 12:45
  • $\begingroup$ I do not see a way to find a single ball with any weighing - the ball will be "masked" by any two regular balls. You must have at least two heavy balls to 3 Pan balance useful. $\endgroup$ – Moti Jun 26 '15 at 15:28
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ That is correct! Great to see the question solved after more than a year. $\endgroup$ – Christian Semrau Feb 11 '17 at 15:43
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You already know beforehand which heap is normal, so the first weighing is not required. I reworded the question to make that clearer. $\endgroup$ – Christian Semrau Aug 2 '15 at 17:26
  • $\begingroup$ If I understand correctly, you test each of the two heavy-ball-containing heaps separately. So you solved the puzzle of finding one heavy ball in a heap with additional normal balls, which requires around log_3(n) weighings. But indeed one can do better with two such heaps! Compare your first weighing: You had two heavy balls, and still got a useful result in every case. $\endgroup$ – Christian Semrau Aug 2 '15 at 17:30
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This procedure does find the two heavy balls. It is in general not better than the naive approach described in the question, so I'll wait for improved solutions. $\endgroup$ – Christian Semrau Jul 3 '15 at 6:14

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.