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].
Ana Ban said, "They will die if you don't help them, Dr. Ecco." The great naturalist stood there, jungle fatigues and all. Twelve-year old Liane was in awe. The woman exuded grace and a sense of purpose.
"I've been working with these chimps for the last eight years," she said. "They are unique specimens. But I'm in Africa in the first decade of the millennium and some greedy officer wants to replace the current corrupt dictator with his own cronies. Last time this happened, all the animals in the zoo were killed in the cross-fire. This time, I'm taking no chances. I've got a huge container on a cargo ship that the shipping company is willing to drill with air holes so the ship can take the chimps to relative safety in Madagascar. The container will house 27 cages in a 3×3×3 cube. We'll put one chimp in each cage. Some of the chimps love each other and quite a few hate one another. I'm not sure how to place them to avoid battles and to keep the loved ones together. Can you help me?"
"Yes," Liane said eagerly. "If it's possible, we'll do it. Tell us which chimps love which ones and which ones might fight which ones."
"Very well," Dr. Ban replied. "Please understand that we know our chimps very well and give them human names that match their temperaments. Some of the names are familiar from history and others are the names of our colleagues some of whose personality traits we see in the chimps. Their names are: Annie, Aristotle, Augustine, Caesar, Carlie, Cecily, Chimpie, Coco, Cordelia, Darwin, Didi, Emily, Goodall, Humboldt, Jonathan, Julia, Katie, Lea, Marie, Miles, Millie, Napoleon, Natasha, Sarah, Theo, Victoria, and Zoe.
"Here is the description of the loves and hates of our chimps. All such emotions are reciprocal, so if chimp A loves chimp B, then chimp B will love A. Similarly, for hates. (For this reason I'll specify only half of the relationship.) If a chimp loves another one, it should be next to that one on the same level of the container and they should share a wall. They will want to touch each other if the water turns rough. If a chimp hates and might fight with another one, it should not be next to that other one vertically or horizontally. Not even diagonally at a bottom or top corner. Their arms are long and their hands strong."
"So, the chimp in the center row of the middle level had better have no enemies," Liane pointed out.
"That's right," said Ban, looking at the young girl. "You may well help me, as you claim."
"Aristotle loves Lea.
Chimpie loves Marie and Cecily.
Darwin loves Annie and Millie.
Humboldt loves Zoe.
Goodall loves Jonathan.
Napoleon loves Emily.
Caesar loves Julia and Cordelia.
Theo loves Zoe.
Augustine loves Didi and Katie.
Coco loves Theo.
Didi loves Augustine.
Carlie loves Jonathan.
"Aristotle might fight with Chimpie, Augustine, Annie, and Marie.
Chimpie might fight with Caesar, Cordelia, Katie, and Carlie.
Darwin might fight with Humboldt, Napoleon, Sarah, Victoria, Miles, and Emily.
Humboldt might fight with Natasha, Didi, Katie, Annie, and Marie.
Goodall might fight with Zoe, Sarah, Didi, Carlie, and Lea.
Napoleon might fight with Caesar, Millie, Natasha, Augustine, Julia, Didi, Lea, and Marie.
Caesar might fight with Natasha, Sarah, Lea, Marie, and Emily.
Zoe might fight with Millie, Natasha, Augustine, Didi, and Victoria.
Millie might fight with Cordelia, Didi, Carlie, Miles, and Lea.
Natasha might fight with Cordelia, Coco, Julia, and Emily.
Theo might fight with Augustine, Didi, Katie, Cecily, Lea, and Marie.
Augustine might fight with Cordelia, Coco, Sarah, and Emily.
Cordelia might fight with Coco, Julia, Katie, Miles, and Lea.
Coco might fight with Sarah, Didi, Katie, Carlie, Annie, and Lea.
Julia might fight with Sarah, Victoria, Carlie, Miles, Annie, and Emily.
Sarah might fight with Didi and Victoria.
Didi might fight with Victoria, Katie, and Emily.
Victoria might fight with Katie, Carlie, and Annie.
Katie might fight with Carlie, Miles, Cecily, Annie, and Emily.
Carlie might fight with Marie and Emily.
Miles might fight with Annie.
Cecily might fight with Annie and Emily.
Annie might fight with Marie and Emily.
Lea might fight with Marie and Emily.
Marie might fight with Emily."
Reader: Can you find a placement of the chimps in a 3×3×3 cage container in which each chimp will share a wall with all the chimps it loves (a wall is better than a floor or ceiling) but will not share even a corner with a chimp it hates? Please provide your answers as three 3×3 matrices, each one indicating a floor.
Liane worked out a solution in a remarkably short 30 minutes. Dr. Ban took some time and then verified it against her list.
"There is one more thing," she said with a sigh. "Chimps that hate one another shouldn't be in the same column of the container. The feces will drive the bottom chimps crazy even if they can't reach one another."
Liane managed to solve the problem even with this constraint.
Reader: Can you find a placement of the chimps in a 3×3×3 cage container in which each chimp will share a wall with all the chimps it loves (a wall is better than a floor or ceiling) but will share neither wall nor corner nor column with a chimp it hates?
Dr. Ban thanked us all, but most especially Liane, and then left.
"Well done, Liane," Ecco said to his beloved niece. "Could you have solved it if, in addition to the latest rules of Dr. Ban, no two chimps who hate each other could be at the same level? If you can't, can you minimize the number of such situations?"
"I have a movie to do, uncle," Liane said as she rushed out the door with her digital camera.
I never heard the answer.
Reader: Would you like to take a crack at this?
Last Month's Solution
One way the prisoner could have escaped is shown in Table 1. Also see Figure 1.
Reader Notes
In addition to taking a few liberties with the biology in the "Micro virus" problem (DDJ, June 2000), I also neglected to tell you about some special cases. The r3 restriction enzyme will not cut every pair of Ts. In particular: If r3 sees TTT, it will cut this as T TT. If r3 sees TTTT, it will cut this as T TT T. If r3 sees TTTTT, it will cut this as T TT TT.
Further, there is the potential for an interaction between the enzyme for CT and the one for TT, so you should know that the three enzymes will cut:
CTT into C, T, T;
CTTT into C, T, TT;
CTTTT into C, T, T, TT;
CTTCT into C, T, TC, T; and
CTTTCT into C, T, TT, CT.
With some subset of these hints, the following clever readers found one or more solutions: Onno Waalewijn, David Cox, Patrick R. Schonfeld, Malcolm Rowe, and David Curran. Patrick had a simple explanation for his basic method: "For the short sequence, I simply generated all valid permutations: all permutations in which T follows C, G follows A, and T follows T. Then for each valid permutation, I calculated the r1,r2,r3,r1/ r2,r1/r3,r2/r3 cut sizes, and discarded all permutations whose cut sizes did not match the correct ones."
His method for the long sequence started with r2 cuts. Malcolm and Patrick both found four solutions for the second problem, which they believe is all there are.
DDJ
