Tech Interview

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

Solution

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.

number the bottles 1 to 1000, and write the number in binary format.

bottle 1    = 0000000001
bottle 250  = 0011111010
bottle 1000 = 1111101000

now take your prisoner’s 1 through 10 and 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 #924 would be sipped by 10,9,8,5,4 and 3. that way if bottle #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.

additional question: to increase your chance of living, which prisoner would you want to be?

if there were 1023 bottles, it wouldn’t matter since everyone would have to take 512 sips. but there are 23 bottles less, so the people whose bits would have been on from 1001 to 1023 won’t have to take a sip. 1001 is [11111 01001] in binary and 1023 is [11111 11111]. the most five significant bits are the most interesting because they would always be on from 1001 to 1023, so all those people are missing out on 23 bottles of wine that they otherwise would have had to drink. so in order to increase your chance of living, you’d probably want to be prisoner 6 to 10. (but depending on how the king determines who is least significant and who is most significant you could get shafted.)

note that if the king was really trying to kill the least number of prisoners, he should have let 999 prisoners each take a sip from their respective bottle numerically (if he had that many prisoners at his disposal). that way only one prisoner would die, and there’s a chance of 1/1000 that no one would die, but then the puzzle isn’t very fun