Probably, you already know the first one. It sounds like this:
You have eight balls all of the same size. Seven of them weigh the same, and one of them weighs slightly more. How can you find the ball that is heavier by using a balance and only two weighings?
Finding the answer isn’t hard. Another interesting question is: how to prove that two weighings is the minimum solution without examining all possible scenarios?
We can reason the following way: there are 8 possible states of the “world”. On each weighing there are 3 possible outcomes. Two weighings give us 3 * 3 = 9 conceivable outcomes. So in principle, the problem might be solvable in two weighings, but not in one, since 3 < 8.
Ok, let’s consider harder ball weighing puzzle:
Now you have twelve balls, and one of them is either heavier or lighter than others. Your task is to design a strategy to determine which is the odd ball and whether it is heavier or lighter than the others in as few uses of the balance as possible.
Reasoning the same way as before, we can conclude that in this case you need only one more weighing. See: now we have 24 possible states of the world (12 balls in question and odd ball can be heavier or lighter). Thus, two weighings are obviously not enough. But three weighings give us 3 * 3 * 3 = 27 conceivable outcomes. Now try to find the optimal strategy!