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?

Hmm! Interesting. I'm sure I had a comment all lined up - but it has disappeared.
I wanted to comment on the expression 'minimise the maximum', which must be a feature of the method used. I agree that the binary approach gives the smallest maximum number of samples. If there are 128 glasses this number is exactly 7; if 129-256 it a maximum of 8. As has already been shown, the only way taking a single sample can fit in with the binary approach is if there are only 129 glasses.

I have a gripe though. The question says that the detective is concerned about wasting a test. True, taking a single sample might solve the problem in 1 - but that is very unlikely; and after that 7 further tests are needed. By dividing the sample 65/64 it is probable that only 7 tests in all would be needed. The maximum might not change, but a test is likely to have been saved. And it could be argued that this is the more pragmatic approach. However, it would not have given rise to the problem. Might this suggest that mathematicians are more concerned about interesting problems than pragmatic solutions? I do hope so.

And now in the hope that this makes it through the ether ... here goes

Posted by DrBob on 2003-11-07 15:58:13