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