The police commissioner hired a mathematician to help at a crime scene. At the scene were between 100 and 200 glasses of wine. Exactly one glass was poisoned. The police lab could test any sampling for poison. A group of glasses could be tested simultaneously by mixing a sample from each glass. The police commissioner desired only to minimize the maximum possible tests required to determine which exact glass was poisoned.

The mathematician started by asking a detective to select a single glass at random for testing. "Wouldn't that waste a test?", the detective asked. "No, besides I'm in a gambling mood.", the mathematician replied. How many glasses were there?

(In reply to re: Waste a test by SilverKnight)

It is likely you will waste a test. Imagine that there were 129 glasses and you divide in two groups of 64 and 65. If the poisoned glass was in group of 64, you could continue with the binary test to the end without wasting a test. If it was in 65 group, you would again divide in 32 and 33 and if the poisoned one was in 32 group, you would not need to waste a test. The probability that the poisoned glass will keep appearing in the odd group all the time to the end (one exception - in second last test when there are 3 glasses left, it will appear in group of 2) forcing you to take one more additional test (8th test instead of just 7) is 2/129, which is about 1,55%.

So, when calculating the average number of tests needed when using the method of wasting one glass first and having 129 glasses, we get 1/129+8*128/129= cca 7,95 tests in average. Explanation - there is a probability of 1/129 of needing just one test and probability of 128/129 of needing 8 tests (including the wasted one).

In case of a 'standard' method, we get 8*2/129+7*127/129=cca 7,02 tests in average. This is significantly better than wasting one test.

Perhaps there is other, more subtle solution?

Posted by Saso on 2003-11-06 12:07:00