A Bottle of Poisoned Wine
Once upon a time there was a king who had owned 1000 bottles of wine, which were going to be used to treat his guest at a huge party. However, 22 hours before the party, the king received a message saying that one (and only one) of the a thousand bottles was poisoned. The poison was specially designed so that the person poisoned would not show symptom until 20 hours later.
The king had tens of thousands of slaves (sorry if you are against slavery) working for him on a construction project, all of whom the king could use to test the poisoned bottle. Taking out laboring slaves, however, would make the project progress slower; therefore, the king wanted as few slaves a possible.
Question: what is the minimum number of slaves needed to test the poisoned bottle? Assuming the process of drinking sample wine takes very little time compared to 20 hours.
The answer is 10.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
In simple words, 10 slaves minimum are needed because 512<1000<1024
If you are not very good at abstract thinking, read the following specifics.
First, label the 10 slaves from 1 to 10
Second, label the 1000 bottles from 1 to 1000.
Here comes the tricky part: the ten slaves will eventually drink samples from all a thousand bottles collectively, but in the following manner.
For example, when bottle 167 is tested: 167 in decimal system is converted to 10100111 in binary 1 appears in first, second, third, sixth, and eighth digit so let slave No. 1,2,3,6,8 drink sample of this bottle
repeat the similar process until all 1000 bottles are tested; this entire process should be negligibly time-consuming
wait for 20 hours until symptoms are all fully developed
See which slave(s) have the symptom: for example, if slaves No. 1,3,5,6,8 have developed symptom, then accordingly write a binary number whose first, second, fifth, sixth, and eighth digits are 1, like 10110011
convert 10110011 back to decimal, which would be 179; therefore, the bottle labeled 179 is poisoned.
This is an inhumane model of a computer if you think you have heard of this idea before.