The 8 ball problem

Author: Kasper B. Graversen, 16/07/08
Keywords: IQ Test, Logic test, Fun
Abstract: The 8 ball problem, the puzzle almost all developers gets wrong! Given 8 balls and a scale identify the one heavier ball using the least number of weighings.
subscribe to my RSS feed


Bookmark and Share


The 8 ball problem

This is one of my favorite questions to ask people. Primarily computer science people, as they always get this one wrong :-)

The problem is quite simple. You are given 8 identical-looking balls, one of which is heavier than the other 7 (all of which weigh the same). Using an old-fashioned mechanical set of scales you must identify the heavier ball using the scale as few times as possible. The scale is constructed using two bowls and an arm enabling the bowls to either balance or have one bowl rising while the other (and heavier bowl) falling. You can't just add one ball at a time thinking its one weighing, however, you may put any number of balls in each bowl... All you need to solve the puzzle is to use a bit of common sense.










Close but wrong

WARNING! Only read this when you have found a solution!

Many people, especially people rooted in computer science, are quick to settle for 3 weighings. This is most probably due to the O( log2 n ) trail of thought. Or mistakingly thinking the answer is to first weigh balls {1,2,3,4} in one bowl, and {5,6,7,8} in the other, pick the heavier bowl. Then as weighing number 2, weigh the 4 heavy balls, e.g. {1,2} against {3,4}. Finally, the third weighing weighing the two remaining balls one in each bowl, thus identifying the heavier ball, e.g. {3} against {4}.

If you settled for 3 weighings you are wrong, try again. You can do better...










Solution

You can identify the heavier ball in only 2 weighings! The secret is not to get fooled into the "divide and conquer" approach where the input is halved in each iteration as explained above. To achieve this in only 2 weighings, you first put 3 balls in each bowl on the scale, e.g. {1,2,3} against {4,5,6}. Should the scale balance, you have only 2 balls remaining which you can compare by putting each in a separate bowl on the scale, e.g. {7} against {8}. Should the scale not balance, however, take the 3 balls from the heavier bowl on the scale (e.g. 1,2,3). Pick any 2 balls and compare these against each other, e.g. {1} against {2}. If the scale balances, you know it is ball 3 is the heavier. Is the scale moving, you know it's the ball on the heavier side.

Have fun...


If you like this site consider subscribing to my RSS feed or how about subscribing by Email.



Comments

If you have any comments to this article, please drop me a mail at firstclassthoughts at gmail dot com please indicate if I can't publish whole or parts of your comment on the site.

  • Corey Spain
    In response to your "The 8 ball problem" article you posted on 07/16/2008. Like all developers as you mentioned got the answer wrong, I too fell for the same answer of "3" very quickly and with confidence! I do love the answer of 2 and understand where I have gone wrong, as u point out, the "divide and conquer" method was the only way i was thinking and felt comfortable with my answer in the fastest time.

    However, I write this email to explain why i think this is the common answer in many developers. As the main goal of this puzzle is to give the lowest weighs as possible to find the heaviest ball, 2 is of course the best answer, but would take a considerably more time to come up with that answer. Developers are naturally pressed to come up with the best solutions in the fastest time. As the answer 3 logically pops up as the quickest and easiest solution to the puzzle, we hastily jump to that conclusion. An answer in a smaller number would have taken considerable more time and therefore is given lower priority then the the faster, sensible answer.

    Bottom line...
    2 is the best answer, but 3 is the fastest and if if this puzzle was carried out in real life, Developers would finish the puzzle with heaviest ball in hand before the time it took figuring out it could have been done in 2 weighs! For the same outcome, to find the heaviest ball, I think the quickest solution is worth the extra weighing. More time to move on to other puzzles. :)

    Great article and I learned a lot in this little lesson. This response can be used in whole on your website.

    Thank You,
    Corey (Java, C++, .Net Developer)
  • Mr. Fnortner
    While normally problems of this sort elicit a hmmmph from me as I move on, having a low tolerance for being snookered, Corey Spain's answer got my juices flowing, and I am moved to comment.

    I have long since retired from data processing (as we called it back in the early days). I know full well the advantages of writing code focused on specific solutions versus generic algorithms. Blistering speeds were possible from humble processors (we didn't think they were humble then--but that's a story for another day) if the code could be written to fit the exact solution. The 8 ball problem has an elegant two step solution, but what does one do if faced with solving a weighing problem for n balls?

    If a programmer has the time, and the problem is bounded, say from 2 balls to 150 balls, then the programmer could, could, write 149 best solutions into his weighing program. On the other hand, programmers specialize in generic algorithms, and the better ones write ingenious methods to solve generic problems, for two reasons: real life problems are not bounded and so the solution space is indeterminate, and resources are scarce and the cost to write a large number of best solutions exceeds the value of solving the problem, in general.

    So, it's no wonder that "people rooted in computer science" go for the three-weighings answer. And I'm not sure they are "settling," either. Psychologists might call this "satisficing." If you had asked a lawyer, he or she might easily have tried to negotiate fewer balls or more weighings, as a first gambit perhaps. It's all in the discipline that folks have become adapted to.


If you like this site consider subscribing to my RSS feed or how about subscribing by Email.


Help spread the word

Share this post on your favorite social bookmarking sites:
If you enjoyed this article, found it thought provoking, educative or otherwise good, please link to this page from your page or social bookmarking page. If you have any texts you think are worth publishing on First Class Thoughts, don't hesitate to send me a mail! Quality always welcome.


Bookmark and Share


The most recent contributions
28/07/09 Magic in mathematics II Fun with the number cyclic numbers, and specifically with 142857 as it is the smallest of such numbers.
13/07/09 My top 8 time-saving Firefox shortcuts This article presents my favorite top 8 time-saving shortcuts in Firefox 3.0 and Firefox 3.5. Get to know these and you'll be saving a lot of time. They have been ordered by "the element of most surprise"
20/05/09 Board Game Jungle speed / Arriba Review of the cool game "Jungle Speed" aka. "Arriba".
16/05/09 Danish Twin words "Twin words" are words that not only have multiple meanings, they must be composed next to each other in meaningful sentences. This article explores the concept of twin words.
Nothing of interest? Try browsing the entire article archive...