5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ My first assumption is that this would gain us nothing over a normal 2-pan system (for one heavier ball). You get no extra information if a single heavy pan cannot fall. $\endgroup$ – Deacon Jun 4 '15 at 20:38
  • $\begingroup$ Can you add a separate heavy weight (the weight of which you may not know) to one of the pans? This changes the answer for e.g. 3 balls. $\endgroup$ – Lopsy Jun 4 '15 at 20:52
  • $\begingroup$ No, you may only weigh the balls you are given. $\endgroup$ – Christian Semrau Jun 4 '15 at 21:03
  • $\begingroup$ This is not how physics works. :p $\endgroup$ – Ian MacDonald Jun 4 '15 at 22:30
  • $\begingroup$ Follow-Up: puzzling.stackexchange.com/questions/16006/… $\endgroup$ – Christian Semrau Jun 5 '15 at 7:28
7
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Very nice! Can you please explicitly state why more than 3^k - 2 balls can not be differentiated without auxiliary balls? $\endgroup$ – Christian Semrau Jun 5 '15 at 6:40
  • $\begingroup$ I have a Doubt over this (1) With A=x, B=x, C=x+1, how can you claim that we are comparing only A&B pans ? What if the heavier ball is in C ? (2) Rephrasing : When you start with 3^k-2 balls, put as A=3^(k-1)-1 & B=3^(k-1)-1 & C=3^(k-1), if one pan is lightest, then fine, but if the heavier ball was in C, then how to proceed ? $\endgroup$ – Prem Jun 5 '15 at 16:32
  • $\begingroup$ I'll add some details to cover your question. $\endgroup$ – user3294068 Jun 5 '15 at 18:40
  • $\begingroup$ @Prem When no pan goes up, you know the heavy ball is in pan C (because pans A and B are equally light, thus do not contain the heavy ball). This leaves you with 3^(k-1) balls to test, and at least one definitely normal ball (dubbed a "ringer") from pan A. Proceed as described in the first part of the answer. $\endgroup$ – Christian Semrau Jun 6 '15 at 8:09
  • $\begingroup$ @user3294068 Just compared solutions again, and found a little imprecision: In the general case, if pan A is the lightest, just noting that you have "at most 3^(k-1) balls and at least one ringer", is not enough. If I gave you 3^(k-1)-1 balls and exactly one ringer, you could not find the heavy ball in k-1 weighings. So you should note that in cases A and B, you get 3^(k-1)-1 balls and two ringers, and can treat one ringer als an unknown ball, and proceed with 3^(k-1) balls and one ringer. $\endgroup$ – Christian Semrau Jun 6 '15 at 8:46

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.