5,705 views
6 votes
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 Answers

Best answer
5 votes
5 votes

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 )

selected by
6 votes
6 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
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 votes
0 votes
We can take advantage of the fact that the anniversary is in $5$ weeks and not $4$.

We have more $7$ more days apart from the month.

So, so, we divide bottle as:

$1$ to $143 (1000/7)$ and give them to $log_2 (143) = 8$ prisoners on $1^{st}$ day (Block $1$)

$144$ to $286$ and give them to $log_2 (143) = 8$ prisoners (same as those of 1st) on $2^{nd}$ day. (Block $2$)

And same way we continue. Of course number, the prisoners and maintain the order.

If some prisoners die on say after a month and on $x^{th}$. Then refer the Block $x$ and convert to decimal and add offset of $x{th}$ day. like in 2nd block we add $143$. On 3rd we add $2*143$ and so on…

So, King might kill at most $8$ prisoners.

But, we won’t ever kill all $8$ we may only kill at most $7$ but those may be any of given $8$, so we need 8 prisoners to test.

Related questions

0 votes
0 votes
1 answer
3
Kabir5454 asked Sep 26, 2022
653 views
Why magic square problem algorithm works ? Problem :- https://en.wikipedia.org/wiki/Magic_squareAny proof for the algorithm of problem why the algorithm works ?