That is an interesting one.
It's easy to see that a maximum for the number of balls would be limited to half the number of terminating leafs in a balanced trinary tree,
n = round_down_to_nearest_int((3^k)/2),
but there is more to it than that.
Given the above equation, I could have used three quesses to solve for 13 balls. If I had a control ball, that I knew was the weight of the non-odd-balls, I could do it with 13 balls. After the first weighing, I will always have a control ball, so I'll assume that this consideration will only affect the equation once.
Also, note that the first weighing divides the balls into 3 groups, with each group limited to round_down_int((3^(k-1))/2) balls.
Therefore, the answer must be:
n = 3*round_down_int((3^(k-1))/2) balls,
for k weighings.
~Mitch |
