David W. answered • 07/23/15
Experienced Prof
There is a well-known math solution to such a problem. There is also strategic logic to be learned. In fact, once the logic is learned, then such math problems become easier. That’s why practice, practice, practice (and did I mention practice?) is included in math courses.
Given a “dose” of wine from an unlimited number of bottles of wine to an unlimited number of prisoners, and a response time constrains the experiment to “a single dose,” we could start, say, a thousand prisoners (since the poison must be in exactly one of 1000 bottles), wait 24 hours and observe which prisoner died. We’d need an identification system to tract wine bottle identification (but we already have prisoner ID numbers).
Can the problem be solved using fewer prisoners (note: when we finally have to say “no,” we have the minimum)?
We could divide the 1000 bottles of wine into two group, each with 500 bottles and have each of the prisoners drink from two bottles – the corresponding first bottles, the corresponding second bottles, the corresponding third bottles, etc, -- then observe which two prisoners die (note: using this method the bottle containing the poison gets drunk twice, once as the first sip and once as the second sip).
Now, can we improve (lessen this number more)?
Yes, we could divide each of the two groups of bottles into halves, producing four total groups and have each prisoner drink four sips. [note: work this out!] Now four prisoners die, and the poison bottle is in one of the groups identified by a four-bit binary number (first half, second sub-half, identified by ‘01’). Notice, that in binary, 00, 01, 10, 11 are the four groups of bottles.
Full disclosure: I’ve taught college computer science, so I recognized the math in this problem pretty easily.
Now, how large a binary number (how many ‘bits’ needed or how many levels of of a tree data structure or how many decisions of a logic path or …) is needed to isolate the one bottle out of 1000? (so that we won't just be talking about the solution 'group')
The powers of 2 (right-to-left in a binary number) are 1, 2, 4, 8, 16, 32, 64, 128, 512, 1024, .., hey! Stop, because that’s enough to isolate 1 in a 1000. So, 10 prisoners, each taking 10 sips of wine are the minimum number to isolate which bottle was poison.
The bottle with the poison will be identified by a 10-bit number, such as 0001011010 because the corresponding prisoners who died (of the 10) will have matching 1 'bits' in the bottle ID number (and we have 1024 bottle ID numbers available).
Now that you have been introduced to binary and have heard my stories about computers, I hope that you will learn more about Computer Science.
David W.
First, I must observe that the world today has worse persecution than that described. Governments and terrorists and religions and companies (using corporate espionage) and individuals and … regularly inflict physical death, physical torture, physical experiments, … much like Hitler or Caesar did. This is documented in many current news articles.
For this problem, the “bigger battle” (and our focus) must be on the math and strategy (or else our students will not be equipped to fight bigger battles someday). On September 11, 2001 (my birthday), I had planned to take cake and ice cream for my evening Computer Data Structures class. Early in the morning, I began getting e-mails asking, “Will we have class tonight?”, so I turned on the TV. Soon, I turned off the TV and sent an all-class e-mail saying that, “Yes, we will have class. If you have government responsibilities (Air Guard, Coast Guard OSC, etc.) and are called in, you are excused, but if not, you have the obligation to learn this material so that, someday, you can contribute to the solution, not the problem.” We had class.
Please see my Answer.
07/23/15