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!
7 Comments
I solved that puzzle a while ago. Strange coincidence :-)). In my version there were 12 coins and one of them was spurious.
Nickolay, you probably meant you had been trying to solve that puzzle ;)
Here’s another one.
You’re at a TV show and need to guess which of 3 boxes contains the prize (2 others are empty). According to the rules after you’ve chosen a box, the presenter opens one of the other 2 boxes, which is empty. Then you may either keep your decision or choose the other box. The question is: what is better, to choose the same box again or the other one?
Thanks Dmitry for presenting this puzzle. I haven’t heard of it before. But your puzzle statement doesn’t specify clearly that the presenter _knows_ where’s the prize. Without this specification, the puzzle has different solution. More on this here: http://en.wikipedia.org/wiki/Monty_Hall_problem
Okay first take 3 3 eggs each side and leave 2 eggs aside
then
case 1 if the both set of 3 eggs are equal then the lighter will be one of the two eggs unweighed so when we weigh them in second installment then we will get the light one.
case 2 if the weight is unequal then take the lighter one, weigh the 2 of three, if both are equal then the third is lightest and if unequal then you get the answer.
Good work, Naveen. Now solve the second puzzle ;)
Umm… I can solve the second puzzle by 4 weighings…
Nevertheless, it’s possible to do in only 3 weighings.
Some hints:
- the first move of dividing all balls into 3 groups is a right one;
- you must always have 3 possible outcomes in every weighting; if you have only 2 outcomes, think again;
- try to calculate the number of possible states after every move to check yourself — if you have 8 or 9 possible states after the first weighting, and 3 after the second, you are on the right way; e.g. the first move mentioned above gives you 8 possible states (you have either 4 low-weight + 4 high-weight balls, or 4 balls of unknown weight).