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].
There should be more to the planet than coke cans, cockroaches, and creature comforts.
-- Ken Burns
Of medium height but good musculature, Burns introduced himself as a "beaster." He was already famous though: A self-made hi-tech billionaire who had retired at 35 to track dangerous animals. He would figure out their habits and how those habits were influenced by people. He used his money strategically, buying land here, putting up fences there, purchasing high technology when necessary. Amazingly courageous, he had attached GPS devices to hundreds of sleeping carnivores in order to track them. ("As long as I don't touch the cubs, no animal attacks me.") Secretive, he waited until he had a complete story and had made all his purchases before announcing anything to the world.
"We want to ensure the genetic diversity of a certain large jungle mammal -- call it an X-mammal -- in Brazil," Burns said. "Hunting has already decimated their population, but they can recover from that, now that there is no market for their bones. On the other hand, destruction of habitat may destroy their genetic diversity, leaving them helpless should a disease hit.
"I've mapped out the area where there is jungle left and I've bought 10 large tracts to keep the X-mammals safe. The tracts are all surrounded by farms and my studies have shown that the animals won't cross open fields. So, I'm also prepared to buy corridors through the farms that haven't destroyed all of their jungle. The question though is which corridors to buy."
Burns paused to look at Ecco.
"I know you want to keep this all secret Dr. Burns," Ecco said. "But we at least need to know about the social habits of X-mammals in order to help you."
"Of course you need more information," Burns said in a forced neutral tone. "Everyone does. Very well, this is what I've found. Each tract of land that I'm buying holds one female and her children. Only two of those children grow to adulthood and it seems always to be one male and one female. (This is the result of fights and, in some cases, deliberate maternal favoritism.) The males will never mate with their sisters or mothers, nor with any female X-mammal that is more than one corridor from their maternal home. The female in a tract will choose one mate, at random I believe, but will not demand fidelity, leaving that male to try his luck with some other female whose home is one corridor away from that male's maternal territory."
"So the females are the responsible ones. How unusual...," Liane said with a good-natured 12-year-old grin.
"Right," Burns replied. "The females raise the family. Each male tries to father as many families among neighboring females as possible and then usually fights to the death somewhere and dies. The adult females don't live much longer, so you can assume that each generation lasts three years and that there is no intermarriage among generations.
"My studies indicate that the X-mammals require genetic diversity in 15 traits, each corresponding to one gene. Genes are passed down through the generations in the normal way. That is, for each trait, one gene comes from the mother and one from the father. Each gene can have two values called "alleles." For trait k, I denote those two alleles as Ak and Bk. So, if there were 10 traits for example, a beast may receive A1, B2, A3, A4, B5, B6, B7, B8, A9, and B10 from its father and A1, A2, A3, B4, A5, A6, B7, B8, B9, and B10 from its mother.
"For each trait, neither allele has a genetic advantage when there is no disease. I don't know which allele has an advantage when there is a disease so I think both should be preserved."
"Are the genes passed on independently, as in Mendel's pea experiments?" Ecco asked.
"Yes, they seem to be," Burns replied. "In the example above, for instance, the beast may pass A1, A2, A3, B4, B5, A6, B7, B8, B9, and B10 to one child and A1, B2, A3, A4, B5, B6, B7, B8, A9, and B10 to another child.
"The cheapest corridor topology is just a chain among the 10 tracts. The cheapest might not be worst. A completely connected population leaves open the possibility that a single male could impregnate all the females. So, I'd like to find out how long the diversity will be propagated through the generations if I just keep that topology."
"Could you help us with an example?" Liane asked.
"Let's try one trait and one family with incest allowed (even though it isn't allowed in the real case)," Burns replied. "The mother has an A and a B allele and so does the father."
"So, each kid might get an A from both mother and father (1/4 chance for each kid) and the biodiversity would be lost," Liane continued.
"Exactly," Burns replied, surprised at this quickness. "Have you ever considered a career in high technology?"
"Can you give us the genetic makeup of the animals to begin with?"
"Yes," said Burns. "They are shown in this table (see Table 1), though you may not need this level of detail. Basically, you need to know that both the A and B alleles for each trait are present in the population in significant numbers to begin with.
"So, here is my option," Burns continued. "Option one: I can keep the linear topology in which tract 0 is connected to tract 1, tract 1 to tract 2, and so on up to tract 8 and tract 9 (but not tract 9 and tract 0). Or I can buy more corridors up to a completely connected set of tracts.
"And I have two unknowns. Unknown one: Maybe the genes are linked. For example, it might be that the genes for most (or even all) of the traits lie on the same chromosome. If they all did and were close together, then it would be likely that the female from tract 9 would pass either B0 A1 B2 A3 A4 B5 A6 B7 B8 B9 A10 B11 B12 B13 B14 to a child or A0 B1 B2 B3 B4 B5 B6 A7 B8 B9 B10 A11 B12 B13 B14 to a child. If the traits were not linked, then a child of that female might get B0 B1 B2 A3 B4, and so on.
"Unknown two: I've assumed that females will mate with any available male with equal probability, but it might be that some males dominate others in a contest. This happens in many animals as we all know...
"So, my first question to you is: Which connected corridor topology option should I choose to maximize the number of generations in which at least some genetic diversity is preserved? (By connected, I mean that it should be possible, through the generations, for one X-mammal's genes to affect a descendant's X-mammal's genes in any tract of land. This is vital for the normal survival traits I don't measure. Another way to look at this is that it should be possible to walk from any tract to any other tract through tracts and corridors.)
Reader: Would you like to take a crack at this?
"Second, could I preserve diversity better by isolating the X-mammals from one another? There is precedent for this: The South American marsupials lost out when South America became connected to North America.
Reader?
"Third, assuming a connected topology, how do the unknowns affect the number of generations it takes for all biodiversity to disappear? Does biodiversity disappear earlier if there is linkage? Does it disappear earlier if there are dominant males?"
Reader: Try to answer these questions in a quantitative way. Compare the scenarios that best preserve biodiversity to those that worst preserve biodiversity and estimate the ratio of the numbers of generations it takes for all diversity to disappear in the two cases. Consider only connected topologies.
Last Month's Solution
Here is Liane's solution to the two problems Dr. Ban posed. This solution subsumes the answer to Dr. Ban's first one.
top level
Aristotle Cecily Chimpie
Lea Natasha Marie
Didi Augustine Katie
next level
Sarah Miles Victoria
Carlie Jonathan Goodall
Annie Darwin Millie
bottom level
Humboldt Napoleon Emily
Zoe Theo Coco
Cordelia Caesar Julia
Reader Notes
The Wordsnakes puzzle (DDJ, August 2000) was to find an ordering among a list of words that gives the highest possible score, where the score is the sum of the scores of the overlaps among adjacent words and the score of an overlap is the square of the size of the overlap. The puzzle presented a list (not in order) and asked readers to find the best order. (The word list had a slight bug. Allen Windhorn pointed out the correct spelling of the word "tessellate." Fortunately, this made no difference in the approach to the solution or the score.)
Alan Schnell, Patrick R. Schonfeld, Earl Paddon, John A. Trono, Dennis Yelle, Kim Pfeifle, Tomas Rokicki, and Dave Curran matched Liane's solution of 357.
Schonfeld, Yelle, and Rokicki found 40 solutions that reached this total. Schonfeld was the first to prove that there cannot be a better one as follows:
1. Each word in the given 39-word list has at least one successor.
2. For each word in the list, determine which successor has the maximum overlap with the word.
3. Add up the squares of these maximum successor overlaps. The sum is 358.
4. Because the last word of a Wordsnake does not have a successor, the sum in the previous step must be reduced by the smallest squared overlap, which is one.
5. Therefore, the maximum score is 357.
David Curran reported the best English 18 letter worksnake: "conversationalists." This simple word yields a score of 663 having the breakdown: con, conversation, conversational, conversationalist, conversationalists, and lists.
Genny Engel managed to beat this with the 15-letter wordsnake "misrepresentations": misrepresent, misrepresentation, misrepresentations, representation, representations, presentations, and ions. This gave her a score of 843.
Martin Laeuter of the mathematics department at Leipzig suggests the following 18 letter German wordsnake: "verwirtschaftetest." From this, the following words are present giving a total of 993 points, an impressive achievement: verwirtschaftete, verwirtschaftetes, erwirtschaftetes, erwirtschaftetest, and wirtschaftetest.
OK, now to the meanings. The used verbs are verwirtschaften, erwirtschaften, and wirtschaften. To begin from the last, wirtschaften is the action of organizing things economically, e.g. making ends meet in the household or the tasks of a manager (to manage affairs). erwirtschaften is working so that money or other means are available to pay expenses. verwirtschaften is simply bad wirtschaften, bad management."
Wordsnakes suggested other games to some clever readers. Earl Paddon suggested a new game called "Hidden Wordsnake":
Simply, a hidden Wordsnake is a regular Wordsnake which is also a word. Examples are hidden (hid, hidden, den), intended (intend, tend, end, ended), and controlled (control, troll, roll, rolled, led). Hope it isn't contagious, seems as though I cannot look at a word without trying to break it down.
He notes as an example that the following all appear in Websters New Universal Unabridged, Second Edition: "ate" can be broken down to a,at,ate,te,e.
David Cox suggested a variant in which there is a bonus if the overlap of two consecutive words in a wordsnake is a word itself.
Michael D. Christenson reports a game for people with amazing memories:
We play a phonic version while hiking called "Jabberwalking." One person starts with a word: harmonica, for instance. The next person repeats that, and adds a word: harmo-Nicaragua. The third person repeats the string: harmo-Nicara-guacamole. This can go on for hours, depending on the hike.
DDJ
