A balance with three pans, detecting the lightest pan (find the one lighter/heavier ball, for a given number of balls)

Question

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.

Answer 1

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.