Main BLOGGER
Google
WWW THIS BLOG
Wednesday, April 06, 2005
 
An evil king and 1000 bottles of wine
An evil king has 1000 bottles of wine. A neighboring queen plots to kill the bad king, and sends a servant to poison the wine. The king's guards catch the servant after he has only poisoned one bottle. The guards don't know which bottle was poisoned, but they do know that the poison is so potent that even if it was diluted 1,000,000 times, it would still be fatal. Furthermore, the effects of the poison take one month to surface. The king decides he will get some of his prisoners in his vast dungeons to drink the wine. Rather than using 1000 prisoners each assigned to a particular bottle, this king knows that he needs to murder no more than 10 prisoners to figure out what bottle is poisoned, and will still be able to drink the rest of the wine in 5 weeks time. How does he pull this off?

1. using timing trick, like radix sorting,
credit to Bigswede
Use 10 prisoners. Label each prisoner with a digit, 0, 1,......,9 Label the bottles of wine 000, 001, ......., 999

On the first day, have each prisoner drink from all the bottles that have his digit in the 100's place. For example, prisoner labeled 3 would taste wine in bottles 300 to 399.
On the second day, same thing, except drink from each bottle with digit in ten's place. e.g. prisoner labeled 3 would drink from bottles 030, 031,..039, 130, ...139, ....930,..939.
On the third day, same thing, except drink from each bottle with digit in 1's place. e.g. prisoner labeled 3 would drink from bottle 003, 013, 023, ...093, 103, ......993.
Wait 31 days (a month) and see which prisoner dies. That gives the first digit (100's place) of the poisoned bottle.
The next day (32), if someone else dies, that gives the 2nd digit, and the third day (33), if someone dies, that gives the 3rd digit.
If nobody dies on day 32, the 2nd digit is the same as the first.
If nobody dies on both days 32 and 33, all three digits are the same (as the first digit).
If a prisoner dies on day 31 and another dies on day 32, but nobody dies on day 33, the bottle could be either of two bottles, with the 3rd digit the same as either the 1st digit or the 2nd digit. Throw both those bottles out.
To resolve this last case, we use a different group of 10 prisoners to taste the 1's digit bottles (at the start), so then someone would die on the 33rd day and the bottle would be uniquely identified. This method uses 10 prisoners, with at most 3 dieing, but 20% of the time, two bottles have to be thrown out, or it uses 20 prisoners, with at most 3 dieing, with only the single poisoned bottle having to be thrown out.

2. No timing trick, binary coding the bottle, 2^10=1024>1000
credit to Vineet Kumar

As for just the plain method, without much explanation: Line up the prisoners in order, each representing a bit. Number each bottle 1 to 1000. For each bottle, convert the serial number to binary, and give a sip to each prisoner corresponding to a 1 bit in the bottle number. After a month, see who dies. Each dead prisoner represents a "1" bit in the poisonous bottle's serial number. For example, if prisoners number 2, 5, 7 and 8 die, that looks like this: prisoner # 0 1 2 3 4 5 6 7 8 9 bit # 0 0 1 0 0 1 0 1 1 0 Assuming we're numbering with 0-9 instead of 1-10 and that 0 is the least significant bit, the number of the poisonous wine bottle is the sum of 2^(prisoner number) for each dead prisoner. In the above example, 0110100100 converted to decimal is 420, so bottle number 420 is the poison.

3. General analysis, credit to AlexH
Lets say we have k "windows" which represent the uncertainty of how long it takes for the poison to show. For example if we know the poison shows sometime between exactly 30 days and exactly 31 days after the poison is drunk, then if we start poisoning at 12am on day 1 we could have 5 windows,then one each for days 31,32,33,34,35 (assuming the wine is needed during day 36) so k=5 in this case. Now we need to label each bottle in base k+1 and have prisoner i drink from the bottle on day j if the ith digit is j and iff the ith digit is 0 he doesn't drink from the bottle at all. If we want to determine how few prisoners we need the answer is (log n)/(log k+1). If we fix a number m of prisoners and want to limit deaths then we need to get n sequences of m digits of base k+1 with the smallest possible bound on the number of non-zero elements. For example, if n=1000 bottles and k=5 windows then we can either use 4 prisoners with a substantial chance that all will die (6^4=1296>1000), or we can use 10 prisoners and have at most 2 die (there are 1176 10-digit base 6 strings with at least 8 0s).

The binary labelling scheme works just fine with 10 prisoners and no timing tricks. This is in fact exactly what my generalized system suggests if you plug in k=1 (i.e we can't do any timing tricks). log 1000/log (1+1) < 10. The optimum binary labelling uses all of the lables containing 0-7 deaths plus most of the labels containing 8 deaths, all together summing to 1000 labels.

Here are some numbers for 1000 bottles, with minimal deaths on 10 prisoners or with minimal prisoners. 1 window: (i.e. no timing possible) 10 prisoners --> at most 8 deaths, avg 4.916
2 windows:
7 prisoners, <=5 deaths, avg 3.567
10 prisoners, <=3 deaths, avg2.777
3 windows:
5 prisoners, <=5 deaths, avg 3.72
10 prisoners, <=3 deaths, avg 2.532
4 windows:
5 prisoners, <=4 deaths, avg 2.976
10 prisoners, <=3 deaths, avg 2.197
5 windows:
4 prisoners, <=4 deaths, avg 3.136
10 prisoners, <=2 deaths, avg 1.948



<< Home

Powered by Blogger

Google
WWW THIS BLOG