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].
Natasha, now a renowned full professor of archaeology though still in her early 30s, entered Ecco's apartment. Apparently, her identification of the most likely beam lengths of Menea had brought her fame and tenure. Success had also kindled an interest in conservation with a blend of tomb raiding.
"You've heard the story of the discovery of King Tut's tomb, Dr. Ecco, I'm sure," she said. "From 1916 to 1922, Howard Carter spent six years in unsuccessful pursuit of the tomb, enduring the unforgiving sun of the Valley of the Kings in Egypt. His funding resources nearly exhausted, he was ready to give up when his luck changed suddenly: One of his workers found a stair. The staircase led to a door. The door to an antechamber, the antechamber to...Carter pulled out hundreds of artifacts, many made of pure gold. Many of these treasures were preserved, but many more were destroyed by hands, pollution, and moisture.
"Recently, we have located an underground stone tomb in Zimbabwe. We believe it is air tight. But the surface air there is infinitely more moist than in the Valley of the Kings. We know that if we excavate it now, the moisture will destroy nearly everything inside, so we want to learn as much as possible by noninvasive sensing.
"Let me tell you what we know. As you can see in Figure 1, the tomb is an enormous hexagon. There are two corridors between vertices of the hexagon (but not along the periphery). The two corridors have diamond-studded walls and are basically straight. Two corridors may even link the same two vertices (that's why I said basically straight). We just know that there are two of them and that no corridors link neighboring vertices.
"We want to determine the vertices that each corridor connects. Our remote sensing devices are scattered by the diamonds, so each device consists of a radio-frequency laser and a detector. The laser is placed along a line segment and shoots towards the detector, which is along another line segment. The detector reports back whether the beam has passed zero, one, or two corridors."
"Diamonds?" 14-year-old Liane asked. "How long do you think you will keep that secret?"
"Not long," Natasha replied. "That's why we need to move fast. I have some drawings that might help. Figure 2 shows the hexagon with three rays. Those rays aren't enough because they can't distinguish (0,3) from (1,4) or (2,5). Similarly, the three rays of Figure 3 are not enough because they give no way to distinguish (0,2) from (2,4). Your job is to set up as few rays (laser-detector pairs) as possible, so that no matter which corridors are present, you will find out which pairs of vertices they connect."
Reader: How many do you need if you must set up all the rays before turning on any laser? You must be able to identify the locations of the corridors for sure. Liane could do it with six rays.
Liane handed Natasha the solution. Natasha studied it.
"Yes, I see. Well, if that's the best you can do, I thank you for your efforts once again." She was remarkably perfunctory I thought, considering that Liane had made her career.
"Nice job," Ecco said to Liane after Natasha left. "But you may be able to do better if you change the rules a little. Suppose you could set up one laser-detector pair, detect the ray, record the result, then set it up somewhere else, detect the ray, record the result, and so on. How many setups would you need? The laser beams still go from a segment of the hexagon to another segment.
"Here's why I think you might do better. Each ray can give three responses, so the total information of four rays is 34=81 alternatives. And there are fewer than 81 alternative layouts of the corridors. Here is why: There are six possible corridors that go between vertex x and x+2 mod 6. There are three possible corridors that go between vertex x and x+3 mod 6. So there are nine possibilities for each corridor. Since there are two corridors, there are 81 possible combinations of the two corridors, but those 81 distinguish between the first corridor and second corridor, which is unnecessary, so this double-counts most combinations. Therefore, four rays should be more than sufficient. Can you do that well?"
I never heard the answer.
Reader: Would you like to give it a try? Also, how would this generalize to higher n-gons (n>6) and more corridors?
Last Month's Solution
1. To answer Liane's unanswered question, in which one runner has a 0.9 probability and the other has a 0.4, we would give all the tickets to the 0.9 runner, because even if the Red team concentrates its attention on that runner, 0.45 is still a better probability than 0.4.
With the original assignment of the "dim-witted" captains, Blue's best strategy is to attack the 0.95, 0.9, and 0.8 runners, in which case the expected number of tickets is only about 442. The probabilities then become:
0.475: 333
0.45: 333 0.4: 42 0.7: 42 0.6: 42 0.5: 42 0.4: 42 0.3: 42 0.2: 41 0.1: 41
2. Assuming only one attack option can apply to any given player, Scarlet's solution began by giving 0 to any runner, p1, whose initial success probability was less than half that of some other runner, p2. The idea is that any solution that entails giving tickets to p2 can only be improved by giving those tickets to p1, since even after being reduced by 1/2, p1 has a better chance of winning. That's the discontinuity at work.
Now, we want the amounts we give to the remaining runners. Suppose, for sake of illustration, there are three. Let the half-probabilities of success be h1, h2, h3. Then the amounts to the runners (a1, a2, a3) should obey the relationship a1*h1 =a2*h2=a3*h3, and so on. Therefore, a1 is proportional to h2*h3, a2 is proportional to h1*h3, and a3 is proportional to h2*h3.
Using this observation, Liane made the following assignments:
0.95: 123
0.9: 130 0.8: 146 0.7: 167 0.6: 195 0.5: 239 0.4: 0 0.3: 0 0.2: 0 0.1: 0
Roger and Sally weren't happy. Nor were some of the younger campers who got no tickets. But the net effect was an expected delivery of over 527 no matter whom Blue attacks, much better than the first time, where the assignment led to an expected value of only 442.1.
Reader Notes
The goal of the "Duelist" puzzle (DDJ, February 2002) was to figure out whether the challenger or the challengee had better odds. The following readers showed that both duelists would do well to do some fast estate planning, because the odds in each case were quite close to 0.5: Dennis Okon, Rodney Meyer, Michael Elkins, Eric Uhrhane, Stephen Waits, Tomas G. Rokicki, Michael Dougherty, Rick Kaye, and Gene Wagenbreth. In this, they agreed with Liane and Dr. Ecco.
DDJ
