Fog Creek Software
Discussion Board




Comments: "Bad King"

http://www.techinterview.org/Puzzles/fog0000000070.html

Given how you guys comb through these, I was surprised to find not one, but two faults with this puzzle. :) It says:

    a bad king has a cellar of 1000 bottles of delightful and very expensive wine. [...] he knows he needs to murder no more than 10 prisoners [...]

He can arrange the numbering system so as to only kill a maximum of 9 prisoners, as he doesn't have to have a bottle that represents all the prisoners until he has enough bottles for a number with "all 1s" in binary. Sure, he's a bad king, and could number things so as to kill maximum prisoners, but 1000 bottles isn't enough to force the possibility of killing all 10. This might be a nitpick. ;)

In the solution, it says:

    solution: i'll give you a hint. 1000 is less than 1024. if there were 1024 or more bottles of wine it would take more than 10 prisoners.

1024 bottles could still be tested by 10 prisoners. Since you know the servant has definitely poisoned one bottle, there's no reason not to number a bottle "0" and have nobody drink from it. If nobody dies, then this is your poisoned bottle.

Brad Wilson
Saturday, November 17, 2001

Taking your argument one step further, couldn't you get away with killing a maximum of eight prisoners?

of the binary numbers with ten digits,

1 number has no zeroes,  11111 11111
10 numbers have one zero, 01111 11111, etc.
(10 choose 2 ) = 45 numbers have two zeroes.
 

Now since we only need 1000 numbers, we can eliminate the numbers with one or no zeroes from our scheme, this leaves 1024 - 11 = 1013 numbers, all of which have at most eight ones, so at most eight prisoners must die.  You can't make it less than eight because if you restrict further you wind up with less than a thousand numbers, and you can't label all the wines.

Ashwani Sastry
Thursday, November 22, 2001

Is this another way of solving the problem(?):

Let's say you divide the bottles into blocks of hundred (10 blocks of hundred).  You mix a little from each bottle in the blocks into an additional bottle. 

On the first day each prisoner will drink from his/her corresponsding block of hundred, i.e. prisoner one will drink from the first block, prisoner two from the second and so on.

Now, you divide the blocks of hundred into blocks of ten (10 blocks of ten for each block of hundred).  You mix a little from each bottle in the blocks into an additional bottle.

On the second day each prisoner drinks from his/her corresponsding blocks of ten, i.e. prisoner one will drink from the first block of ten of each block of hundred.

Finally, on the third day each prisoner drinks from the first bottle from each block of ten, i.e. prisoner one drinks a little from bottle 1, 11, 21, 31, etc.

Let's say bottle 508 was the one containing the poison.  Four weeks and one day later prisoner 5 would die.  That means all bottle in the fifth block of hundred could contain the poison.  The next day prisoner 1 would die, that means the first block of ten from the fifth block of hundred could contain poison.  The next day prisoner 8 would die, and the king would know which bottle is poisoned!  The great thing is that the maximum number of prisoners that will die is 3.

Marcus
Monday, December 17, 2001

Only *one* prisoner needs to die!

Note that the puzzle says: "the bad king decides he will get some of the prisoners in his vast dungeons" which I assume means that he has at least 1000 prisoners. If so, all he has to do is use 1000 prisoners, assign each one of the 1000 bottles to take a sip from, see which one dies, and throw away the bottle from which that prisoner drank.

Davide

Davide Andrea
Tuesday, December 18, 2001

I just wanted to make one correction to my solution above:

If bottle 508 is poisoned, the first prisoner to die is number 6, not 5, i.e. on the first day, prisoner 6 drinks from the block of bottles numbered 501-600.

For my solution I am also assuming, the King only wants to use ten prisoners, and that the poison takes exactly four weeks to show its effect.

Marcus
Tuesday, December 18, 2001

*  Recent Topics

*  Fog Creek Home