King and Wine Bottles

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)

king-wine-bottle

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.

31 Thoughts on “King and Wine Bottles

  1. 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.

  2. juilee on July 18, 2014 at 9:31 am said:

    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.

  3. Swap on July 25, 2014 at 6:04 pm said:

    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.

  4. 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..

  5. 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.

  6. 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.

  7. Ritu Raj on January 8, 2015 at 2:20 pm said:

    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

    • Simrandeep on March 3, 2015 at 12:51 am said:

      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.

  8. Er Chirag Sharma on January 12, 2015 at 6:34 am said:

    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.

  9. Rishabh Sakhare on January 21, 2015 at 8:31 am said:

    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

  10. Aditya on April 3, 2015 at 12:22 pm said:

    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.

  11. Shiv on April 7, 2015 at 4:10 pm said:

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

  12. Jayanth on July 25, 2015 at 6:30 pm said:

    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.

  13. Mangesh Kharat on October 5, 2015 at 6:51 pm said:

    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

  14. LEE INHO on November 10, 2015 at 4:50 pm said:

    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.

  15. 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.

  16. sujeet pratap Singh on July 14, 2016 at 2:55 pm said:

    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.

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

  18. Surendra on May 28, 2017 at 7:35 pm said:

    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.

  19. Eugene on October 25, 2017 at 3:52 am said:

    What if we let every prisoner of 10 drink a sip of 999 bottles: 1st prisoner drinks sip from 1 to 1000 except 1, 2nd drinks from 1 to 1000 except 2 etc.
    In a month all prisoners will die except one, and we know from which bottle he did not drink.

  20. Eugene on October 25, 2017 at 4:02 am said:

    Please do not post my response, it is not correct: we would need 1000 prisoners to check all the bottles.

    It seems binary response is the only one correct answer.

  21. 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.

    How prisoner 2 to 9 will sip, in which pattern ?

  22. manish sharma on August 31, 2019 at 3:53 pm said:

    Very simple solution:
    Let’s make 999 glasses
    1st glass – 1&2 mixed
    2nd glass – 2&3 mixed
    3rd glass -3&4 mixed
    ….
    999th glass – 999 & 1000 mixed
    they are given to 1000 different prisoners
    let’s take if 1&2 glass prisoners get killed then bottle 2 contains the poison and so on.

  23. Since, there is no limit to take prisoners. King take 1000 prisoners corresponding to 1000 bottles and give only a sip to respective bottles and labeled them accordingly. After 1 month he will get to know which is poisoned bottle and only 1 prisoner will be killed.

  24. Bugmaster on February 11, 2020 at 8:17 am said:

    Where is that servant? Im sure we can persuade him to talk which bottle is poisoned. The king is bad after all.

  25. Jatin Kataria on September 9, 2020 at 1:32 pm said:

    I have an alternative approach:
    Divide 1000 bottles into 10 batches where each batch will have 10 bottles.
    Let the batches be B1,B2,…,B10 and bottles in each batch be b1,b2,…,b10. Therefore, each bottle can be represented by a unique identifier eg. B1b3 means Batch 1 bottle 3
    Let 10 prisoners be represented as P1,P2,…,P10

    Assume B2b4 is the bottle that’s poisoned. Now to identify it let us make the prisoners drink small sips from bottles in the following way–>

    1st combination of drinking (All batches for all prisoners but bottle number fixed):
    P1= B1b1+B2b1+…+B10b1
    .
    .
    P4= B1b4+B2b4+…+B10b4
    .
    .
    P10=B1b10+B2b10+…+B10b10

    2nd combination of drinking after they were made to drink the 1st ( batch numbers are fixed but all bottles for all prisoners):

    P1= B1b1+B1b2+…+B1b10
    .
    .
    P2= B2b1+…+B2b4+…+B2b10
    .
    .
    P10=B10b1+B10b2+…+B10b10

    At the end of 1 month, we find that P2 and P4 die which will tell us that the only common factor between the two prisoners was the bottle B2b4 from the above 2 combinations and hence B2b4 was the poisonous bottle.

  26. Patel Taksh on July 25, 2021 at 4:18 pm said:

    If there is no limitation on no of prisoners then
    king can arrange all bottles in 25*40 matrix, king can make 25 glasses containing wine from 40( which are placed in that row/column) bottles and doing same other 40 glasses containing wine from 25 glasses ( which are placed in that row/column).
    Now take ( 40 + 25 ) prisoners and let them drink each one ,
    Only 2 of them will die and we can trace back Poisoned Bottle.
    ( for example , if from those 40 prisoner 5th prisoner and from 25 prisoner 12th will die then
    poisoned bottle = matrix[12][5] or [5][12] ( which ever way matrix was designed ) )

    also , 40*25 is the factors with lowest sum . So Minimum prisoners and casualties = 2

Leave a Reply to Mauro Cancel reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation