Tuesday, February 24, 2009

Weighing puzzle

This is one gem, that I got from a friend of mine. The puzzle in its simplest form goes like this:

There are a set of 8 balls. Out of which 7 are of same mass, and the remaining one is heavier than the rest. What is the minimum number of weighings required to find out the heavier ball? i.e. How many times do you require to use the balance?

My Method

I do not know what you would do, but what I did was to divide the balls first into groups of two groups of 4 balls, then take the heavier set, and divide it into two parts and so on. This yields an answer of 3. More precisely, the answer is:

log2nwhere n is the number of balls.

 

Actual Answer

However the actual answer is two weighings. The technique is to split the balls into three approximately equal groups, here we have 3,3,2. Then weigh the 3,3 groups against each other, if they are the same, then weigh the two remaining balls against one another. If one of the two 3,3 groups are heavier, then select that group and weigh any of the two balls against one another, if one is heavy, then you got the ball, if both are equal, then the third one of the group is the heavier.

So the correct expression is

log3nfor n balls.

 

Decision Tree

Here is a schematic diagram:

Decision Tree

No comments:

Post a Comment

I'd love to hear from you !