12 Balls , prove you have to put 4 balls on each side in order to find odd ball is 3 times

Question

You have twelve (12) balls and a set of balance scales.

One (1) of the balls is a different weight to the other eleven (11) balls.

You are allowed to use the balance scales three (3) times.

You need to determine which ball is the “odd one out” and whether it is heavier or lighter than the other balls.

this is the solution for 4 balls.

how can I prove with a decision tree that if I dont start with 4 balls on each side ; I cant find the odd ball in 3 times? should I show the worst case of weighing 1&1 /2&2 ..../6&6 balls in first time?

Answer 1

If you don't choose to break up the 12 balls into 3 sets of 4, then one of the sets will have at least 5 balls in it.

Suppose the heavy ball is in the set of 5 or more. It's impossible to deduce which of those balls is heavy by only using the scale twice.

Answer 2

Use the scale once to know "<", "=" or ">", then we can get one trit of information.

To find out 1 odd ball (heavier or lighter) within 12 balls, we should pick one from 24 cases (1L, 1H, 2L, 2H, ..., 12L, 12H). This problem contains less than 3 trits of information ($24<3^3$), so it is possible to solve by using the scale three times. The solution is mentioned in the original question:

In the first step of this solution, we use the scale with 4 balls in each side, then we can divide 24 cases into 3 sub problems: each with 8 cases for "<", "=" and ">" respectively. Each sub problem contains less than 2 trits of information ($8<3^2$), so it is possible to solve by 2 times.

This is the unique way, because any other ways (divide 24 cases into 3 groups) get at lease one group more than $3^2=9$ cases. For example:

• put 6 balls on each side, then we can get only "<" and ">" (1 bit but not 1 trit of information), i.e. divide into 12 + 12;
• put 5 balls on each side, then we can divide into 10 + 10 + 4;
• put 3 balls on each side, then we can divide into 6 + 6 + 12;
• ...

Interestingly, it is impossible to find out 1 odd ball (heavier or lighter) within 4 balls by using scale twice, although there are 8 cases containing less than 2 trit of information. (Refer right "=" branch of the above figure.)