Blood

"Human or newt?" Liane asked with a grin.

Jacobs smiled, "A quick wit. We'll need that for the problem I'm going to pose to you, Dr. Ecco.

"As you may know, Hepatitis C is a horribly debilitating illness that can be passed by blood transfusion. The test for the presence of Hepatitis C is called the Elisa test. It isn't accurate enough, giving us both false positives (good blood is thought to be bad) and false negatives (bad blood is thought to be good). There is an expensive but very precise technique based on the Polymerase Chain Reaction (PCR). This technique is so precise that if we take a drop of blood from 50,000 different pints and as few as one pint has Hepatitis C, we will detect it.

"Our center receives 100,000 pints per day. Very close to 1 percent of those pints has the disease. We would like to figure out which pints have Hepatitis C by using no more than 20,000 tests. Each test takes a day, however, and we want to decide the fate of each pint in two days or less. Can you help us?"

"How accurate do we have to be?" asked Liane. "I mean if you don't care whether you throw out some good blood with the bad, then we need no tests at all -- just throw out the whole lot."

"You have a future in health administration," Jacobs answered with a grin. "To start with, please assume that you can't throw out more than two good pints with every bad pint."

"Let's first try the case where each pint can be tested for only one day before its fate must be decided," Ecco suggested.

Reader: Before reading on, see if you can find a method that results in under 35,000 tests and doesn't entail throwing out more than 2000 pints of good blood, assuming there are 1000 pints of bad blood. The fate of each pint must be decided in one day.

"Good suggestion, uncle," said Liane to Ecco. "Well, since there are 1000 bad pints, and we allow 2000 false positives, we divide the pints into 33,333 groups of three and one group of one. We test all the pints in each group together. 1000 groups of three will have a bad pint. For each such group, we throw out all the pints."

Reader: In the situation in which two days are allowed for testing and there are 1000 bad pints out of 100,000 and 2000 good pints may be thrown out, Liane was able to do the job with under 12,000 tests. How well can you do?

"What if no errors are permitted?"

Reader: Liane was able to handle the no-error case in 20,000 tests.

"So, we either throw away perfectly good blood, or we need that many tests," said Dr. Jacobs sadly. "Suppose our pretest screening improved a lot and we could ensure that no more than one pint had Hepatitis C. What is the smallest number of tests you could do with one day of testing, assuming you don't want to waste any good blood?"

Reader: Liane was able to do this with just 17 tests, but each test requires samples from many pints.

"Maybe one bad pint is unreasonable. What if there could be a small number, say 10. You still don't want to waste any good blood."

Reader: Liane had no particularly good method for this that was guaranteed to give an answer in one day. Even for two days, her best answer required 1900 tests in the worst case. Can you do better?

Jacobs had taken notes in a medically illegible scrawl. He even wrote down Liane's last solution. "You have a brilliant niece Ecco. My compliments," he said. He folded his piece of paper into his jacket pocket shook hands with us and left looking very satisfied. Ecco was not.

"Liane, think," he demanded of his niece. "The gap between 17 and 1900 is huge, all for a handful of pints that could be bad. Surely you can close the gap. Suppose I give you as many days as you want."

For the case of two bad pints, Liane had a solution requiring under 40 tests, but nearly 20 days.

I never heard either of them speak more of the generalization of this problem.

Reader: Do you have any ideas regarding the problem "You have a handful (10 or fewer) of bad pints out of 100,000. You have as many days as you please. How do you do the grouping and testing?"

Last Month's Solution

The solution to the first question concerning the game "Simple" is that player X can force a win in the original game in about eight moves. Here is how. Without loss of generality, X can force the following situation (or something symmetric):

XO

X

Now, O has two choices (because any other would lead to three Xs in a line and make it impossible for O to stop the result):

1.

O

XO

X

2.

XO

X

O

Let's follow Case 1 first. Player X forces player O by threatening a win:

O

XO

X

X

Player O stops the certain win:

O

XO

XX

O

Now player X plays under the first O:

O

XO

XX

X

O

Now, O must stop the two Xs and has two choices:

1.1

O

XO

XXO

X

O

1.2

O

XO

OXX

X

O

From 1.1, we get to:

O

XO

XXXO

X

O

followed/forced by:

O

XO

OXXXO

X

O

and this is followed by:

O

XO

OXXXO

XX

O

which leads to two forced wins (a forced win is three Xs in a row without Os) So, this finishes Case 1.1.

From 1.2, player X can play a forcing move:

O

XO

OXXX

X

O

So, player O responds with:

O

XO

OXXXO

X

Now, player X does:

O

XO

OXXXO

X X

O

and can force a win.

In Case 2, Player X plays a forcing move:

X

XO

X

O

So, player O must respond:

O

X

XO

X

O

Now, player X does:

O

X

XO

XX

O

So, player O must respond with either:

2.1

O

X

XO

XXO

O

or

2.2

O

X

XO

OXX

O

In Case 2.1, player X plays a forcing move and player O responds:

O

X

XO

OXXXO

O

Then player X plays:

O

XX

XO

OXXXO

O

and guarantees a win. This takes care of Case 2.1.

In Case 2.2, player X plays a forcing move and player O responds:

O

X

XO

OXXXO

O

Now, player X plays the following clever move (unconnected to any other node):

O

X X

XO

OXXXO

O

This ensures a win by X. This takes care of Case 2.2.

Reader Notes on the "Stars and Starlets Puzzle"

Several readers improved on Dr. Ecco's solution to the "Stars and Starlets Puzzle" (DDJ, January 2000). The best solutions, starting with the suggestion of Chris Young, had the following flavor:

Scenes

Day 1
1 Hacket
6 Thompson McDougal Anderson Scolaro Spring
14 Anderson Scolaro
18 Scolaro McDougal Hacket Thompson

Day 2
3 McDougal Scolaro Mercer Brown
9 Casta McDougal Mercer Scolaro Thompson
10 Casta McDougal Scolaro Patt
16 Scolaro McDougal Casta Mercer
17 Scolaro Patt Brown

Day 3
2 Patt Hacket Brown Murphy
5 Mercer Anderson Patt McDougal Spring
11 Patt
12 Hacket Thompson McDougal Murphy Brown
15 Thompson Murphy McDougal Patt

Day 4
4 Casta Mercer
7 Casta Patt
8 Mercer Murphy
13 Hacket Murphy Casta Patt
19 Casta

This gives a total of $3,341,440 for actors' fees (a substantial savings over the original cost of $4,975,360). Other readers with similarly excellent solutions (that is, that gave the same actor fee total) included: Thomas Cloutier, Tomas G. Rokicki, Jason Strickland, Onno Waalewijn, Christian Grigis, Paolo Friedli, Tom Dinger, Charles Taylor, Alan Dragoo, Geoffrey Probert, Patrick R. Schonfeld, Frank Adrian, Mark Whitaker, Jacques Belzile, Fernando H. Kato, David Berson, Mathew Davies, John A. Trono, Philip Staite, Scott Williams, Carl Smotricz, Francis C. Swasey, Larry Holding, Herb Halvorson, Kurt Jones, Malcolm Kay, Brenton Hoffski, and Terje Mathisen.

Several clever readers improved on Dr. Ecco's solution but left some unnecessary actor fees relative to the Young et al. solutions: Jon Beal, Greg Smith, Jeff Hafner, Nick Knight, Craig Stevenson, Philip Staite, Earl Paddon, Charles E. Killian II, Pike Enz, Jason Strickland, Paul Gerken, Sy Wong, and Geoffrey Probert.

DDJ