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].
Usually, I can distinguish biologists from technologists by how they react to inconsistent experiments. The technologists view the inconsistency as evidence of a bug in the program or even the programmer. By contrast, biologists — who live with the fact that "identical" experimental conditions often give different results — consider inconsistency to be a window into an unexplored world.
Our visitor, tanned and athletic looking, quickly revealed his approach to science.
"I believe carbon is the key to the amino acid pathway I am studying," Andrei Laurence explained, "but I haven't been able to reproduce the experiment that shows this. I grew some plants and then added carbon (in the form of sugar) to half of them, and measurements showed that the half with carbon produced much more of my amino acid. The problem is that I haven't been able to reproduce this result. Even when I give the plants all possible illumination and nitrogen levels, they don't show the difference. So, now I must determine which other factors have an effect. The trouble is that there are a lot of them — things like time of day, the age of agar I used, and so on — and I think most are irrelevant. I won't trouble you with their values, but just the fact that there are eight such factors, each with four possible values. But doing 48 or roughly 64,000 experiments for each carbon value will take me years. A small random sample won't do either. There might be some synergy between the factors, at least pairs of them.
"So I would like to perform a set of experiments having the property that for each value of carbon, any two factors Fi and Fj, any value v1 of factor Fi, and value v2 of factor Fj, some experiment tests v1 of Fi and v2 of Fj. I call this the 'all-pairs property.'"
Liane interjected: "Suppose there were only two factors. Then you would need at least 16 experiments for each value of carbon, correct?"
Dr. Laurence nodded. Liane then started writing something on paper.
"And if you had four factors, you could do with 21 experiments, correct?" she asked.
Reader: Before reading on, can you identify a set of 21 experiments for each value of carbon having the all-pairs property? For each factor, Liane used the values a, b, c, and d to represent the four values as shown in Table 1.
"Right again," Laurence said. "The question is: What will it take for eight factors?"'
Liane came back with an answer after a few hours.
Reader: Liane was able to achieve the all pairs property with only 30 experiments for each value of carbon, not even twice as many as would be required for just two factors. Can you do that well?
Laurence was visibly relieved. "Liane, you have reduced a three-year project to a one-month project," he said. "Come visit me in my lab any time."
"Nicely done, Liane," said Ecco after Laurence left. "And what if Dr. Laurence had needed an 'all triplets property': That is, for each three factors Fi, Fj, and Fk, and any three values v1 from Fi, v2 from Fj, and v3 from Fk, some experiment sets Fi to v1, Fj to v2, and Fk to v3. 64(=4×4×4) is clearly a lower bound, but can you get an answer with fewer than 100 experiments?"
I never heard the answer to that question.
Last Month's Solution
1. An enormous single square is munchable regardless of the loop order and of the starting point.
2. The T shape that Liane identified is munchable with two nanomunchers but not with one.
3. As Figure 1 shows, start at the node labeled 1 and loop right, left, down, up.
4. Suppose that a grid of the form n×1, n×2, or n×3 for any n is mostly horizontal. That is, n horizontal by 2 or 3 vertical. One way to munch the grid is to start at the lower left and loop as follows: If n is even, then left, up, right, down; if n is odd, then up, right, down, left.
If the grid is n×m and both n and m are greater than 3 and odd, then start at the bottom left corner and use the sequence: up, right, down, left. You can make it all the way around. You will handle the bottom two rows, then the right two, then the top two, then the left two, and will start on the third from the bottom row moving right.
Reader Notes
Tom Rokicki, Michael Birken, Andrew Palfreyman, and Bruce Moskowitz sent in clever solutions to the Stone Tomb of Zimbabwe puzzle (DDJ, May 2002). Under the assumption that the corridors within the tomb could cross (the intended assumption) and all beams have to be placed before any tests are run, Rokicki was able to show that for any n-sided polygon where n>=6, there must be ceil(n*(n-4)/2) lasers (where ceil(x) is the ceiling function that returns x if x is an integer and the next integer greater than x otherwise). This number is close to the requirement that there must be a laser between every wall and every other wall.
Rokicki argued as follows for the case when n is large:
Consider two corners on the polygon that are not near each other (farther than two units away). Call their locations (a) and (b) where we number the corners sequentially around the polygon. Whatever laser combinations we set up must be able to distinguish the following two cases: (a->b+1), (a+1->b) (corridors are parallel) versus (a->b), (a+1->b+1) (corridors cross). The only laser firing that can make this distinction is one that fires from wall (a..a+1) to wall (b..b+1); all other lasers will always cross the same number of corridors.
Bruce Moskowitz showed how to use only five beams to find two corridors in a hexagon in the dynamic version of the puzzle, where new beam positions can be determined after learning the results from the previous beams. As an example solution, he started with (0..1,1..2), (0..1,2..3), (0..1,3..4). The rest follows from case analysis and always arrives at a unique answer after five beams. Here, (x..x+1) means putting an endpoint between vertices x and x+1. He also showed that even a seven-sided polygon could be covered by six beams in this dynamic setting, even though the static version requires 11 beams as indicated by Rokicki's expression.
A small historical note: Centuries before Europeans arrived in Zimbabwe, the people there built cities out of stone. Tombs like these may well exist.
DDJ
