Eight Balls Puzzle

Like in other puzzles, you might’ve encountered it either online or in a book. Variations exist but the core idea behind the solution is the same.

Here’s the problem description

You have eight balls all of the same size. Seven of them weigh the same, and one of them weighs slightly more. How can you find the ball that is heavier by using a balance and only two weighings?

My initial approach was divide the whole in two sets of four, but that isn’t good enough because it would require three weighings. Yet I recognised that I was going in the right direction: divide and conquer was the way to go.

Solution Link to heading

The solution I ended up with is the following:

1. split the full set in three 3 subgroups, of which two are made of 3 elements each, and the last 2

2. measure the two 3-element groups

3. if subgroups in step 2. are equal in size, then we discard this 6 balls, and used the second weighing to find out the heavier ball from the 2-element subgroup

4. else if the subgroups are not equal, we discard the subgroup made of two balls. We also discard the 3-element subgroup that is lighter.

   The final step is to take any two balls of the 3-element heavier subgroup from the first measurement, and then observe either that the 2 balls used in the second measurement are of the same weight, so the heavier ball is the one left out of the second measurement; or the 2 balls are not equal and thus we can also identify the heavier one.

This is a binary search solution so it runs in $ O(log (n)) $ time.