Tanya Khovanova's Math Blog

Langton’s ant travels on the infinite square grid, colored black and white. At each time step the ant moves one cell forward. The ant’s direction changes according to the color of the cell he moves onto. The ant turns 90 degrees left if the cell is white, and 90 degrees right if the cell is black. After that, the cell he is on changes its color to the opposite color.

There is a symmetry of time and space for this ant. If at any point of the ant’s travel, someone interferes and reverses the ant’s direction in between the cells, the ant and the grid will traverse the steps and stages back to the starting point.

Let’s give this ant a life. I mean, let’s place him inside the Game of Life invented by John H. Conway. In addition to the Langton’s ant’s rules, I want the cells to change colors according to the rules of the Game of Life.

Let me remind you of the rules of Conway’s Game of Life. We call black cells live cells and white cells dead cells. Black is life and white is death. The cell has eight neighbors — horizontal, vertical, diagonal. At each time step:

• A cell dies of agoraphobia, if it has more than three neighbors.
• A cell dies of boredom, if it has less than two neighbors.
• A dead cell can be born again, if it has exactly three neighbors.
• Otherwise, the cell’s status doesn’t change.

So, our ant will be traveling in this dying and reproducing population and correcting nature’s mistakes. He revives dead cells and kills live cells.

There is an ambiguity in this ant’s life description. The life can happen at two different moments. In the first ant’s world, the ant jumps from one cell to the next, and while he is in the air, the cells have time to copulate, give birth and die. Upon landing, the ant changes direction and uses his magic wand to change the life status of its landing cell. In the second ant’s world, the ant moves to the destination cell, changes its own direction and the status of the cell and then takes a smoke. All the fun, sex and death happen while he is enjoying his cigarette.

The ant’s life has symmetry in a way that is similar to the symmetry of the ant without life. If we reverse the ant’s direction back and also switch his life-style from the first to the second or vice versa, then the ant and the grid will go backwards in their states.

The parameters for the Langton’s ant were chosen to make the ant’s behavior interesting. The parameters of the Game of Life were chosen to make the Game of Life’s behavior interesting. To make the ant’s life fascinating, we might want to modify the ant’s behavior or the Life’s rules. The synergy of the ant and the Life might be intriguing only if the ant changes its behavior and the Life changes its rules.

Let’s experiment and discover how we need to change the rules in order to make the ant’s life interesting.

John H. Conway is teaching me his doomsday algorithm to calculate the day of the week for any day. The first lesson was devoted to 2009. “The 2009’s Doomsday is Saturday” is a magic phrase I need to remember.

The doomsday of a particular year is the day of the week on which the last day of February falls. February 28 of 2009 is Saturday, thus 2009’s doomsday is Saturday. For leap years it is the day of the week of February 29. We can combine the rules for leap years and non-leap years into one common rule: that the doomsday of a particular year is the day of the week of March 0.

If you know the day of the week of one of the days in 2009, you can theoretically calculate the day of the week of any other day that year. To save yourself time, you can learn by heart all the days of the year that fall on doomsday. That is actually what Conway does, and that is why he is so fast with calculations. The beauty of the algorithm is that the days of the doomsday are almost the same each year. They are the same for all months other than January and February; and in January and February you need to make a small adjustment for a leap year. That gives me hope that after I learn how to calculate days in 2009 I can easily move to any year.

To get us going we do not need to remember all the doomsday days in 2009. It is enough to remember one day for each month. We already know one for February, which works for March too. As there are 28 days in February, January 31 happens on a doomsday. Or January 32 for leap years.

Now we need to choose days for other months that are on doomsday and at the same time are easy to remember. Here is a nice set: 4/4, 6/6, 8/8. 10/10. For even months the days that are the same as the month will work. The reason it works so nicely is that two consecutive months starting with an even-numbered month, excluding February and December, have the sum of days equaling 61. Hence, those two months plus two days are 63, which is divisible by 7.

Remembering one of the doomsdays for every other month might be enough to significantly simplify calculations. But if you want a day for every month, there are additional doomsday days to remember on odd numbered months: 5/9, 9/5, 7/11 and 11/7. These days can be memorized as a mnemonic “9-5 job at 7-11,” or, if you prefer, “I do not want to have a 9-5 job at 7-11.”

If you throw in March 7, then the rule will fit into a poem John recited to me:

The last of Feb., or of Jan. will do
(Except that in leap years it’s Jan. 32).
Then for even months use the month’s own day,
And for odd ones add 4, or take it away*.

*According to length or simply remember,
you only subtract for September or November.

Let’s see how I calculate the day of the week for my friend’s birthday, July 29. The 11th of July falls on the doomsday, hence July 25 must be a doomsday. So we can see that my friend will celebrate on Wednesday this year.

You might ask why I described this trivial example in such detail. The reason is that you might be tempted to subtract 11 from 29, getting 18 and saying that you need to add four days to Saturday. In the method I described the calculation is equivalent, but as a bonus you calculate another day for the doomsday and consequently, you are getting closer to John Conway who remembers all doomsdays.

My homework is the same as your homework: practice calculating the days of the week for 2009.

Visitors to the math department of Princeton University used to stop by John Conway’s office. Even if it were closed, they could peek through the window in the door to see the many beautiful, symmetric figures hanging in his office.

The figures, which John Conway had made, were there for 20 years. Just recently John received a letter informing him that his office had been inspected by the State Fire Marshall and that “those things hanging from your ceiling are against the State’s fire code and must be taken down.” The math department was worried about a possible fine.

So John threw away the “things.” I wanted to cry as I watched these huge garbage bags being taken away. I rescued several figures, but that was all that I could fit into my car. For 20 years no one complained, but now the bureaucracy has beat out beauty and mathematics.

This picture is the last view of the “hazardous” office.

On one of my visits to Princeton, I stopped by the math department and, as usual, asked John H. Conway what he was up to. He told me that he was turning numbers inside out. He explained that to perform this procedure on a number you need to reverse every prime factor, multiply the reversed factors back and reverse the result. For example, for 34, which is the product of 2 and 17, we need to reverse 2 and 17 (turning inside), changing them into 2 and 71, multiply back, getting 142, and reversing again (turning outside), leading to the resulting number 241.

He started with a number, turned it inside out, then turned the result inside out, and so on, thus getting an infinite sequence for any number. Every sequence he had calculated up to this point ended with a cycle.

Before I had interrupted him, he was calculating the sequence starting with 78 and it was growing. I suggested that Mathematica could do this calculation faster than John could do in his head. Although that was very rude considering his reputation for speed, John agreed, and we moved to a computer. The computer confirmed that the sequence starting with 78 was growing wildly.

While playing around with this, I became very interested in numbers that are fixed under this turning inside-out operation. First, prime numbers do not change — you just reverse them twice. Second, palindromes with palindromic primes do not change, as every reversal encounters a palindrome to apply itself to. I started to wonder if there are palindromes that are fixed under the turning inside-out procedure, but are not products of palindromic primes.

Here is where John had his revenge. He told me that he would be able to find such a number faster than I could write a program to find it. And he won! He found such a number while I was still trying to debug my program. The number he found was 1226221.

Here is how he beat me. If you have two not-too-big primes that consist of zeroes and ones and that are reversals of each other, their product will be a palindrome. And John is really fast in checking primes for primality. See his lesson in my essay Remember Your Primes.

The next day, when I stumbled on John again, he was doing something else. I asked him about the numbers and he told me that he was no longer interested. Initially he had hoped that every sequence would end in a cycle. The turning inside-out operation doesn’t produce much growth in a number. On top of that, prime numbers are stable. That means that if the turning inside-out operation was a random operation with a similar growth pattern, there would have been a very high probability of every sequence eventually hitting a prime. But the operation is not random, as it doesn’t change remainders modulo 9. In particular, sequences that start with a composite number divisible by 3 would never hit a prime. Our experiment with 78 discouraged him by showing no hope for a cycle.

I asked him, “Why not do it in binary?” He answered that he had sinned enough playing with a base 10 sequence.

A year later when I next visited Princeton and saw John again, I asked him if he had published or done something with the operation. He had not. He agreed to submit the sequence to the online database, but only if we came up with a name he liked. And we did. We now call this operation TITO (turning inside, turning outside). Please welcome TITO.

When my son Sergei made it to the International Linguistics Olympiad I got very excited. After I calmed down I realized that training for this competition is not easy because it is very difficult to find linguistics puzzles in English. This in turn is because these Olympiads started in the USSR many years ago and were adopted here only recently. So I started translating problems from Russian and designing them myself for my son and his team. For this particular problem I had an ulterior motive. I wanted to remind my son and his team of rare words in English with Greek origins. Here is the problem:

We use many words that have Greek origins, for example: amoral, asymmetric, barometer, chronology, demagogue, dermatology, gynecologist, horoscope, mania, mystic, orthodox, philosophy, photography, polygon, psychology, telegram and telephone. In this puzzle, I assume that you know the meanings of these words. Also, since I am a generous person, I will give you definitions from Answers.com of some additional words derived from Greek. If you do not know these words, you should learn them, as I picked words for this list that gave me at least one million Google results.

• Agoraphobia — an abnormal fear of open or public places.
• Anagram — a word or phrase formed by reordering the letters of another word or phrase, such as satin to stain.
• Alexander — defender of men.
• Amphibian — an animal capable of living both on land and in water.
• Anthropology — the scientific study of the origin, the behavior, and the physical, social, and cultural development of humans.
• Antipathy — a strong feeling of aversion or repugnance.
• Antonym — a word having a meaning opposite to that of another word.
• Bibliophile — a lover of books or a collector of books.
• Dyslexia — a learning disability characterized by problems in reading, spelling, writing, speaking or listening.
• Fibromyalgia — muscle pain.
• Hippodrome — an arena for equestrian shows.
• Misogyny — hatred of women.
• Otorhinolaryngology — the medical specialty concerned with diseases of the ear, nose and throat.
• Pedophilia — the act or fantasy on the part of an adult of engaging in sexual activity with a child or children.
• Polygamy — the condition or practice of having more than one spouse at one time.
• Polyglot — a person having a speaking, reading, or writing knowledge of several languages.
• Tachycardia — a rapid heart rate.
• Telepathy — communication through means other than the senses, as by the exercise of an occult power.
• Toxicology — the study of the nature, effects, and detection of poisons and the treatment of poisoning.

In the list below, I picked very rare English words with Greek origins. You can derive the meanings of these words without looking in a dictionary, just by using your knowledge of the Greek words above.

• Barology
• Bibliophobia
• Cardialgia
• Dromomania
• Gynophilia
• Hippophobia
• Logophobia
• Misandry
• Misanthropy
• Misogamy
• Monandry
• Monoglottism
• Mystagogue
• Pedagogue
• Philanthropism

Here are some other words. You do not have enough information in this text to derive their definitions, but you might be able to use your erudition to guess the meaning.

• Antinomy
• Apatheist
• Axiology
• Dactyloscopy
• Enneagon
• Oology
• Paraskevidekatriaphobia
• Philadelphia
• Phytology
• Triskaidekaphobia

Robert Calderbank and Ingrid Daubechies jointly taught a course called “The Theory of Games” at Princeton University in the spring. When I heard about it I envied the students of Princeton — what a team to learn from!

Here is a glimpse of this course — a problem on Evolutionarily Stable Strategy from their midterm exam with a poem written by Ingrid:

On an island far far away, with wonderful beaches
Lived a star-bellied people of Seuss-imagin’d Sneetches.

Others liked it there too — they loved the beachy smell,
From their boats they would yell “Can we live here as well?”
But it wasn’t to be — steadfast was the “No” to the Snootches:
For their name could and would rhyme only with booches …

Until with some Lorxes they came!
These now also enter’d the game;
A momentous change this wrought
As they found, after deep thought.

Can YOU tell me now
How oh yes, how?
In what groupings or factions
Or gaggles and fractions
They all settled down?

Sneetches and Snootches only:

Sneetches and Snootches and Lorxes:

Find all the ESSes, in both cases.

My guest blogger is a friend and a wordsmith Sue Kelman:

* * *

Rizzo (Ratso to his friends) was my cage mate. We had a nifty pad at Children’s Hospital — all we could eat with no scrounging, clean beds, quiet surroundings, and plenty of activity to keep us occupied.

Rizzo’s favorite was the maze. Each week he bragged to us about how fast he made it through to the cheese. Larry over in Row-D was always the slowest. All the guys used to razz him about it. No matter how hard he tried, Larry took the wrong turn every time. I think his mother spent some time out at a psych hospital, so maybe they messed with her brain and that affected Larry. Who knows? I suspect that know-it-all visiting researcher from MIT knows what happened to Larry but he’s probably keeping it under his hat until he publishes his results in JAMA. Putz!

Okay, so one day, Rizzo just came back from one of those tests where they make us hit a little button when the red and green lights go on. Personally this is my favorite gig because of course there’s no running around, but Rizzo likes to throw a monkey wrench into the research data. So every now and then, even when he knows how we should respond, he does just the opposite. I told you, he’s one smart rodent.

Rizzo’s pretty famous, too. Oh he’s not as famous as that talking grey parrot that used to be over at Harvard, but he’s been around. For a while he was a top gun — the big performer for a group of genetics guys. He’s had his DNA tested more times than Mike Tyson.

Then they lent him out to Hematology where, I swear, the guy’s already had 15 blood transfusions. No wonder he’s healthy as a horse.

Me, I’m just your average lab rat. I know the drill: wake up, eat a few pellets, perform, eat some more pellets, doze off, and wake up to do it all over again. Not a bad life if you can stay away from those vivisection weirdos. They’re like Dr. Mengele all over again.

I’d tell you more but Rizzo’s gonna tell us about the time he got out of his cage and made it almost all the way to the Starbucks wagon before they caught him. Great story and he’s a real raconteur. None of that Stuart Little crap. We fall over laughing every time we hear it. Gotta go.

Due to the popularity of my previous posting of linguistics puzzles, I’ve translated some more puzzles from the online book Problems from Linguistics Olympiads 1965-1975. I’ve kept the same problem number as in the book; and I’ve used the Unicode encoding for special characters.

Problem 180. Three Tajik sentences in Russian transliteration with their translations are below:

• дӯсти хуби ҳамсояи шумо — a good friend of your neighbor
• ҳамсояи дӯсти хуби шумо — a neighbor of your good friend
• ҳамсояи хуби дӯсти шумо — a good neighbor of your friend

Your task is to assign a meaning to each out of four used Tajik words.

Problem 185. For every sequence of words given below, explain whether it can be used in a grammatically correct English sentence. If it is possible show an example. In the usage there shouldn’t be any extra signs between the given words.

1. could to
2. he have
3. that that
4. the John
5. he should
6. on walked
7. the did

Problem 241. In a group of relatives each person is denoted by a lower-case letter and relations by upper-case letters. The relations can be summarized in a table below:

The table should be read as following: if the intersection of the row x and the column y has symbol Z, then x is Z with respect to y. It is known that e is a man.

You task is to find out the meaning of every capital letter in the table (each letter can be represented as one English word).