The Poisoned Glass
PooSung Park
the police commissioner said to his wife.
"You see, we had all those partly filled glasses
lined up in rows on a table in the hotel kitchen.
Only one contained poison, and we wanted to know which one
before searching that glass for fingerprints.
Our laboratory could test the liquid in each glass,
but the test take time and money,
so we wanted to make as few of them as possible.
We phoned the university and
they sent over a mathematics professor to help us.
He counted the glasses, smiled and said:
'Pick any glass you want, Commissioner.'
'But won't that waste a test if we test it first?' I asked.
'No,' he said,
'you didn't understand at all.
Choosing one is just part of the best procedure.
We won't test that first.'"
"How many glasses were there to start with?"
the commissioner's wife asked.
"I don't remember. Somewhere between 100 and 200."
What was the exact number of glasses?
(It is assumed that any group of glasses can be tested simultaneously
by taking a small sample of liquid from each,
mixing the samples and making a single test of the mixture.)
Darren Rigby
I'm guessing the intended answer is 128. Here's what I'd do:
Pick any 64 glasses, take a small sample from each, mix and test. If poison
is found, take the 64 glasses you sampled before, and repeat the process
with half of those glasses. If no poison is found, take the unsampled glasses
and pick half of those. This system will identify the poisoned glass in 7
tests.
However, any number of glasses from 100 to 128 can be checked in 7 tests,
(less if you're lucky) and any number from 129 to 200 in 8 tests (again
less if you're lucky).
I don't understand what that was the professor said. ``Pick a glass and we
_won't_ test it.'' (It also seems like a slightly dodgy method of committing
a murder. How could the police know one glass is poisoned, but not know who
the intended victim is? And if all the glasses are gathered together on one
table, say, then no one, not even the killer, would know who picks up the
poisoned glass!)
--
djr={gridby, dart, axoq}
David Karr
> We phoned the university and
>they sent over a mathematics professor to help us.
> He counted the glasses, smiled and said:
> Choosing one is just part of the best procedure.
> We won't test that first.'"
> What was the exact number of glasses? [between 100 and 200]
It seems clear that the "mathematics professor" was not a true
mathematician at all, but rather an imposter, and so nothing can
be determined from what he said; since he is not a mathematician,
he could have come up with any silly procedure for any number of
glasses for some obscure reason.
A real mathematician (or a real computer scientist, for that matter)
would have known that the most efficient procedure is a search on a
*balanced* binary tree, that is, a tree with two children of each node
and with the leaves either all at the same distance from the root or
some just one link further from the root than the rest. The first
test to make would be on a sample collected from (perhaps
approximately) half the glasses. In extreme cases (for example, with
192 glasses), that first collection could include anywhere from 1/3 to
2/3 of the glasses. But it could not be anywhere near 1 or N-1 out of
N total glasses, for N >= 100.
An unbalanced binary tree may have the same worst case number of tests
required to find the poison as a balanced tree, but on average it will
require us to make more tests. That's because if a tree is not
balanced, you can always reduce the average distance of its leaves
from the root by moving some of the most distant leaves closer.
-- David A. Karr (ka...@cs.cornell.edu)
Lee Shere
> "Mathematicians are curious birds,"
>the police commissioner said to his wife.
>
> "You see, we had all those partly filled glasses
>lined up in rows on a table in the hotel kitchen.
> Only one contained poison, and we wanted to know which one
>before searching that glass for fingerprints.
> Our laboratory could test the liquid in each glass,
>but the test take time and money,
>so we wanted to make as few of them as possible.
>they sent over a mathematics professor to help us.
> He counted the glasses, smiled and said:
>
> 'But won't that waste a test if we test it first?' I asked.
> 'No,' he said,
> 'you didn't understand at all.
> We won't test that first.'"
>
>the commissioner's wife asked.
>
> "I don't remember. Somewhere between 100 and 200."
>
>by taking a small sample of liquid from each,
>mixing the samples and making a single test of the mixture.)
>
leaving 128 to be tested in the "binary" method, as others have
already outlined. Lee
Kim Kerler
John Hakemian
'ka...@cs.cornell.edu (David Karr)' wrote:
>In article <4jbbgf$n...@snunews.snu.ac.kr>, PooSung Park wrote:
>>they sent over a mathematics professor to help us.
>> He counted the glasses, smiled and said:
>> We won't test that first.'"
>
>It seems clear that the "mathematics professor" was not a true
>mathematician at all, but rather an imposter, and so nothing can
>be determined from what he said; since he is not a mathematician,
>he could have come up with any silly procedure for any number of
>glasses for some obscure reason.
>
>A real mathematician (or a real computer scientist, for that matter)
>would have known that the most efficient procedure is a search on a
David,
I agree with everything you said. But I"ll bet that the answer that the
poster was looking for was 129 glasses, as one more than the only power of
two that falls between 100 and 200; my guess is that the "professor"
planned to do a binary tree search on the other 128, winding up either
finding the correct glass in seven tests, but if he fails (i.e. the seventh
test, a single glass from the two left in the tree, is negative), then
doing a eighth test of (or against) the single "reserved" glass.
Best regards.
--
/| John Hakemian, aka
//|\ sail...@nyc.pipeline.com
///|\\ Chesapeake Isle MD
////|\\\ and NYC
__/////|\\\\__ PANACHE on the Chesapeake
/ PANACHE/ PANACEA in the BVI
~~~~~~~~~~~~~~
David Moews
PooSung Park <sung@I_should_put_my_domain_in_etc_NNTP_INEWS_DOMAIN> wrote:
| "Mathematicians are curious birds,"
|the police commissioner said to his wife.
| "You see, we had all those partly filled glasses
|lined up in rows on a table in the hotel kitchen.
| Only one contained poison, and we wanted to know which one
|before searching that glass for fingerprints.
| Our laboratory could test the liquid in each glass,
|but the test take time and money,
|so we wanted to make as few of them as possible.
|they sent over a mathematics professor to help us.
| He counted the glasses, smiled and said:
| 'But won't that waste a test if we test it first?' I asked.
| 'No,' he said,
| 'you didn't understand at all.
| We won't test that first.'"
|the commissioner's wife asked.
| "I don't remember. Somewhere between 100 and 200."
|by taking a small sample of liquid from each,
|mixing the samples and making a single test of the mixture.)
If there are 129 glasses, we can perform a binary search of 7 tests on
128 of the glasses, leaving aside the glass the police commissioner chose;
this will be successful unless, with probability 2/129, all our tests come up
negative, when we must test again to determine whether the poison is in the
odd glass out. This requires 7 + 2/129 = 905/129 tests on average, which is
optimal. If there are 127 glasses, the police commissioner's glass can be
set aside and all the remaining glasses grouped in 63 pairs; then a binary
search can be run on the 64 resulting entities; an additional test will be
needed 126 out of 127 times, for a total of 7 - 1/127 = 888/127 tests on
average, which is also optimal.
Unless the number of glasses is 1 more or 1 less than a power of 2, it
is not possible to construct an optimal search procedure which distinguishes
a unique glass. Hence there were 127 or 129 glasses.
PS: When I saw this puzzle in the `Mathematical Games' section of SCIENTIFIC
AMERICAN, the answer given was 129, but the reason given was that
testing a glass first leaves the worst-case number of tests at 8. As
David Karr points out, this is inadequate justification. I think that the
poster has reworded the puzzle in order to avoid this interpretation.
--
David Moews dmo...@xraysgi.ims.uconn.edu
David Karr
>'ka...@cs.cornell.edu (David Karr)' wrote:
>>
>>A real mathematician (or a real computer scientist, for that matter)
>>would have known that the most efficient procedure is a search on a
>
> I agree with everything you said. But I"ll bet that the answer that the
>my guess is that the "professor"
Oops, did I forget to mention 129? I should point out, however,
that if you do a binary search on the "other 128" ignoring the
129th glass until the end (and then only if it becomes relevant),
you are essentially searching a balanced binary tree. The first
test will be on 64 glasses, leaving 65 untested glasses at that
stage.
On the other hand, maybe the person *was* a real mathematician. I'm
reminded of the story about the mathematician who was asked to make a
cup of tea, and had to fill a pot, put it on the stove, etc. The next
day, someone asked him to make tea again, but this time there was a
pot of water already on the stove. The mathematician poured it out
and declared, "Now we've reached a problem we've solved before, so
we're done."
David Karr
>Unless the number of glasses is 1 more or 1 less than a power of 2, it
>is not possible to construct an optimal search procedure which distinguishes
>a unique glass. Hence there were 127 or 129 glasses.
But in what way was the single glass "distinguished" in either of these
protocols? Only in that you decided to give a special connotation
(largely irrelevant to choosing the glasses for the first few samples)
to one glass out of many that will not be sampled at first.
You could, of course, take any number of glasses, name one of them
Matilda, and make sure you don't test Matilda right away. Now Matilda
is "distinguished" from the other glasses in your protocol.
OK, let's try that a little more constructively. Set Matilda aside.
Now form the remaining glasses into a "set of suspects" and search
them as follows:
1) Take samples from half the glasses in the set of suspects
(exactly half of them if the number is even, round up
if the number is odd) and test the combined sample.
2) If there was poison in the sample, the sampled glasses become
the new set of suspects. If not, remove the sampled glasses from
the set of suspects.
3) If there is more than one glass in the set of suspects, continue
from step 1.
4) If the single remaining glass in the set of suspects has never
been included in a sample that tested positive for poison, test
it now. If it does not contain poison, the poison is in Matilda!
In other words, in any maximally efficient procedure for finding the
poisoned glass from any number of glasses, there is one glass that
will never be sampled for testing. I've chosen to call that glass
Matilda; you can call it something else if you prefer.
(By "maximally efficient" I mean the fewests tests need be performed
on average. The original problem doesn't count the effort of taking
and combining samples from large numbers of glasses, so neither do I.)
Therefore the fact that you can distinguish one glass that will not
be tested tells you nothing about how many glasses there were at the
start.
Of course if I were the police detective, I'd want to check that there
really is poison in the glass that I dust for fingerprints. (It would
be very embarassing at trial when the defense attorney asked, "But
what made you so sure there was poison in *any* of the glasses? You
never found poison at all! Don't you think this is excessively
careless?") If the glass turns out to be Matilda (which happens on
average 1 out of N times for N glasses), this entails an extra test.
The strategy I've given is still maximally efficient with regard to
the average number of tests that might need to be performed, but it
does not have the best worst-case behavior for every N. Ironically,
if you insist on testing every glass, the only time this will
adversely affect the worst case is when N is 2^k + 1, in which case
you'll have to test k + 2 times in the worst case instead of k + 1
times. For any other value of N, the worst case is k + 1 tests
whether you test every glass or not.
ObPuzzle: prove the above claims.
Of course there are still ways you can single out a glass as the "last
to test" without running into this behavior, for example you can
include Matilda in the original set of suspects but just keep track of
it and make sure it is never selected for testing unless it's the only
glass left.
(On the other hand, the best way to deflect defense attorneys is to
make sure that once you narrow down your possible suspects to two or
three glasses, you test each one individually. This sticks you with
worst-case behavior of k + 2 tests for 2^k + 1 glasses no matter what
you do.)
>PS: When I saw this puzzle in the `Mathematical Games' section of SCIENTIFIC
>AMERICAN, the answer given was 129, but the reason given was that
>testing a glass first leaves the worst-case number of tests at 8. As
>David Karr points out, this is inadequate justification. I think that the
>poster has reworded the puzzle in order to avoid this interpretation.
I hadn't seen the Scientific American article, but I guessed the
person who posed this had the same answer in mind. I will hazard a
conjecture (I could be wrong) that the puzzle was reworded not to
change the answer but in an attempt to make the puzzle clearer,
similar to the attempt on the puzzle about which part of the train
moves backward. Of course I don't know this.
David Moews
David Karr <ka...@cs.cornell.edu| wrote:
|David Moews <dmo...@xraysgi.ims.uconn.edu| wrote:
||Unless the number of glasses is 1 more or 1 less than a power of 2, it
||is not possible to construct an optimal search procedure which distinguishes
|But in what way was the single glass "distinguished" in either of these
|protocols? Only in that you decided to give a special connotation
|(largely irrelevant to choosing the glasses for the first few samples)
|In other words, in any maximally efficient procedure for finding the
|poisoned glass from any number of glasses, there is one glass that
|will never be sampled for testing.
I agree: unless we smuggle in a binary number from outside, the 129-glass
procedure does not distinguish a unique glass; my statement above is
unformalizable and meaningless. However, if you start with 127 glasses, the
commissioner's glass (`Matilda') is the only glass in which poison can be
found in 6 tests, instead of the usual 7. In terms of the binary search
tree, with sets of glasses at the internal nodes and single glasses at the
leaves, Matilda is
the unique glass fixed by all automorphisms of the search tree,
and such a glass can only exist if the number of glasses was 1 less than
a power of 2. No doubt, then, there had to be 127 glasses. But this
is probably not what the proposer intended.
|...Set Matilda aside.
|Now form the remaining glasses into a "set of suspects" and search
|them as follows:
|
| 1) Take samples from half the glasses in the set of suspects
| (exactly half of them if the number is even, round up
| if the number is odd) and test the combined sample.
| 2) If there was poison in the sample, the sampled glasses become
| the new set of suspects. If not, remove the sampled glasses from
| the set of suspects.
| 3) If there is more than one glass in the set of suspects, continue
| from step 1.
| 4) If the single remaining glass in the set of suspects has never
| been included in a sample that tested positive for poison, test
| it now. If it does not contain poison, the poison is in Matilda!...
|Of course if I were the police detective, I'd want to check that there
|really is poison in the glass that I dust for fingerprints....
|If the glass turns out to be Matilda (which happens on
|average 1 out of N times for N glasses), this entails an extra test.
Such a search procedure (call it `sure') for N glasses gives an
ordinary search procedure for N+1 glasses, since we can just
set one glass aside and conclude that the poison must be in it when our
sure search procedure comes up empty. Conversely, given an ordinary
search procedure for N glasses, call Matilda the glass we pick when
all our tests come up negative; then if we put an empty glass in Matilda's
place, the procedure is sure on the remaining N-1 glasses. These
transformations preserve worst-case efficiency (but not average
efficiency.)
|The strategy I've given is still maximally efficient with regard to
|the average number of tests that might need to be performed, but it
|does not have the best worst-case behavior for every N. Ironically,
|if you insist on testing every glass, the only time this will
|adversely affect the worst case is when N is 2^k + 1, in which case
|you'll have to test k + 2 times in the worst case instead of k + 1
|times. For any other value of N, the worst case is k + 1 tests
|whether you test every glass or not.
I'm not sure whether you're talking about your strategy above or
the best possible sure strategy. If N is between 2^k+1 and 2^(k+1), your
strategy always takes k+1 tests to infer that the poison is in Matilda,
and to make sure we must make k+2 tests. If we use the best possible sure
strategy, and N is in the same range, it takes only k+1 tests at worst
to be sure unless N=2^(k+1), when it takes k+2 at worst.
--
David Moews dmo...@xraysgi.ims.uconn.edu
David Karr
>However, if you start with 127 glasses, the
>commissioner's glass (`Matilda') is the only glass in which poison can be
>found in 6 tests, instead of the usual 7. In terms of the binary search
>tree, with sets of glasses at the internal nodes and single glasses at the
>leaves, Matilda is
>
> the unique glass fixed by all automorphisms of the search tree,
>
>and such a glass can only exist if the number of glasses was 1 less than
>a power of 2. No doubt, then, there had to be 127 glasses. But this
>is probably not what the proposer intended.
This is a good point, though this particular distinction need not be made
at the beginning; it can be postponed until very near the end of the
procedure, and in fact in most cases it need never be made to complete
the procedure.
Starting with (for example) 127 glasses, always test half (rounding
up) of the glasses that might still contain the poison. So you test
64 glasses to begin with. If the test is negative, the poison is in
one of the other 63 glasses, and you *might* find it in just 6 tests,
but you don't yet know (unless you've made a lot of decisions
unnecessarily early) which glass it would be in in that case. You
needn't distinguish that glass until (and if) you get very near to it
in the search tree; in fact, if you happen to get 5 negative tests in
a row (on 64, 32, 16, 8, and 4 glasses, in that order), then from the
remaining 3 glasses you'll select just two for testing, and the third
glass then is distinguished as the glass that *might* be found after
just 6 tests (i.e., after the test you're about to make). On average,
you can expect to have to distinguish this glass 3/127 of the time.
>I'm not sure whether you're talking about your strategy above or
>the best possible sure strategy. If N is between 2^k+1 and 2^(k+1), your
>strategy always takes k+1 tests to infer that the poison is in Matilda,
>and to make sure we must make k+2 tests.
Oops, that's because I muffed the strategy. Here's the new, improved
version (not quite as elegant as before, unfortunately):
Name one glass Matilda and set it aside. Now form the remaining
glasses into a "set of suspects" and search them as follows:
1) If your set of suspects consists of two glasses that have never
been tested, _sample_ _both_ _of_ _them_. Otherwise, take samples
from half the glasses in the set of suspects, rounding up.
2) Test the combined sample. If it contains poison, the sampled
glasses become the new set of suspects. If not, remove the
sampled glasses from the set of suspects.
3) If there is more than one glass in the set of suspects, or if the
set consists of just one glass that has never been sampled,
continue from step 1.
4) If you have one suspect glass remaining, the poison is in that
glass. Otherwise the poison is in Matilda.
The main change in this procedure is the emphasized words in step 1.
You need to be a little more eager to sample glasses toward the end of
the procedure in order to be "sure." You then trade off the
average-case performance when Matilda is not poisoned in return for
better performace when Matilda *is* poisoned, so you get better
worst-case performance but the same average performance.
What distinguishes Matilda from the other glasses is that it is
"last in line" for testing: it will never be sampled unless all
other glasses have already been sampled and tested. But I think
our discussion is painting this as a rather silly distinction,
which was my main point.