Thursday, July 24, 2008
8 ball weighing problem
The 8 ball problem describes thought inertia of a computer scientist or programmer. When given a problem to find a heavier ball hidden among seven other identical balls using a balance scale using a minimum number of weighings, a CS person would answer that three weighings are required, based on 8 being encoded in three bits, each weighing giving dividing the problem in half. In fact, only two are required, because each weighing gives one of the three answers, so the bits are not binary bits, but ternary bits, reducing the problem set by a factor of three. So, with two weighings you can find a heavier ball hidden among eight identical others.
Subscribe to:
Posts (Atom)
