The Puzzle Returns!
by Tom Temple
13 January 2009
By popular demand. The score stands at
- Brayton: 4
- Fromberger: 4
- Joran: 4
- Jourdan: 4
- North: 4
- Plumer: 4
- Shea: 4
- Cosmo: 0
- Tom: infinity
It’s a tight race for second!
Recall the classic twelve ball, three weighing problem. Of the K balls, one is either heavier or lighter and your goal is to determine which (and whether it is heavy or light) by using a balance N times.
The problem for this week is to determine the most balls that can be distinguished in N weighings. Your anwer is allowed to be adaptive. In fact, I’m suspicious that your anwer must be adaptive.[2]
Feel free to define it as a recursion, i.e. assume you have a method for determining K’ balls in N-1 weighings and then use K’ in your expression for K. If you do this, be sure to define a base case e.g. N=2 or N=3.
Bonus. Suppose that I have marked exactly one of the K balls and tell you that the marked ball is either normal or light; it is surely not heavy. How does this change your answer?
2 Bonus to anyone who proves or disproves this.
