Fog Creek Software
Discussion Board




"bad king" slightly misstated

Either the "bad king" problem is slightly misstated, or I didn't read it carefully enough.

The problem as stated is find the bad wine while "murder[ing]" at most ten prisoners.

That's an unfortunate word.  The trivial solution (corrall 1000 prisoners, have each drink from a unique bottle, then you know which is the poisoned one at the cost of mudering only one prisoner) fits that description.

If the problem were stated to find the bottle while "involving" only ten prisoners, or if the problem stated that all prisoners involved in the solution had to be murdered later for secrecy, then the answer as stated is of course correct.

Yours sincerely etc.
  --JMike

J. Michael Hammond
Monday, July 15, 2002

Even if I don't have 1000 prisoners I can still improve my odds with every prisoner I add.

Given N prisoners where N = 10 + n

Take n bottles from the 1000 and give each of the n prisoners a bottle.  Take the remaining 1000-n bottles and proceed as the solution recommends.  If you are 'lucky', one of your n prisoners will die and you will have identified the poison with only one death.  Otherwise, you will kill off some set of the 10 prisoners and find the poison that way.

Every prisoner you add over 10 slightly improves the odds that none of the 10 will die.

William Frantz
Tuesday, July 23, 2002

Getting worse and worse...

I just realized that it takes a month to find out the results of poisoning prisoners.  That's a long time.  The more prisoners you add, the more chances are that your results will be tainted by the natural or accidental death of one or more of your prisoners.  You are going to have to be willing to toss some good wine just to be safe.

If I were one of the 10 and I knew what was going on, I would try to make a pack with the other 9 that we all kill ourselves if they make us drink wine (hey, we are all prisoners anyway).  That would completely ruin the experiment and might discourage the whole situation.

The king could just toss all the wine and save the lives of his prisoners, but he wants the wine for "his anniversary party".  Well come now, how many bottles will the king drink at his party?  Maybe 1 or 2, but not 1000.  Clearly the remaining wine is for his guests.  So either get 2 new bottles or just give 2 samples to 2 prisoners.  They only have a 1/1000th chance of dieing and the king will be safe.  Of course this raises the odds that somebody at the party will die, but who cares about them?  We only need to save the life of the king, right?

The other alternative is to use the 5 weeks before the party to build up an immunity to iocane powder.

"Clearly I cannot choose the wine in front of me!"

William Frantz
Tuesday, July 23, 2002

Now let's just wait a second here....

Who's to say that you have to have ALL of the bottles of wine sampled?  You only need to test 999 bottles... if none of the prisoners die, then you've identified the bottle you HAVEN'T tested as the poisoned bottle.

Cuts down on wasted wine and prisoners both, in the long run.

I started counting at Zero, just like any normal programmer would. :)

Stephen Hoffman
Wednesday, July 24, 2002

Not only will using 999 prisoners each taking one sip save on dead prisoners (1 or 0), but it will save wine, which the king probably cares more about.  Using the 10 prisoner solution, each bottle is sipped 5 times on average (5 of the 10 bits).  Using the 999 prisoner solution, they are only sipped once (and one, not at all).  So the king will have a lot more wine left.

The original solution only makes sense if the king only has 10 prisoners he's willing to risk killing.

Gil Milbauer
Wednesday, August 21, 2002

*  Recent Topics

*  Fog Creek Home