h1

8, 9, 12 balls problem

July 21st, 2014

Lately I’ve been reading some common interview puzzle problems and came across the 8-ball problem. I’ve come across this problem before, along with some more complex variations. In particular, http://learntofish.wordpress.com/2008/11/30/solution-of-the-12-balls-problem/ already gives a very good explanation of the solution. My only complaint is that I found it a bit difficult to keep track of the numbering. Thus, this post is not much more than my personal rendition of the problem and solution, using colour rather than labels.

The most basic variation is that you are given 8 balls but one is heavier than the rest. You are asked to find the minimum number of times you would use a balancing scale such that you would definitely find the heavier one.

basic 8 balls problem

basic 8 balls problem

I think it helps when you know that the solution is two times and you get to work that out. Here’s a visual solution:

basic problem solution

Solution to basic problem

This is the same solution for 9 balls, one heavy — the only difference is the second weighing is always the bottom case. However, a more interesting variation is of the same practical scenario but this time you are not told whether the one ball is heavier or lighter, just that it is different.

One ball has a different weight

Less knowledge: one ball weighs differently

This time solution to this is three times — this is somewhat straightforward for the 8 or 9 balls case, as an extension to above. But for the 12 ball case, the reasoning is much more subtle.

Addendum: It has been almost a year since I’ve last visited this post, I might one day finish with the visual version of the 12 ball case, but for now, I’ll just have to leave published as is. The original link‘s explanation will have to do.

 

Leave a Comment