King Elessar summons the wizard Gandalf to court, seeking his counsel. A foul plague has been incapacitating the soldiers. King Elessar asks Gandalf if there exists a test for the disease that is 100% sensitive and 100% specific (ie perfect). Gandalf says that a perfect blood test does exist, but it is very expensive, requiring the venom of a special lizard found only in the Morgul Vale. Each blood test would cost one gold piece, but the Royal Purse only has 500 gold pieces to spare, and there are 1000 soldiers that need to be tested. Gandalf sleeps on it and returns the next day with a plan for testing all of them that won’t break the bank:
- Take a blood sample from each of the 1000 soldiers;
- Split each of these samples into two parts;
- Take one part of each sample and mix batches of ten of the samples together to create 100 mixed samples.
- Test each of those mixed samples;
- A few things could happen:
- If the test gives a negative result, we know all of the original ten samples are clear, and we can move on;
- If the test gives a positive result, then we know at least one of the original ten samples is positive. In that case we test the second part of the sample for each of the ten soldiers. We can then identify which soldiers are positive.
Gandalf finishes by saying “I expect sixty of the mixed batches to be negative. For the other forty batches, I expect the results to be positive, and hence we will have to test all four hundred of the original samples. This gives a total expected cost of 500 gold pieces.”
- What disease prevalence is Gandalf implicitly assuming here?
- Can Gandalf revise his scheme to reduce the expected cost even more?