Sunday, October 14, 2012

problem about king and prisoners

I describe this problem as a story....;)
Once a upon a time there was a king and one day he prepared a party for his family . There was exactly thousand of wine bottle for this party. But a rebel puts poison in a wine bottle to assassinate the king and somehow king knew that and he wanted to find that poisoned bottle before the party. There was one day to begin the party. So he ordered his servants to use king's prisoners to find that bottle. It will take couple of hours to die after drinking this poisons.
The challenge is finding the poisoned bottle using minimum number of prisoners.
I heard this probelm from viduneth

6 comments:

  1. Your interest "Hacking"

    ReplyDelete
    Replies
    1. yeap. but don't know too much...that is a very interesting field. isn't it....;)

      Delete
  2. My guess is around 7.... :-)

    I didn't work it out completely. But I thought maybe the approach would be something like a binary search.

    Of course, if we assume that initially we would have a fixed number of prisoners and at each pass a prisoner would die, then you have to have the correct number of prisoners to find the bottle in the needed number of passes.

    So assuming that at each pass we are going to be one prisoner less, if we need x number of prisoners, at each pass it is going to be like 1000/x/(x-1)/(x-2) ... and so on. This is like factorials, so calculating factorials other way round, you get 6! = 720 which is not enough, so have to go for 7! > 1000.

    Of course, that is just my two cents worth. There is probably a better approach... :-)

    ReplyDelete
    Replies
    1. Ayye, we have to find the bottle in one pass because as I mentioned after drinking from poisoned bottle it will take couple of hours to see the effect. we have one day to the party. assume it will take 23 hours to die after drinking poisons. now find the used minimum number of prisons. we don't worry about the number of prisoners who will die. the exact thing is using minimum number of prisoners...:)

      Delete
    2. @sunrong: what is the explanation?..:)

      Delete