Billiard Balls and Scale

First divide the 15 balls into three groups of five balls. Call the groups $A$ , $B$ , and $C$ . Let the ball of different weight be ball $X$ and call the group without ball $X$ as "perfect" and the group with ball $X$ as "imperfect".

Weighing 1 : Weigh group $A$ and group $B$

$\text{Weigh A and B} \implies \begin{cases} \text{If balance, C is }\red{\text{imperfect.}} \\ \text{If imbalance, C is }\blue{\text{perfect.}} \end{cases}$

Weighing 2 : Weigh group $B$ and group $C$

$\small \text{Weigh B \& C} \implies \begin{cases} \text{If C is }\red{\text{imperfect.}} \implies \begin{cases} \text{If C is heavier, X is heavier.} \\ \text{If C is lighter, X is lighter.} \end{cases} \\ \text{If C is }\blue{\text{perfect.}} \implies \begin{cases} \text{If balance, A is }\red{\text{imperfect.}} \\ \text{If imbalance, B is }\red{\text{imperfect.}} \end{cases} \implies \begin{cases} \text{If imperfect is heavier, X is heavier.} \\ \text{If imperfect is lighter, X is lighter.} \end{cases} \end{cases}$

Conclusions: After two weighing, we have identified which group of five balls has ball $X$ , and whether ball $X$ is heavier or lighter.

Weighing 3: Weigh a pair of two balls of the imperfect group.

$\text{Weigh 2 pairs of imperfect group} \implies \begin{cases} \text{If balance, the other ball is X.} \\ \text{If imbalance, the imperfect pair is known.} \end{cases}$

Weighing 4: Weigh the two balls of the imperfect pair and ball $X$ is found.

Therefore, the least number of weighing is $\boxed 4$ .

The answer I came up with is 4 and the 4th weigh is only necessary in a couple of scenarios. I believe it might be able to be done in 3 but I have not figured out how. I am looking to the community to either show me how it can be done in fewer moves or confirm, mathematically, why it requires 4 weighs. My solution is shown below.

Gary's solution shows that $4$ weighings is possible. It's not hard to see that $3$ is insufficient.

To see this, consider that there are $30$ possible outcomes: $15$ balls can be the outlier, and the outlier can be either heavy or light. One weighing divides the outcomes into $3$ groups: the balls on the left are heavier, the balls on the right are heavier, or the outlier is in the remaining balls. So narrowing down our outcomes into $1$ possibility after $n$ weighings requires that the number of initial outcomes be at most $3^n.$

In our case, we have $30 \le 3^n,$ so $n \ge 4.$

First, separate the balls into three groups of 5.
Test 1-5 vs 6-10 and then test 1-5 vs 11-15.

There are two possibilities:

1) One of those two tests will be balanced. The ten balls in the balanced groups can be ignored. The heavy/light ball is in 6-10 or 11-15, and we can deduce whether it is heavy or light from the test that includes its group.

2) Neither test is balanced. Then the heavy/light ball is in 1-5 and we can deduce whether it is heavy or light from the tests with its group.

We have reduced the set of balls to a group of five, and know whether the extra ball is heavy or is light.

Without loss of generality, the extra ball is heavy, and is in group 1-5. Weigh 1-2 vs 3-4. If they balance, the heavy ball is #5. If not, take the two balls from the heavy side and test them against each other to isolate the heavy ball.

I did not initially have a proof that 3 tests do not suffice, but I remembered my information theory at roughly the same time as helpful comments appeared, so I include a second half of the proof for the sake of completeness.

Edit: the information-theory lower bound An algorithm that takes at most $n$ steps, and where each step has at most $d$ possible outcomes, can only output at most $d^n$ different solutions. One can see this by modeling an algorithm as a decision tree, with branching factor $d$ and height $n$ . Such a tree will have at most $d^n$ leaves, which correspond to the different outputs.

In the current problem, $d=3$ , since each weighing has three possible results: left heavier, right heavier, and balanced. Thus a three-step algorithm can only reach $3^3 = 27$ different solution possibilities. But there are 15 choices of the ball, and 2 choices of "heavy" vs "light", which means there are 30 different possible scenarios. Thus a 3-step algorithm would not suffice.

With thanks to Mark Hennings.

See this balance puzzle article , and replace "coin" with "billiard ball".

Since the target billiard ball is different from the others and the goal is to identify the billiard ball, the number of weighings for $c = 15$ billiard balls is

$\lceil \log_3 (2c + 1) \rceil = \lceil \log_3 (2 \cdot 15 + 1) \rceil = \boxed{4}$ .

Normal problem with oddity of offending ball specified, it would need 3 weighings by dividing in 5,5,5 — 2,2,1 —1,1. However, one extra weighing is required in 5,5,5 to find the oddity of the ball.