**Problem:**

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)

**Solution:**

Think in terms of binary numbers. (now don’t read the solution, give a try).

Number the bottles 1 to 1000 and write the number in binary format.

bottle 1 = 0000000001 (10 digit binary)

bottle 2 = 0000000010

bottle 500 = 0111110100

bottle 1000 = 1111101000

Now take 10 prisoners and number them 1 to 10, now let prisoner 1 take a sip from every bottle that has a 1 in its least significant bit. Let prisoner 10 take a sip from every bottle with a 1 in its most significant bit. etc.

prisoner = 10 9 8 7 6 5 4 3 2 1

bottle 924 = 1 1 1 0 0 1 1 1 0 0

For instance, bottle no. 924 would be sipped by 10,9,8,5,4 and 3. That way if bottle no. 924 was the poisoned one, only those prisoners would die.

After four weeks, line the prisoners up in their bit order and read each living prisoner as a 0 bit and each dead prisoner as a 1 bit. The number that you get is the bottle of wine that was poisoned.

1000 is less than 1024 (2^10). If there were 1024 or more bottles of wine it would take more than 10 prisoners.

One way of looking to refine the solution is as follows:

It should take only 8 prisoners. One can utilize the fact that there are 5 days in between the 1st day of results of probable deaths and the king’s anniversary. From the 30th day to 34th day we have 5 days to see which group of people die. Proceeding as in the above solution, we require 8 prisoners only. 1000/5=200, 200<216, i.e. 2^8. So it takes only 8 prisoners.

But again, if some of the prisoners die from the 30th day to the 34th day, it might become stochastic to figure out the only poisoned bottle. Hence it requires all 10 prisoners to figure it out correctly all the 999 pure wine bottles that the king can drink.

There can be another solution. arrange 1000 bottles into 10 squares. each square contains 100 bottles arranged in 10 rows and 10 columns.

each prisoner drinks all 100 bottles from one square and also drinks all bottles from one row and one column in all other squares.

For eg prisoner 1 drinks all bottles from square 1 and all bottles in row1 and column 1 of square2, row 1 and column 1 of sq3, row1 and col1 of sq4..till sq 10. prisoner 2 drinks all 100 bottles from sq 2 and all bottles from row2 and col2 of sq1, row 2 and col2 of sq3,etc till sq10.

now assume the bottle is in row 2 col 5 in sq 1 (random assumption)

so prisoner 1 will die, prisoner 2 will die and prisoner 5 will also die. hence we know the co-ordinates of the bottle. this will happen for any case. 3 prisoners out of 10 will always die and give us co-ordinates.

If prisoner 1 dies, prisoner 2 dies and prisoner 5 also dies, how are u sure that its the bottle in row 2 col 5 in sq 1 and not in row 5 col 1 in sq 2 or row 1 col 2 in sq 5 ?? There are 9 possibilities .. U have to omit 9 bottles then and wouldn’t get 999 but 991 instead.

Simple solution could be,

Put numbers 1 – 1000 to each wine bottle & 1 – 999 to each prisoners. And if King has 999 prisoners, we can follow this procedure.

Divide all the bottle into groups of 2. Now there are 500 groups of wine bottles and let first 500 customers drink wine from one group (i.e. from two wine bottles in that group).

And let 500th prisoner drink only from 999th bottle

Put each of these prisoners into 500 different cells. Now, next 499 prisoners will drink wine from only odd number of bottle (i.e. 501th prisoner will drink from 1st wine bottle; 502nd will drink from 3rd wine bottle & .. 999th will drink from 997th bottle).

If by the end of the month only one prisoner dies, wine bottle from that group with even number is poisonous. If prisoner from last cell (500th) cell dies then 999th bottle is poisonous. If no one dies then 1000th bottle is poisonous.

read the question carefully before u answer…..

Why kill 10 prisoners, when you can do the job by just killing 1?

Pick 999 prisoners and number them. Have them taste from bottle number 1 to 999 respectively. After 1 month see which prisoner dies – corresponding bottle has the poison. If nobody dies, bottle number 1000 is the culprit – so there is a chance that nobody is murdered.

This way, it takes even less time – only 4 weeks.

Perhaps.. this is the simplest answer.. but Quiz should have condition that you dont have those many prisoners.. or how can you detect the bad bottle with less number of prisoners..

Idea from Radix sort can be used to solve this.

1. Number the bottles starting 0 till 999 i.e. 1000 bottles.

2. Make 3 groups of 10 prisoners each i.e. total 30 prisoners required.

3. Mix a sip of wine from each bottle with number at unit place is as 0 i.e. bottle number 000, 010, 020, 030, ……..,990. Do the same for number at unit place as 1, 2 3….9.

4. Pick first group of prisoners (Unit Group) and let them sip the mixtures made with different numbers at unit place i.e. prisoner 1 of unit group sips the mixture made by bottles with number at unit place is as 0 and so on for rest of the prisoners of this group.

4. Similarly do step three with different digits at tens & hundreds places i.e. with bottle number 000, 001, 002,…..100, 101 ,102,……909 for 0 at tens place and 000, 001, 002,…..099. And let other two group of prisoners Tens Group & Hundreds Group sip this mixture in the same way.

5. At the end of 30 day 3 prisoners will die, 1 from each group and by their number you can figure out which bottle number was having poison.

The quiz doesn’t really say how many prisoners the king has, it say only that he has less then 1000; if he has more then 10 then the solution can be different from the one proposed.

A possible solution is

Make each of the 10 prisoners to drink a sip from 100 bottles each.

one of them will die…now we are narrowed down to 100 bottles(which the dying person was assigned)

similarly we will divide those 100 bottles between 9 prisoners..say 11 bottles per person.when one of them dies we are narrowed down to 11 bottles(If none dies we have our poisoned bottle)

again we will divide those 11 bottles between 8 remaining prisoners..each of them drinks only one and we can get our poisoned bottle.if none dies we know that the poison is in one of the remaining 3 bottles.

This way we have killed only 4 prisoners and will still get the solution.

please let me know if there is anything wrong with this procedure

Your answer has time limit problem. As it is mentioned, king has anniversary in 5 weeks and he has to utilize remaining 999 bottles on that day. In your case, it will take 12 weeks.

1000/10=100 make 10 set of 100-100 bottles and after that give one set to one prisoners definitely effected bottle will come in one set and respective prisoner will die and we have 100 bottle and 9 prisoners 100/10=10 so make 10 set of 10-10 bottles and give one-one set bottle to each prisoners so now may be possible that one out of 9 will die or not any one because effected set of bottles may be assign or not to a prisoner if one out of 9 prisoner will die then we will get effected 1set of bottles or if no body will die that means remaining or unassigned set of bottles was effected so now u have only 10 bottles and 9 or 8 prisoners and now 10/2 =5 now you have 5 set of bottles and 8 or 9 prisoner select 5 prisoner out of 8 prisoner and assign each prisoner a set of bottle any one prisoner will die so now you that one out of 2 bottle if affected by poison now select 1 prisoner and give one bottle at a time to prisoner to take a sip so now problem solved without make any more affords.

Think in terms of binary numbers. (now don’t read the solution, give a try).

Number the bottles 1 to 1000 and write the number in binary format.

bottle 1 = 0000000001 (10 digit binary)

bottle 2 = 0000000010

bottle 500 = 0111110100

bottle 1000 = 1111101000

Now take 10 prisoners and number them 1 to 10, now let prisoner 1 take a sip from every bottle that has a 1 in its least significant bit. Let prisoner 10 take a sip from every bottle with a 1 in its most significant bit. etc.

prisoner = 10 9 8 7 6 5 4 3 2 1

bottle 924 = 1 1 1 0 0 1 1 1 0 0

For instance, bottle no. 924 would be sipped by 10,9,8,5,4 and 3. That way if bottle no. 924 was the poisoned one, only those prisoners would die.

After four weeks, line the prisoners up in their bit order and read each living prisoner as a 0 bit and each dead prisoner as a 1 bit. The number that you get is the bottle of wine that was poisoned.

1000 is less than 1024 (2^10). If there were 1024 or more bottles of wine it would take more than 10 prisoners

Debs gave the simplest answer possible but why using 999 prisoner, it can be done with 1 prisoner only and in I month 998 seconds.

Take one prisoner and let him have a sip from first bottle.

After 1 sec

Take same prisoner and let him have a sip from second bottle.

Again After 1 sec

Take Same prisoner and let him have sip from third bottle.

Again After 1 sec

Take Same prisoner and let him have sip from fourth bottle.

SIMILARLY

Take Same prisoner and let him have sip from 999th bottle.

If After 1 month , prisoner dies…then 1st bottle is poisoned…

If After 1 month and 1 sec , prisoner dies…then 2nd bottle is poisoned…

If After 1 month and 2 sec , prisoner dies…then 3nd bottle is poisoned…

….

….

If After 1 month and 998 sec , prisoner dies…then 999th bottle is poisoned…

And if he never dies then 1000th bottle is poisoned.

if 10 prisoners drinks one sip from each bottle with binary one. how much would be left for the king !!!!

Why not use 3 dimensional matrix. i.e., arrange the bottles in a 10x10x10 in X, Y and Z axis. Day 1: Each prisoner drinks 100 bottles corresponding to his number along the X axis. That is, 111,112,113, 211,212,221,222 and so on. 2 days later, change the axis over to the Y axis. 2 days after that, change to the Z axis. After 4 weeks, in case prisoner number 3 dies, then you know that the X co-od is 3. After 2 days, if prisoner number 5 dies, you know the Y co-od is 5. In case no one dies, the Y co-od is also 3. Another 2 days later, if prisoner 7 dies, then Z co-od is 7. Hence, the bottle at 3,5,7 is the culprit. In case only prisoner 3 dies and no one else dies, then 3,3,3 is the poisoned bottle.

Just 3 prisoners will die. Arrange those bottles in cube of 10*10*10 in X,Y,Z direction.

For each row in direction put 1 prisoner for each place now late them drink sip from all bottles in that row. 3 prisoners will die and you will gate exact position of that bottle

if we know the result at least one month (4 weeks) there is no way to know except my way.

Just mix whole bottles together after that put it back to bottles.

now we have 1000 poisonous bottles.

Actually the 10x10x10 matrix won’t work. Suppose after four weeks no.3 dies. Then x coordinate is 3. After two days no. 8 dies. So the y coordinate is 8. Now no one dies two days later. So the z coordinate can be either 3 or 8 and hence the bottle can be at 388 or 383 and we will never be able to know.

Guys there is one more simple solution that is just take 500 prisoners n make a set of 2 bottles fr each prisoner…

Each one of them drink sip frm one of the bottle of their set on day 1 and aftr 3 days drink ship frm another bottle of their set.

So if aftr 30 days anyone of them dies thn find tht bottle which he drink on fst day… tht bottle contains poison…

Otherwise if anyone dies on day 33 tht means the bottle which he drink on 3rd day contains poison…

So that’s it we find that bottle before 5 weeks.

why cant we use 1000 prisoners so that only one of them would die

Using 999 prisoners which is 1 less than 1000 prisoner.

He will kill only 1 prisoner worst case ,which is less than 10 prisoner.

Make all of them have a sip from 1 of 999 bottles if any one of them dies the bottle which he drank from is poisonous.

if none dies the bottle from which no one drank was poisonous.

He gets 999 bottles at the end of one month.