The Balancing Act

Lets us start with a puzzle somewhat common place. A shopkeeper gets a stock of dozen cricket balls out of which one is a cork ball (kookaburra) and the remaining are rubber balls.  He is asked not to touch balls with hands (as it has to be used for the match), but is given a "pan" balance which will show either equal, less than, or larger than for the weights on the pans.

Find the minimum number of uses of the balance to find out the heavy ball.

Hint: 1 >> Separate the balls

The extension to this puzzle is interesting, Let us say that we want to find the odd ball (which can be  heavy/light) from the lot of 12 cricket balls. 

Guess how?

The interesting fact is that the odd ball can be determined with its weight in three measures. The idea is very similar to the source coding - Huffman coding. We can form a coding tree and verify it easily.

Let Left pan be represented as L and right pan as R.

The stepwise solution is as follows,

1. Divide the 12 balls into groups of three.
2. Weight 2 groups (of three balls) --> 1st measure. There are three possibilities 
• L=R then discard both the group
• L>R , call case A
• L<R , call case B
3. (If case A or case B happened) In the cases L>R and L<R, replace the right set by any of the untouched group. --> 2nd measure Then, 
• L=R, then the balls removed from the right pan is the odd group and follows the case in the previous measure. (ie, if case A-- light, case B -- heavy)
• L!=R, the the case which happened in the previous measure follows(ie, if case A-- heavy, case B -- light)
4. From the odd group determined from 3, take any two balls and do the measure;  --> 3rd measure
• if L=R, the  odd ball is the unmeasured ball and follows the same weight as in point 3.
• if L!=R, then the odd ball is one which follows the case in point 3.

The reader now can try to generalize this for \(m\) measurements