Here’s a classic puzzle: you are a rather evil King. You have 1000 bottles of wine. Exactly one is poisoned. You need to find out which one. You have 10 prisoners. You can use them to test the wine.
Now, to make the problem more difficult: poison takes effect only after 10 hours, and you need to find the poisoned bottle within a day. (If the poison worked instantly, you could easily find the poisoned bottle by making just one prisoners test them all one by one. If you had unlimited time, you could cut the number of bottles in half while using just one prisoner by making him test half of the bottles, and it would be enough with 10 to find the right one. But you do not have time for this.)
You may stop here and try finding the solution on your own, if you want to, but the puzzle is considered hard, and it will most likely will take time. My intent is to simplify the solution a bit, and make it more transparent.
Here’s the standard solution: enumerate all 1000 bottles with binary numbers from 0 to 1110000011 (if I am not mistaken) and make the prisoner number i try the bottle number k iff the ith digit of the number k is 1. After 10 hours some prisoners will die (or perhaps no one will, if the poisoned bottle was the zeroth one) and then you will be able to reconstruct the binary number of the poisoned bottle.
Let’s see how it works when there are 3 prisoners (A, B and C) and 8 bottles:
bottle number 0: 0 0 0
bottle number 1: 0 0 1
bottle number 2: 0 1 0
bottle number 3: 0 1 1
bottle number 4: 1 0 0
bottle number 5: 1 0 1
bottle number 6: 1 1 0
bottle number 7: 1 1 1
prisoners:……….A B C
A will bottles 4, 5, 6 and 7, B will try 2, 3, 6 and 6, and finally C will try 1, 3, 5 and 7. If, say A and C die, you will immediately know that bottle number 5 was the poisoned one.
Here’s a rather more clear formulation of the same solution: don’t just use prisoners to find the bottle – use the subsets of prisoners. The set of 10 prisoners has 1024 subsets, more than enough. Assign each bottle to some subset. (Naturally, since each prisoner belongs to more than one subset, she will have to try more than one bottle). After 10 hours some subset of the set of prisoners will completely die out. Then you will know that the bottle, which you assigned to it was the one.
Of course, if you decide to implement this scheme you will inevitably have to use something like the binary number trick described above, but I think my explanation is better, deeper in some sense, and helps to understand not only how, but why. Or maybe not.