The Gateway to Computer Science Excellence

+6 votes

A bad king has a cellar of 1000 bottles of delightful and very expensive wine. A neighboring queen plots to kill the bad king and sends a servant to poison the wine. Fortunately (or say unfortunately) the bad king’s guards catch the servant after he has only poisoned one bottle. Alas, the guards don’t know which bottle but know that the poison is so strong that even if diluted 100,000 times it would still kill the king. Furthermore, it takes one month to have an effect. The bad king decides he will get some of the prisoners in his vast dungeons to drink the wine. Being a clever bad king he knows he needs to murder no more than 10 prisoners – believing he can fob off such a low death rate – and will still be able to drink the rest of the wine (999 bottles) at his anniversary party in 5 weeks time. Explain what is in mind of the king, how will he be able to do so ? (of course he has less then 1000 prisoners in his prisons)

+4 votes

Best answer

Suppose there are 1000 prisoners, each one of them can be given a sample of wine from each of the 1000 bottles and within 4 weeks, one must die and we know the poisoned bottle (assuming no one else dies due to other reason :D)

Now, let there be 999 persons. Now, we can have 1 person taste wine from 2 bottles and after 4 weeks, either one person dies or 2 persons die -> in any case we know the poisoned bottle.

**Now we can do smarter. **(Better solution)

Let the bottles be numbered $1,2,3, \dots , 1000$. Now, we can make two solutions from bottles $1-500$ and $501-1000$ respectively. Give these two to most troublesome prisoners. At least one must die within 4 weeks, but we cannot wait for it. So, simultaneously we proceed as follows:

For $1-500$ solution, we make another solution of $1-250$ and $251-500$ before head and similarly for $501-1000$. So, now we kill maximum 2 person and we find which of the 250 bottles contains the poisoned one.

Going like this, with 3 killing, we find 128 possible poisoned ones,

with 4, 64,

with 5, 32,

with 6, 16,

with 7, 8,

with 8, 4,

with 9, 2,

with 10, 1.

Essentially we are traversing a binary tree and we are sure to kill 10 person when we find the poisoned bottle. (King should ensure good prisoners are at bottom of tree and bad ones at top :D )

+3 votes

Lets think this problem with binary numbers..

10 prisoners are 10 bits

2 ^ 10 = 1024 bottles ( here it is 1000 )

Now , the solution

Arrange prisoners in order P1 P2 P3 P4 P5 P6 P7 P8 P9 P10

bottle 1 = 0000000001 Bottle 1 will be tasted by last prisoner (say P10 ) bottle 2 = 0000000010 Bottle 2 will be tasted by 2nd last prisoner (say P9 ) bottle 3 = 0000000011 Bottle 3 will be tasted by 2nd last and last prisoner (say P9 and P10 )

So on... After one month Arrange prisoners in same order . Died prisoner =1 Living prisoner is=0 read the bit and find the bottle

+2 votes

To simplify lets consider the case for 8 bottles first, we can represent the search tree for this case as in the diagram below:

The first prisoner coloured blue drinks solution form 4 bottles( B5, B6, B7 & B8), second prisoner coloured green drinks two solutions made from two bottles each(B3 & B4, B7 & B8), third prisoner coloured red drinks from 4 bottles (B2, B4, B6, B8). Now based on who dies and who doesn't we can figure out which bottle contains to poison. Consider the case in which no prisoner dies, then we know that B1 contains the poison since it is the only bottle which wasn't part of any solution that the prisoners drank.

Now for n=1000 we will have a binary tree with height of 10 and for each level (excluding root) we need only 1 prisoner, so at most 10 prisoners will die.

0

So, we should go to such a depth of the tree which equals the no. of prisoners (in a single leaf node) rt?

+1

@Arjun sir, first divide the bottle in 2 set. each set 500

then mix that some portion of each of fyrst 500 bottle in 1 glass and next 500 in other glass

Now there are 2 solution

give 2 prisoner to drink,

One must be dead

Now go to that side 500 bottle , from which side mixture drink by the prisoner

Now divide divide those bottle in 250 - 250 and again get 2 mixtures

then mix that some portion of each of fyrst 500 bottle in 1 glass and next 500 in other glass

Now there are 2 solution

give 2 prisoner to drink,

One must be dead

Now go to that side 500 bottle , from which side mixture drink by the prisoner

Now divide divide those bottle in 250 - 250 and again get 2 mixtures

+1

@srestha one can die after 4 weeks and we have totally 5 weeks before which we must find the bottle. So, we cannot wait in serial for not more than 1 person to die.

+1

I think , No need to wait

go like binary tree , and max 10 prisoner affected go through that leaf as u told :)

go like binary tree , and max 10 prisoner affected go through that leaf as u told :)

52,345 questions

60,503 answers

201,881 comments

95,331 users