4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I do not know if it makes a difference to the puzzle, but: You may not assume that the heavier balls are just slightly heavier than a normal ball, but they may be arbitrarily heavy (even more than n times a normal ball). Imagine having an assistant move the balls, so that you never get to tough them and feel their weight. $\endgroup$ – Christian Semrau Jun 5 '15 at 7:36
  • $\begingroup$ Please to clarify: Are all three pans on the scale at the same time (I.E., Is it a classic hanging balance with 3 arms in a triangular pattern instead of just 2) or can the scale only hold 2 pans at a time and you must change them out? $\endgroup$ – Engineer Toast Jun 5 '15 at 14:46
  • $\begingroup$ Please to clarify: Does the LPDR apply no matter the weight of the balls on the scales? I.E., if there is a single lightest pan, it will go up no matter how much weight is placed upon it? $\endgroup$ – Engineer Toast Jun 5 '15 at 14:47
  • $\begingroup$ All three pans are on the balance at the same time. A hanging balance with 3 arms would behave different from this LPDR balance, so instead imagine three pans in a row, sitting on a hidden weighting mechanics, like so: three-pan balance $\endgroup$ – Christian Semrau Jun 5 '15 at 16:04
  • $\begingroup$ The LPDR always applies: As long as there is a single lightest pan, it will go up, no matter how many balls are on each pan. If you think about it, "this is not how physics works", but I think it's a valid imaginary machine. :-) $\endgroup$ – Christian Semrau Jun 5 '15 at 16:09
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Wow! I never tried to find predetermined weighing patterns (that do not depend on previous weighing results), and I'm quite impressed by your findings! $\endgroup$ – Christian Semrau Jun 15 '15 at 20:09
  • $\begingroup$ Your results for 1 and 2 weighings are correct. Showing that n=5 with k=2 is impossible is quite simple, but as it was not asked, it shall not be answered here, and maybe spared for a different question :-) $\endgroup$ – Christian Semrau Jun 15 '15 at 20:22
  • $\begingroup$ Your solution for n=9, k=3, is correct, and I am still impressed. Your argument why n=10 and n=11 are not solvable, is also correct. As an addition, for n=11, the best you can do is weigh 2+2+3 balls, which leaves at most 25 possibilities. May I ask, did you find your solutions and numbers of remaining possibilities completely by hand, or which tools did you use? $\endgroup$ – Christian Semrau Jun 15 '15 at 20:31
  • $\begingroup$ I guessed my pattern for n=6, and later confirmed it would work. I then extended that for n=9. $\endgroup$ – user3294068 Jun 15 '15 at 20:42
  • $\begingroup$ Are you interested in some more variants? The original puzzle has some problems concerning two lighter balls. :-) And I accidentally overshot the original puzzle by solving for k=4 and k=5 (not by hand). $\endgroup$ – Christian Semrau Jun 15 '15 at 21:00

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.