4
$\begingroup$

This is a continuation of the questions A balance with three pans, detecting the lightest pan (find the one lighter ball) and (find the one heavier ball). There, I asked for the maximum n given a bound for k, now I'll ask for the minimum k given a value for n. This question is based on a puzzle told to me by a friend, Markus Götz, who put his version online here: Deviating Ball Puzzles (pdf).

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 problems

In each problem you are given n balls. They are all of the same weight, except as stated in each problem. You are to identify the deviating ball by only using the balance, weighing only the given balls. You are also to present a method to identify the deviating ball.

1) You are given n balls, one of which is lighter. What is the least number of weighings, k(n), so that the lighter ball can always be identified with at most k weightings?

2) You are given n balls, one of which is heavier. What is the least number of weighings, k(n), so that the heavier ball can always be identified with at most k weightings?

Note about the relation to the previous questions

If k(n) was nondecreasing, this question would be trivial after answering the questions linked above, where I asked to find n(k), the maximum number n of balls for k weighings. But how does k(n) really grow? OTOH, after answering this question, the other ones become almost trivial.

$\endgroup$
  • $\begingroup$ Isn't it just the inverse of the functions in the other two questions? $\endgroup$ – Ivo Beckers Jun 6 '15 at 16:45
  • $\begingroup$ The two functions are indeed (one-sided) inverse of each other: k(n(k0)) = k0. This does not fully define k(n) for all values of n, so the answers to the other two questions do not answer this question. OTOH, knowing k(n) for arbitrary n provides knowledge of n(k), so in some sense, this question subsumes the two others. $\endgroup$ – Christian Semrau Jun 6 '15 at 18:45
  • $\begingroup$ For 2) you can not identify the heavier ball without additional constraint of what heavy is. $\endgroup$ – Moti Jun 8 '15 at 5:22
  • $\begingroup$ I reformulated the question. I hope it is clearer now. All problems for the three-pan balance have the same setup, they just differ in the number and relative weight of deviating balls, and the direction of optimization (least k for given n, or largest n for given k). $\endgroup$ – Christian Semrau Jun 8 '15 at 19:26
  • $\begingroup$ The next problem is to identify two heavier balls: puzzling.stackexchange.com/questions/16006/… $\endgroup$ – Christian Semrau Jun 10 '15 at 20:53
2
$\begingroup$

Reversing my answers for the other two questions (using $[]$ for the "ceiling" function):

Lighter: $$k = [\log_4 n]$$ except for $n=2$, which has no solution.

Approach: Put $4^{k-1}$ balls on each pan, set rest aside. Weigh. If one pan rises, it contains the light ball. If no pan rises, the light ball is in the extra pile. The largest pile is at most $4^{k-1}$ balls. Continue with putting $1/4$ of the balls on each pan until you have a solution.

If the number of balls remaining after a weighing is not a multiple of four, you can add in eliminated balls ("ringers") to even things out.

Heavier: $$k \approx [\log_3 (n+2)]$$ except for $n=2,3$, which have no solution. Also, edge cases are slightly off (see details below). For $n=2$ or $n=3$, there is no way to determine one heavy ball using this type of scale.

Approach: put $[n/3]-1$ balls on each pan, which leaves you with 1 to 3 left over. Add the extras to one pan, giving you two equal-number pans and one extra-number pan. If the heavy ball is on one of the equal-number pans, the other equal-number pan will rise. If neither rises, the heavy ball is on the extra-number pan.

Repeat this process with the smaller number of balls until you are done. For steps after the first, you have some balls that are known to be normal weight (I call these "ringers"). You can use ringers to make the numbers work out such that with $x$ remaining balls, you can put $[x/3]$ or fewer balls on each pan and add ringers to make the numbers work out so you have two equal pans and one extra pan. (This requires at most two ringers and you must have at least two ringers after the first step). Thus, if you have $x$ candidates after the first weighing, you can complete the process in at most $[\log_3 x]$ more steps.

Do a bit of math and you have $$k = [\log_3 (n + 2)]$$ except:

$n = 2,3$: Impossible.

$n = 3^i-3$ $(i>1)$: Requires $k=i+1$ steps. $i.e. n = 6$ requires $k=3$ steps, even though $n=7$ only requires $k=2$ steps.

To illustrate the special case of $n=6$, if you put two balls on each pan, then you are guaranteed that two pans are each full of normal balls, so no pan will rise. Thus, you can only put 1 ball each on two pans and 2-4 balls on the third pan. If no pan rises, then the heavy one is one of the set of 4, and for $n=4$, you require 2 more weighings.

This issue arises for any $n=3^i-3$: you put $n/3-1 = 3^{i-1}-2$ balls on two pans, leaving $3^{i-1}+1$ balls remaining. If the heavy one is in the latter set, that will require $k=i+1$ more weighings.

$\endgroup$
  • $\begingroup$ Correct solution for the lighter ball, except for one special case: If n is of the form 3*4^(k-1)+2, you leave 2 balls out, and what if the light ball is one of these? (Will check the heavy ball next.) $\endgroup$ – Christian Semrau Jun 8 '15 at 20:27
  • $\begingroup$ Your strategy for the heavier ball matches my own strategy. But I do not see clearly why n = 3^i - 3 is not solvable with i weighings. $\endgroup$ – Christian Semrau Jun 8 '15 at 20:36
  • $\begingroup$ Updated to address both comments. $\endgroup$ – user3294068 Jun 8 '15 at 22:29
  • $\begingroup$ Very good. Did you already see the case of two heavy balls? :-) $\endgroup$ – Christian Semrau Jun 9 '15 at 7:21
  • $\begingroup$ @ArghyaChakraborty We are putting $4$ balls on each of the 3 pans, and leave $4$ balls aside. $\endgroup$ – Christian Semrau Jun 28 '15 at 8:16

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.