Problem: There are 500 barrels of wine and exactly one of them is poisoned. The king wants to identify the poisoned barrel but he is ready to sacrifice only 4 prisoners. They have 4 days to find the poisoned barrel. The poison has the property that after consuming it one can die anytime in the next 24hrs. Give the strategy to find the poisoned barrel.
Source: Shahbaz also CSE blog
Source: Shahbaz also CSE blog
This comment has been removed by the author.
ReplyDeleteThis is an extension of a commonly known puzzle where you have 512 barrels and 9 prisoners but only 24 hrs. That puzzle can be solved by numbering each barrel from 0 - 511 and then writing the barrel number in binary. We will need only 9 bits, each bit corresponds to a prisoner. For the ith wine jth bit is 1 if jth prisoner consumed ith wine. This way we have a unique combination of prisoners allocated to every barrel.
ReplyDeleteIn this problem we have 4 prisoners and 4 rounds. Naively, in each round we can check 16 barrels. However, we are considering these 4 rounds rather independently. How can we assign to each barrel a unique combination of prisoners?
Here, we can make use of the fact that there are 4 rounds, so each barrel is assigned to a prisoner in either round 1 or round 2 or round 3 or round 4 or never. In this way, we can number 625 wines using only 4 digit. Each barrel is uniquely assigned to the 4 prisoners.
For example wine 624 is assigned to each prisoner in round 4. So if, all the prisoners are alive till round 4 and die at the end of round 4, we know it is wine 624 that is poisoned. Another example, say wine 1 (0001)is poisoned. It is assigned only to prisoner 1 in round 1. If he is the only one to die after round 1, we know that all the barrels starting with 1 i.e 0001,2001,2221,2331, 2341 etc are under suspicion. To find the right barrel we move to next rounds. As no one died in the later rounds, we will know it is 0001 = barrel 1. If say 4th prisoner died in round 2, we will say 1002 = barrel 251 is poisoned.