I saw the puzzle in 'The Man Who Counted' by Malba Tahan (Norton 1993). A diamond is hidden in one of eight sacks of rice. The one with the diamond will be heavier than the other seven, and you have a balance to use to find out which one it is in, but you are only allowed two weighings. (I'm doing this from memory, I'm sure the details will be different from what was in the book, but the puzzle is the same.)
I'll put in a bit of space before discussing it, in case you want to think about it before seeing the answer.
Scroll down...
I started by thinking you would need three weighings, because I assumed you would do it as a binary calculation. However he trick is to realise that there are three outcomes from each weighing: left heavier, right heavier or balanced, so you need to make use of the 'balanced' condition as well as the other two. You compare two groups of three sacks (say nos 1,2,3 compared to 4,5,6). If it balances, you know it is not in any of those six, so it must be in one of the other two and you weigh 7 against 8 which gives you the answer. If instead 1+2+3 is heavier than 4+5+6, then you weigh 1 against 2. Either one those is heavier (giving you the answer) or they balance, in which case it is in 3. If 4+5+6 were heavier you do the same for them (weigh 4 against 5, form example).
You could of course find the diamond in this way from 9 sacks, but saying eight misleads you into thinking of binary steps.
The three outcomes from each weighing means that you can distinguish 3 x 3 = 9 different solutions, hence you can identify up to nine different situations. Or, you could say that each weighing gives you log2(3) = 1.585 bits of information. Two weighings gives you 2 x 1.585 = 3.17 bits of information. Finding 1 from 8 equally-probable outcomes requires log2(8) = 3 bits, so the 3.17 bits from the two weighing is enough information. (And of course log2(9) = 2 x log2(3))
No comments:
Post a Comment