You have 6 balls, of which one is either heavier or lighter, and you do not know which of the two situations it is. The other 5 balls all weigh the same.
You have a balance scale. What is the minimum number of weighings you need to figure the odd ball out?
The minimum number of weighings required is
3
Proof it's possible:
Put 2 balls on each side of the scale.
If the scale balances, then the fake ball is in the two remaining balls. Now compare one of them with a real ball. If the scale is uneven, you will know the ball is fake and if it's heavier or lighter. If it balances, the last ball is fake and you can use your last weighing to know if it's heavier or lighter.
If the scale is uneven, one group of balls is lighter than the other. Compare the two balls in the lighter group. If the scale is uneven, you'll know one of the two balls is lighter, and you can use your last weighing to identify which one of the two it is. If the scale is even, then you'll know one of the two other balls are heavier, and you can use your last weighing to identify which one of the two it is.
Please note that here, we've also figured out if the odd ball is heavier or lighter (which was not required by the question).
Proof it's optimal:
2 weighings are not enough. The first weighing must be either one ball on each side or two balls on each side to obtain information.
In the first case, if the scale balances, you will have to guess in one weighing which one between the 4 remaining balls is fake. This is impossible.
In the second case, if the scale does not balance, you will have to guess in one weighing which one between the 4 balls you weighed is fake. This is impossible.
Actually, with the same number of weighings, you can go up to
13 balls. See this page. (it also shows that with 12 balls, you can still guess if the odd ball is lighter or heavier).
Let us start with three balls which we label A,B,C. Put A and B on the balance. If they balance, the odd one is C. If they do not balance, the odd one is either A or B, but definitely not C. Weigh A against C: if they balance then B is the odd one, otherwise it is A. That is two weighings maximum, with a 1/3 chance of doing it in 1.
The same works for three pairs of balls. Two weighings give us the pair with the odd ball. Weigh any ball from the odd set against any ball from the other set. If they do not balance, then it was the odd one. If they balance, then it was the other one. That gives us the odd ball in 3 weighings with a 1/3 chance of doing it in 2.
We can extend this to 12 balls, weighing them in 3 sets of four balls, then finding the odd pair from the odd set of four, then the odd ball from the pair in the same way. This gives us the odd ball in 4 weighings with a 1/3 chance of doing it in 3. And so on for higher powers of 2.
How about nine balls? Or twenty-seven?
For three sets of three balls, we can determine the odd set and whether the odd ball is lighter or heaver with three weighings. We can then determine which of three balls is the odd one with one extra weighing because we now know which side has the odd ball when they don't balance. We can find the odd ball out in 27 with five weighings, and 81 with 6 weighings, and so on.
