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?
Well... as long as it's a power of two, we can do a 'binary search' by doing half at a time.
In other words, if it were up to 128 (2^7), then we can test 64, then 32 (in which group has the poison), then 16 (in which group has the poison), etc.... and identify the poison in 7 tests.
But if we have
129 or more (up to 2^8=256), then it may take up to 8 tests.
So, it occurs to me, that we don't change the maximum, if that is the number of glasses of wine.
______________
But if there were more than 129, then you would want to be more useful that checking just one (you'd check n-128)... since then you have to potentially
binary search either group
So, to ensure that you're not going past the maximum, the number of glasses must be 129.
Edited on November 5, 2003, 9:41 am
first thoughts
