Saturday, October 15, 2011

Google Recruitment Puzzle Explained

This forum includes a discussion on the puzzle. The most helpful answer is Morgan Creighton's. It turns out that the key to answering which is the smallest number of weightings one need to determine the heavier ball is the nature of the balanced scale (a more challenging alternative of simply being asked how to do it in two). For every weighting, the scale provides a trinary bit of information (a trit) (left side is heavier, right side is heavier or they are equal). The ternary system includes three numbers to describe three basic outcomes: 0, 1, 2. The single and double digit numbers in base 3 can describe 9 different numbers (decimal number is put in a braket): 0, 1, 2, 10, 11, 12, 20, 21, 22. Therefore up to 2 digit terniaries are more then enough to describe a system with 8 balls (actually it will work with 9 balls two - the slight amendment in the process will be to have three groups of three balls).

No comments:

Post a Comment