A great friend of mine recently sat for an interview. He was asked a question which has fascinated me since some days now. It is
Consider you have 100 balls which look the same but one out of them is either heavier or lighter than the rest . You are given a beam balance , then find out in minimum how many steps can you determine which ball is the odd one out?
The question is what is the solution to this problem? I can do this in 7 moves. Can we do anything better than it. How would one solve the generalized case of $100$ balls and $n$ of different weight ?
Divide the balls into three piles of as equal size as possible: two piles of 33 balls each, and one pile of 34 balls.
Weigh the equally sized piles. If the two piles are the same weight, then the odd ball must be in the 34.
If the two piles are different weights, we need to figure out if it is a result of a ball being heavier or lighter, so take 33 of the balls from the pile of 34 to compare to the heavier of the two piles. If it is again unbalanced, then the heavier pile must have a heavier ball. Otherwise, the lighter of the original piles has a lighter ball. Discard all balls except those in the odd pile.
From there, continue dividing the pile into thirds and testing two equally sized piles until none left.
$100\mapsto 34\mapsto 12\mapsto 4\mapsto 2\mapsto 1$, and a possible one additional step somewhere in the middle to determine whether the odd ball is heavier or lighter, for a total of $6$ steps.