Algorithmic Efficiency: Finding the Heaviest Ball

Let’s suppose that we have a scale and 8 metal balls that are equal in weight except for one of them, which is heavier than all. We have to identify the one that is the heaviest. The only way we can compare the weight of the two balls is by placing them on the scale and checking which one weighs more.

One of the possible solutions

We can find the heaviest ball by placing one ball on the left side and putting all balls one by one on the other side of the scale (the side which goes down has the heaviest ball). This method will take at most $7$ tries to get the heaviest ball.

Note: If we have $\text{N}$ number of balls, then this algorithmProcedure: step by step to solve the problem will take $\text{N-1}$ steps. It will be really difficult if $\text{N}$ is a large amount.

Solution in 3 tries - The halving technique

We can find the heaviest ball by distributing balls into two parts: putting half balls on one side of the balance and half on the other and checking which side of the scale is heavy. Moving on, we’ll discard all the balls on the lighter side (as they can’t have that heavier ball) and select all the balls from the heavier side and then apply the same halving technique until we find the heaviest ball.

Analysis of the halving strategy

The halving technique will reduce the number of tries to use the scale in order to compare the balls.

$$N,\space \frac{N}{2}, \space \frac{N}{4}, \space \frac{N}{8},\space ... \space 4,\space 2,\space 1$$

This essentially means that we are shrinking the size of the problem by half in each step.

In other words, the number of tries the player needs to make for finding the heaviest ball is $\log_2 N$.

Solution in 2 tries

We can find the heaviest ball in $2$ tries only by placing $3$ balls on the left side, $3$ balls on the right side, and the remaining $2$ balls outside the balance. Now there are two possibilities:

1. The balance maintains an equilibrium state, which means that the $2$ balls kept outside of the scale contain the heaviest one. We can easily identify the heaviest ball in $1$ step by placing both balls on each side of the scale.

2. If either side weighs down, this means that the heavier side contains the heaviest ball (we discard the balls from the other side, as well as the two outside). Now, we can find the heaviest ball in $1$ additional step (considering only these 3) as described in the above hint.

Another problem

Similarly, let’s suppose that we have $9$ balls instead of $8$.

The halving technique ($\log_2N$ solution)

Note $N$, in this case, is odd. Can we apply the halving technique directly to it? Yes! we can. We can keep $1$ ball outside the scale and apply the halving technique to the remaining balls. In this particular scenario, we can find the heaviest ball in a maximum of $3$ steps. How? Think about it.

So, generally, if the number of balls is $N$, we can apply the halving technique (binary searching) to solve this problem in $\log_2 N$ steps.

Note: For the odd case, we’ll simply place $\lfloor{N/2}\rfloor$ balls on both sides and one outside. In case of equality, the ball outside is the required ball. Otherwise, we choose the heavier side and repeat the process until we are left with one ball only.

Dividing the balls in 3 parts ($\log_3 N$ solution)

As in the halving technique, we’ll divide the problem set into 3 equal sets, the tertiary search.

For example, in the case of $9$ balls, we can start by placing $3$ balls on each side of the balance and leave the remaining $3$ outside the balance.

Note: This tertiary searching is just an extension of the halving technique, where we place the entire $N/3$ balls outside, making the search more efficient.

If both sides are balanced, we’ll use the balls which were kept outside. It must have the heavier ball, which can be figured out in $1$ more step.

If $1$ side is heavy then we can use those $3$ balls in the next step to identify the heaviest one in the next step.

Therefore, we shrank the search space of $N$ balls in the following fashion:

$$N, \space \frac{N}{3}, \space \frac{N}{9}, \space \frac{N}{27}, \space ... \space 9,\space 3,\space 1$$

The number of tries to find the heavier ball will take $\log_3N$ steps.

In this case, $N$ was $9$. Therefore, we can identify the heaviest ball in $2$ steps only using the $\log_3N$ approach.