Dennis, a professor of computer science at New York University, is the author of The Puzzling Adventures of Dr. Ecco (Dover, 1998); Codes, Puzzles, and Conspiracy (W.H. Freeman & Co., 1992); Database Tuning: A Principled Approach (Prentice Hall, 1992); (coauthored with Jason Wang and Bruce Shapiro) Pattern Discovery in Biomolecular Data: Tools, Techniques, and Applications Oxford University Press, 1999); and (coauthored with Cathy Lazere) Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists (Springer-Verlag, 1998). He can be contacted at [email protected].
Liane wrote from summer camp, fuming: "The camp administration decided to institute a color war, probably to satisfy nostalgic parents," she wrote. "It was the Red team against the Blue team. I was on Blue. The main event involved a game with two large concentric circles. Inside the smaller circle were the judges. In the annulus of the larger circle were the members of the Red team. We Blues started outside the larger circle. We had a strategy meeting.
"Our dim-witted captains had 1000 tickets to distribute. Our team's objective was to get as many tickets as possible to the inner circle. The captains gave 1/3 of the tickets to each of our strongest two runners, Sally and Roger. They split the last 1/3 among the last eight of us. The rules are simple. We charged the outer circle. If we made it to the inner circle without being tackled, we gave our tickets to the judges. If not, we were out of the game and our tickets never made it to a judge.
"The Red team apparently formed a plan to tackle Sally and Roger. They succeeded, thus making us lose 2/3 of the tickets. I made the captains promise that next time they would consult me before they assigned tickets. When they saw that even Sally and Roger thought this was a good idea, they agreed.
"Here is the model I have thought up. The Red team reserves special tackles for targeted people, but their general defense is also quite strong. Each runner has a certain probability of getting through the general defense (succeeding). However, if Red concentrates their special tackles on that runner, the probability of success is multiplied by 1/2. The Red team can concentrate their tackles on only three of our runners. However, just to be pessimistic, let's assume they know the initial probabilities as well as we do, and they even know how many tickets each of our runners gets, through spies. We want to maximize the expected number of tickets that get through.
"Let's take a simple example: There are just two runners. One has initial probability 0.9, the other 0.5. If the Red team can reduce the probability of only one of my runners by half, who should get more tickets and what is the best way to distribute the tickets?"
Reader: Try to figure this out before reading on. Your intuition may deceive you.
"If Blue gives x to 0.9 and 1000-x to 0.5, Blue gets 0.9x+(1000-x)0.5 if the only defense were the general defense. But the adversary will choose to halve 0.9 if 0.45x>(1000-x)0.25. The adversary will choose either runner indifferently if 0.7x=250 or x=357. So, one possibility is giving 357 to the 0.9 runner and 643 to the 0.5 runner. Now, no matter which is halved, we get about the same expected number (a little more than 482). So, we are giving less to the better runner than to the poorer one. Could this be right?
"Let's see. Suppose instead, we give the 0.9 runner 357+y and the 0.5 runner 643-y tickets where y>0. Then the rational adversary will choose the 0.9 runner as a victim. The net effect is that we gain an extra expected 0.45y (because the 0.9 runner has more) but lose an expected 0.5y (because the 0.5 runner has less). So, we lose on balance. Similarly, if we give the 0.9 runner 357-y and the 0.5 runner 643+y, then the Red team will concentrate on the 0.5 runner. We will lose 0.9y because we've given less to the 0.9 runner and we will gain 0.25y.
"So, we give the 0.9 runner slightly more than half what we give to the 0.5 runner. If the worse runner had a probability of 0.8, then the division would be roughly 530 for the 0.8 runner and 470 for the 0.9 runner. The bigger the difference in abilities the more the worse runner is favored. Mathematics leads one to strange destinations.
"But there is a discontinuity. What would be the best distribution if the initial probabilities of the two runners were 0.9 and 0.4?"
Reader: Again, please have a try. Liane didn't bother to answer.
"So, with those preliminaries out of the way, here are the initial runner probabilities: 0.95, 0.9, 0.8, 0.7, 0.6, 0.5, 0.4, 0.3, 0.2, and 0.1. Sally and Roger have the first two probabilities (they really are great athletes). The first distribution was 333 to each of Roger and Sally and then 42 or 41 to the rest. That is:
0.95: 333
0.9: 333
0.8: 42
0.7: 42
0.6: 42
0.5: 42
0.4: 42
0.3: 42
0.2: 41
0.1: 41
"What would be the best strategy for Blue in that case and what would be the expected number of tickets that would make it to the inner circle?
Reader: What do you think?
"Could you help me figure out how much to give each runner, now that the captain will listen to me?"
Ecco looked at me. "Well, Professor, do you think we can help my forlorn niece?"
"I'll give it a try," I said. "The discontinuity does make things hard."
Reader: Professor Scarlet was able to get an expected value of over 500. How well can you do?
"Nice work, Scarlet," Ecco said. "Here's a variant that Liane might ask us about in her next letter: How do the strategies change if the Red team is understood to have three attack options and these can be spread among three Blue team runners as above or two or three can apply to one runner. If k attack options apply to one Blue team runner, then that runner's probability of success decreases by a multiplicative factor of 1/(2k). So, the Red team could apply two to a 0.9 runner and one to a 0.8 runner, reducing the former to 0.225 and the other to 0.4."
I wasn't able to answer that one.
Reader: Would you like to give it a try?
Last Month's Solution
First, put together the snippets in this order: GAGACGATT, TGGATA, AC, TTGGATTAAA, AACGGA — add TT to get AACGGATT, CA, TG, and ACCCGA.
Professor Scarlet's solution — have six element nucleotide snippets for every possible pair of amino acids. There are 400 such snippets. Glue these together pair by pair to get a sequence 16 long. I don't know how to do better, but a good study of the code might show a way. And it might even point to a general manufacturing technique. The main rub in general is that for an amino acid sequence of length L, there are 20L different possibilities.
Reader Notes
Several readers improved on Ecco's solution to the Desert Sprinkler problem (DDJ, January 2002) including Rodney Meyer, Alexander Fedorov, Lloyd Rice, Ray Shanley, Kenneth Price, Geoffrey Probert, Christopher Evans, Andrew Palfreyman, Zebadiah Kimmel, Stephen Waits, Glenn Simpson, Mark Feldman, Tomas G. Rokicki, Alan Dragoo, David Hewitt, David Geldreich, David Stevenson, Lothar Breuss, and Greg Janee.
Some readers thought they were giving solutions that watered no edges but ended up having an x- or y-coordinate less than the radius.
Two of the best solutions came from Rodney Meyer. First, he obtained a solution covering 381 square meters for the case when all sprinkler coordinates were integral and water was not allowed to leave the area, see Table 1. Tom Rokicki beat this by assuming that touching a square meter meant touching the very middle (i.e. 0.5 meter offset from each side), thus obtaining 444; see Table 2.
Rodney Meyer's wet-edge solution watered a remarkable 507 square meters using the clever strategy of placing sprinklers outside the area (a possibility the puzzle never excluded); see Table 3.
DDJ
