algorithmic analysis

You have eight identical keys. One is heavier than the rest. Using nothing but a balance, what is the most efficient way to find it?

Solutions:

The most obvious answer is to split the keys into four groups of two, weigh each set individually, and in a maximum of four attempts you’ll have your answer. A rung above is the divide and conquer approach.  Split the keys into two groups of four on the balance, take the heavier four, split them in half, determine which two are heavier then weigh them against each other. Same answer, three steps, but it can be done in two. You split the keys into three groups, two sets of three and one set of two. Put the groups of three on the balance, if they are equal weigh the two remaining balls against each other. If they are not equal, balance two keys from the heavier side and take the third one out,  if one is heavier you have your key, if they balance you know the one left over is the heaviest.

The applied principle exploits the additional information provided by the balance. By splitting the keys into three groups and comparing two of them we can infer the state of the third. So the balance provides three pieces of information instead of two. In the worst case using this additional piece of information will always be 33% more efficient.

Demo (executable)

Demo (java Source)