## PRIZE PUZZLE FOR MAY 2008## POISONED WINEYou are the ruler of a medieval empire and you are about to have a celebration tomorrow. The celebration is the most important party you have ever hosted. You've got 1000 bottles of wine you were planning to open for the celebration, but you find out that one of them is poisoned. The poison exhibits no symptoms until death. Death occurs within ten to twenty hours after consuming even the minutest amount of poison. You have thousands of prisoners at your disposal and just under 24 hours to determine which single bottle is poisoned. What is the smallest number of prisoners you must have to drink from the bottles to be absolutely sure to find the poisoned bottle within 24 hours?
The answer is 10 -- only ten prisoners are required to deduce which bottle of wine is poisoned. Number the prisoners 0 to 9. Number the bottles 0 to 999. Prisoner 0 must sample every odd-numbered bottle. Group the bottles into blocks of 2. Prisoner 1 must sample the odd-numbered groups. Group the bottles into groups of 4 and get prisoner 2 to sample the odd-numbered groups. Then group them into 8's and so on until prisoner 9 gets to sample the bottles 512 to 999. (There could, of course, be 1024 bottles so some prisoners get off lightly.) After a while there will be a number of dead prisoners. Decode their numbers as binary digits in a 10-bit number. This will locate the bottle of wine that is poisoned. Thanks to Christopher Broughton for sending me this puzzle. What is the probability of surviving if you are one of the prisoners? Does it depend on your prisoner number? No one answered this puzzle correctly. John Stafford had a good idea with the answer 64 by arranging the bottles in a 32 x 32 matrix and allocating each row and each column to one of the prisoners who has to sample all the bottles in his/her row or column. The poisoned wine would then kill two prisoners which would locate the row and column of the dreaded bottle. |