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].
We had heard of Dr. Robert Hatchett. A world authority on bioterrorism and toxic waste disposal, he exuded a sense of ironic good humor at the over-hyped technology he heard about every day.
"Nanomachines in science fiction play the role of magic," he said with a smile. "If one needs a super-flexible robot, a swarm of nanomachines fits the bill. If one needs extra-sensory perception, nanomachines can do that, too. The foreseeable reality, however, suggests that nanomachines have pico-intelligence.
"In fact, the nanomunching machines we are planning to deploy for hazardous waste disposal will follow a trivial program of the form:
eat at start position<br>
loop<br>
if there is something to eat to the left<br>
then go there and eat it<br>
if there is something to eat above<br>
then go there and eat it<br>
if there is something to eat to the right<br>
then go there and eat it<br>
if there is something to eat below<br>
then go there and eat it<br>
end loop<br>
"We abbreviate such a loop as left, up, right, down. Because the nanomuncher gets its nutrients from what it eats, it won't visit a node that it has already eaten or that another nanomuncher has partly eaten. The nanomuncher will not even go through that node. All it will do is keep following the loop on the graph it is assigned to until it can't continue.
"Note that the loop keeps its 'program counter' position after each move. So if you start at A and go left to B, you will first try to go up from B. If not possible then right, if not possible then down, if not possible then left. If none are possible, then B is called a black hole and the nanomuncher will disintegrate. The goal is to eat at every node in a given graph before entering a black hole. If you succeed, then you have 'munched' the graph.
"You are allowed to choose the first node and to choose the order in the loop. So a loop might be right, up, left, down, for example."
"I see that both can make a difference," 14-year-old Liane volunteered. "Consider 
. If you start at B, then you will surely lose, no matter what your loop is. If you start at A or C, you will win, regardless of the order in the loop.
"Here is an example in which the order makes a difference. Suppose you have:
If you start at C, then you will win if the loop is down, right, up, left (or anything else that starts with down), but not if it is right, down,...(or anything else that starts with right)."
"Very fast on the uptake, young lady," said Hatchett. "Perhaps you can answer this one: What is the connected graph with the fewest nodes that cannot be munched, no matter what the order or what the starting point?"
Reader: Before reading on, give it a shot.
Liane thought about this for a few seconds. "Any two or three node graph must constitute a single path, which can obviously be munched," she said. "So the smallest impossible connected graph must have four nodes:"
"Well done again," said Hatchett. "Now, here are a bunch of questions. Are there any shapes having the property that even an arbitrarily large graph of that shape has a solution, regardless of the start node and regardless of the order of the loop?"
Reader: Would you like to try this one?
"Are there graphs that are munchable with two nanomunchers (with different starting points and possibly different loop orderings) but not with one?" Hatchett asked. "You can assume that if a nanomuncher arrives at a node already occupied by another, it will retreat. If two nanomunchers reach an uneaten node at the same time, the one coming from a lower node will retreat; if they both come from nodes at the same height, then the one to the left will retreat. You may not assume any other synchronization nor may you assume that different nanomunchers work at the same speed."
Reader: What do you say about this (pretty easy) one?
"How about vice versa; for instance, some graph that two nanomunchers can't munch but one can?" he continued. "For this to be true, there must be a successful start node and loop configuration for one nanomuncher, but none for two nanomunchers. (It's not enough to find one unsuccessful configuration for two nanomunchers. All configurations must be unsuccessful.)"
Reader: This one is open. Do you have thoughts?
"You have posed many interesting questions," Ecco said with a smile. "Is there one question that you are most concerned about?"
"Well, two actually," Hatchett responded. "You see here in Figure 1 a graph that is a portion of a grid. Can you munch it?
"Second, we will often be faced with grids of various vertical and horizontal dimensions. Which ones are munchable by a single nanomuncher and how?"
"I take it that a grid is a two-dimensional nxm checkerboard configuration, right?" Liane asked.
Hatchett nodded.
Liane took longer on this one. "I can arrange to munch any nx1, nx2, or nx3 grid. I can also handle any nm grid when both n and m are odd. I'm not sure about the others."
Reader: Can you match Liane's achievement? Can you determine whether all nxm grids are munchable? Would your answer change if you had two nanomunchers?
Last Month's Solution
The goal was to find the number k (5 in Liane's solution) such that all numbers between 1 to n (57 in Liane's solution) could be expressed using only arithmetic operators and using under 5 (a coincidence) members of k. In this case, the average cost was 4.98. The method Liane used was quite brute force. She explored each generator between 3 and 20. For each generator k, she seeded a dynamic programming algorithm with the generator for 1(k/k) and 2(k+k/k). Then for any value i, her program would explore every addition and multiplication possibility involving numbers less than i, and every subtraction and division possibility greater than i.
1: 5/5
2: (5+5)/5
3: (5+(5+5))/5
4: 5-(5/5)
5: 5
6: (5/5)+5
7: ((5+5)/5)+5
8: (5+5)-((5+5)/5)
9: (5+5)-(5/5)
10: 5+5
11: (5/5)+(5+5)
12: ((5+5)/5)+(5+5)
13: (5+(5+5))-((5+5)/5)
14: (5+(5+5))-(5/5)
15: 5+(5+5)
16: (5/5)+(5+(5+5))
17: ((5+5)/5)+(5+(5+5))
18: (5*5)-(((5+5)/5)+5)
19: (5*5)-((5/5)+5)
20: (5*5)-5
21: ((5/5)+(5*5))-5
22: (((5+5)/5)+(5*5))-5
23: (5*5)-((5+5)/5)
24: (5*5)-(5/5)
25: 5*5
26: (5/5)+(5*5)
27: ((5+5)/5)+(5*5)
28: (5+(5*5))-((5+5)/5)
29: (5+(5*5))-(5/5)
30: 5+(5*5)
31: (5/5)+(5+(5*5))
32: ((5+5)/5)+(5+(5*5))
33: (5+(5+(5*5)))-((5+5)/5)
34: (5+(5+(5*5)))-(5/5)
35: 5+(5+(5*5))
36: (5/5)+(5+(5+(5*5)))
37: ((5+5)/5)+(5+(5+(5*5)))
38: (5*(5+5))-(((5+5)/5)+(5+5))
39: (5*(5+5))-((5/5)+(5+5))
40: 5+(5+(5+(5*5)))
41: (5/5)+(5+(5+(5+(5*5))))
42: ((5/5)+5)*(((5+5)/5)+5)
43: (5*(5+5))-(((5+5)/5)+5)
44: (5*(5+5))-((5/5)+5)
45: (5*(5+5))-5
46: ((5/5)+(5*(5+5)))-5
47: (((5+5)/5)+(5*(5+5)))-5
48: (5*(5+5))-((5+5)/5)
49: (5*(5+5))-(5/5)
50: 5*(5+5)
51: (5/5)+(5*(5+5))
52: ((5+5)/5)+(5*(5+5))
53: (5+(5*(5+5)))-((5+5)/5)
54: (5+(5*(5+5)))-(5/5)
55: 5+(5*(5+5))
56: (5/5)+(5+(5*(5+5)))
57: ((5+5)/5)+(5+(5*(5+5)))
If you may use an average of 6 numbers, then it is possible to handle all numbers from 1 to 121. The average here is exactly 6. (The solution is available electronically; see "Resource Center," page 5.) It is interesting that 4 works better than 5 for this. The best solution for 7, where 308 was possible using 6 as a generator, is also available electronically.
Reader Notes
Before discussing the solutions to the Color War puzzle (DDJ, April 2002), I should mention that the inspiration for the model underlying this puzzle came from Aris Tsirigos's masters thesis at Cornell.
Clever readers found some excellent solutions to the problem. The best came from Robert Byard, Nicholas Singer, Shawn B. Nematbakhsh, Pike Enz, Andrew Palfreyman, Leif Jensen, Warren Dougherty, Douglas Wilson, Jason Strickland, John Trono, and Dennis Okon.
Byard was the first to offer the optimal solution for Blue, distributing 162, 171, 192, 219, 256, 0, 0, 0, 0, and 0 to the players in descending order of their initial probability to win. Once again, the best runners don't get the most tickets. The expected result after three tackles is 537.60. He also pointed out that double targeting doesn't help Red.
The techniques readers used to tackle the problem varied: Byard used spreadsheets; Jensen, linear programming; Wilson, a genetic algorithm; Strickland, exhaustive search; and Trono, simulated annealing. Who would have thought Color War could lead to so much thought?
DDJ
