Extraterrestrial Ants Puzzle
The lesser-known tracking problem
We'll get to the extraterrestrial ants in a later section. The actual puzzle is a food-locating problem that ants from the planet Ox face on a daily basis.
But for background, let's talk about more familiar navigation issues that Earthly dogs and Earthly ants have solved in slightly different ways.
Search-and-Rescue Dogs have saved the lives of countless lost hikers.
In order to learn the missing hiker's scent, the dog may sniff a pen (better still, a remote control!) or some other item belonging to the person in question. Then the dog is taken to the general area where the lost hiker was last seen. Eventually, the dog locates the scent trail. Question: Does the dog turn right, or does he turn left?
If we were talking about bare footprints, instead of scent trails, this would not be an problem. There's an obvious rule-of-thumb. Or should I say, "rule of toes?"
The highly intelligent tracking dog exploits a property of outdoor scent trails. The person's dander particles within the plume disperse over time. This widens the older part of the plume. The scent plume is narrowest near the source.
The dog crosses the scent plume at two locations. Then he goes in the direction where the plume is narrower.
After a few hours of joyful walking and sniffing, the dog locates the lost hiker, and receives an enthusiastic atta-boy from his handler. However the canine strategy is not ubiquitous throughout the Animal Kingdom.
Feynman's ant experiment
The late Richard Feynman was a Nobel Laureate in Physics. However his keen curiosity about the Natural World extended well beyond his specialty. Here's a summary of a scientific exploit mentioned in one of the biographies.
One fine day, Feynman noticed that some ants had invaded his cupboard. He surmised that the ants leave chemical trails behind them, after finding a good food source. After the discoverer returns to the nest with his booty, other ants will follow the chemical trail directly to the food.
Feynman wanted to test the hypothesis, and to solve his ant problem in a nonviolent way.
He put a bit of sugar in the middle of the kitchen floor. Using a small scrap of paper, he ferried the ants--one at a time--from the main column to the sugar. Each ferried ant left a chemical trail from the sugar to the nest. Over time, the sugar scent trail became stronger and stronger.
The pantry scent trail slowly evaporated, and eventually died out. Initially the ants focused all of their efforts on the sugar. When all of the sugar granules had been transported back to the nest, the ants completely 'forgot' about the much larger supply of food in the pantry! This was an elegant way to test the scent trail hypothesis, without needing to do any chemical analysis.
An educated guess on my part: Unlike Search-and-Rescue dogs, Earthly ants do not need to worry about scent plume widths. The nest scent is quite strong. When a foraging ant encounters a food scent trail left by another ant, she instinctively turns away from the generic nest scent.
The ants of Planet Ox are similar to Feynman's ants. After finding a food source, they leave trail markers behind them, to guide other ants. However there's one important difference between Ox ants and their terrestrial counterparts.
Ox ants scrawl a trail of X's and/or O's behind them in the sand, as they carry the bits of food back to the nest. There's no interesting chemistry involved.
Their superior vision obviates the need for food-related pheromones. However this creates a new problem.
If a foraging ant stumbles across a food trail, how to determine the direction to the food source? If Ox ants always approached food trails from the same side, they could use a simple rule: If you see a trail of X's, turn left to find the food; otherwise turn right. However that's not a useful assumption in the real world--or even in the Ox world. A good food trail requires both X's and O's.
The puzzle: In order to yield unambiguous directionality, what is the minimum number of characters for a repeating unit of the long O-X trail?
If you're dying to know the answer, you can skip the next short section, and then read the solution.
A short history of the puzzle
The creation of the Extraterrestrial Ant Puzzle was a collaborative effort between mathematician Dean Hickerson and myself, while we were carpooling back to Sacramento County, after a hike to Feather Falls, near Oroville, California. After mentioning Feynman's ant experiment, I proposed the puzzle, and suggested that it had a solution.
Here is my intuition at the time. A binary symbol could be used in one of two ways: to indicate directionality in the 'unit cells', or to function as a wall between successive units of the repeating message. Then Dean became the first person to solve the Extraterrestrial Ant Puzzle. And the rest is history. :)
Here is one of the two minimal 'unit cells':
If we were to string four of these together, we would have
The two rules that all Ox ants understand is:
1. Don't take the double O's too seriously.
2. To find the food, turn in the direction of the excess X's.
The "excess X's" makes the second step difficult for me to pronounce quickly, but it's easy to remember.
If I was a foraging ant who walked up to the above string, I would mentally change all of the double O's to lower case, and the message would read as,
In Ox Ant Language, that means, "Turn left here."
If I'd approached from the opposite side , it would have read as,
which translates to, "Turn right here."
In either case, the trail would lead me to the food. Clever, those Ox ants.
The Green Tree Ant photo was courtesy of Jennifer Marohasy. She has a PhD in biology, and is a leading advocate for evidence-based environmental policy in Australia. A few of her strong interests include Australian water issues, seasonal rainfall forecasting, and the Great Barrier Reef.
Here's a LINK to her short blog post about the extraordinary ant species in the photo.
Copyright 2012 and 2013 by Larry Fields