Nov 9, 2009

The Bad King Problem

A bad king has a cellar of 1000 bottles of delightful and very expensive wine. a neighbouring queen plots to kill the bad king and sends a servant to poison the wine. (un)fortunately 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 1,000,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 at his anniversary party in 5 weeks time.

explain how...

12 comments:

  1. Is there any solution to this?

    ReplyDelete
  2. If his dungeon is really very vast, he could just give 1000 prisoners each one wine to try - only one prisoner need die!

    ReplyDelete
  3. Yes there is. You can solve for upto 1024 bottles of wine using 10 prisoners. Give it a shot its a beautiful problem :)

    ReplyDelete
  4. @anchan: That would rather mean killing far too many prisoners when it can be done using just 10

    ReplyDelete
  5. yes if there is only one bottle of wine that contains the poison.. n if he has a sample space of 1000..he vl end up killing only one prisoner if each one has a spoonful frm 1000 diffrnt wines

    ReplyDelete
  6. There are 10 prisoners and 1000 bottles. Clearly, each prisoner would drink a mixture of wine samples. And thus there might be a case when wine from a particular bottle goes into more than one such mixtures. So more prisoners might die.

    ReplyDelete
  7. Not if each prisoner only tastes one of the wines! Only one is poisoned, so only one will die.

    ReplyDelete
  8. consider a 10digit binary no.nos from 0 to 1024 can be generated using this 10 digit no, each representing 1 to 1024. so only 1 prisoner will die corresponding to the bottle number which is poisoned.

    ReplyDelete
  9. SOLUTION:
    ------------------------------------------------
    Label the wine bottles from 1 to 1000. Convert the labels into binary system> Thus, we'd get 10bit binary codes for all the wine bottles (since 2^10 is 1024).

    Take ten glasses and number them from 1 to 10. Now, Considering wine bottles 63 for instance. Its binary code would be 0000111111. So pour it into glasses 1,2,3,4,5 and 6 (i.e. where ever you get 1 in digits place in the binary code).

    Do this for all the bottles. and make those 10 prisoners drink wines in these 10 glasses.

    Based on how many prisoner die you'll be able to get 1s in the binary code. For instance, prisoner 1,4,6,9 and 10 die and rest remain alive. Thus, we can conclude that the poisoned bottle binary code would be 1100101001. Reconvert the binary code to decimal form. You'll get the answer.

    ReplyDelete
  10. @Freddo

    Would you care to elaborate on the logic behind this procedure?

    How are we able to accomplish (or make the answer apparent)it in the binary system and not in the decimal system?

    ReplyDelete
  11. Sorry dude.. got it .. was a little put off by the binary representation :P ..... but figured out the logic.. every number can be expressed as a sum of powers of two (that's how the wine sampling is done)... seems like a gem of a puzzle :)

    ReplyDelete
  12. I think there's a slightly more intuitive way to conceptualize this.
    Just work out the base cases (calculate the minimum people you need for 4-7 bottles) and you'll see what's going on.
    You have one bottle that all 10 pick. Then one bottle that noone pick. Then you have 10 bottles with 10 different sets of 9 people each picking. Then you have all the possible bottles with X different sets of 8 people each picking. How do you figure out all the different combinations of 9, 8, 7 people? Basically, it's just 10 choose 0 plus 10 choose 1 plus 10 choose 2 plus ... plus 10 choose 10.
    If I properly recall I think I may have proved at some point that the sum over 1<=n<=x of (x choose n) is equal to 2^n.

    ReplyDelete