Tanya Khovanova's Math Blog

For his Master’s thesis, my son Alexey Radul wrote the Symmetriad — a computer program to compute and display highly symmetric objects.

The objects the Symmetriad is after are the 4D generalizations of Platonic and Archimedean solids. His thesis contains a picture gallery made with the Symmetriad, and these are my three favorite pictures.

The pictures have cute titles. The problem is that I still haven’t installed the WordPress plugin that allows me to put captions under the pictures. That is why you have to guess which title matches which picture. The titles are: “The Planets are Aligned,” “Great Jaws,” and “Diamonds are Forever.”

If you are wondering why one of the pictures shows a non-connected object, in fact the object is connected, but some of the edges are white, so that you can better see 3D cells of the object.

Subsequent to the publication of this thesis, Alexey enhanced his software to make even more dramatic pictures. The following pictures have no titles, so feel free to suggest some:

I think it would be nice to publish a book with all these pictures. As a book on symmetries should be published on a symmetric date, the next opportunity would be 01.02.2010.

I love Grand Tour puzzles more than I love Sudoku. You are given a graph, for example, a square grid like the one on the left. Some edges are highlighted. You need to find a closed path that visits each vertex exactly once and includes the highlighted edges as part of the path. Mathematically speaking you need to reconstruct a Hamiltonian circuit on a graph, once you are given a part of it. The highlighted edges are chosen to guarantee a unique solution to the puzzle.

On the left you can see a sample grand tour problem with its solution. This puzzle was designed by Glenn Iba. On Glenn’s Grand Tour Puzzle Page you can find many grand tour puzzles of varying levels of difficulty. The puzzles are playable. That is, you can click or unclick an edge. You can also branch out in a different color, which is especially useful for difficult puzzles when you want to test a hypothesis. I just want to warn you: these puzzles are addictive — I couldn’t stop playing until I solved all of them.

Below there is a simple grand tour puzzle from Glenn’s collection, but this time on a triangular grid:

You do not need a grid to construct a puzzle. But these puzzles look very natural on grids. I tried to analyze square grid puzzles a little bit. The first important point is that for square grids with odd number of vertices on each side of the square, Hamiltonian cycles do not exist. This point is easier to prove for directed Hamiltonian cycles. You can make a directed cycle from an undirected one by choosing a direction. If you have a directed cycle on a square grid, then the number of edges pointing up should be the same as the number of edges pointing down. We can say the same thing about edges on the cycle pointing left or right. Hence, the number of edges of a Hamiltonian cycle on a square grid should be even. At the same time, the number of edges of any Hamiltonian cycle equals the number of vertices.

I just proved that you need only consider square grids with an even number of vertices on each side. For square grids with two vertices on each side, there is only one Hamiltonian cycle, namely the border of the square. The only grand tour puzzle for this grid won’t have highlighted edges at all. For a square grid with four vertices on each side there are only two different Hamiltonian cycles up to isomorpshisms:

If we count all the reflections and rotations, we will get six Hamiltonian cycles. The next picture shows all 11 grand tour puzzles on this grid. If we count rotations and reflections, we will get 66 different grand tour puzzles.

Below are the sequences associated with this puzzle. Except for one case, I do not know if these sequences are in the Online Encyclopedia for Integer Sequences. I don’t know because I only counted two terms of each sequence, and this information is not sufficient to identify the sequence.

• A003763 Number of Hamiltonian cycles on 2n by 2n square grid of points. The sequence starts 1, 6, 1072, ….
• Number of Hamiltonian cycles up to isomorphism on 2n by 2n square grid of points. The sequence starts 1, 2, ….
• Number of Grand Tour puzzles on 2n by 2n square grid of points. The sequence starts 1, 11, ….
• Number of Grand Tour puzzles up to isomorphism on 2n by 2n square grid of points. The sequence starts 1, 66, ….
• The smallest number of edges in a Grand Tour puzzle on 2n by 2n square grid of points. The sequence starts 0, 2, ….
• The largest number of edges in a Grand Tour puzzle on 2n by 2n square grid of points. The sequence starts 0, 4, ….

If you look at Glenn Iba’s 6 by 6 square grid puzzles, you can see that the smallest number of edges is not more than 6. And the largest number of edges is no less than 12.

You can also make similar sequences for a triangular grid.

I invite you to calculate these sequences and submit them to the OEIS, if they are not already there.

I’m not kidding; there is such a paper. It is titled, “A Headache-causing Problem” and its authors are Conway (J.H.), Paterson (M.S.), and Moscow (U.S.S.R.). The acknowledgements in the paper shed some light on how Moscow became a mathematician:

The work described here was carried out when the first and second named authors enjoyed the hospitality of the third. The second and third authors are indebted to the first for expository details. The first and third authors gratefully remark that without the constant stimulation and witty encouragement of the second author this paper

[The next part was meant to be on the following page, Conway told me, but the editor missed the humor and just continued the sentence…]

was completed.

As a consequence of this joke, Moscow is envied by many mathematicians as it has an Erdős number of 2. Now wait for a couple of hundred years, and Moscow will be the only living mathematician with an Erdős number of 2. I can just imagine future mathematicians trying to persuade Moscow to coauthor papers with them, because this will be the only way for them to score an Erdős number of 3.

Even though I lived there for 30 years, I had no idea that Moscow had a talent for math. Of course, this talent only emerged when Moscow was more than 800 years old.

This wonderful paper by Moscow was very difficult to find. It was presented to Hendrik W. Lenstra on the occasion of his doctoral examination. It was published in 1977 in a book titled “Een pak met een korte broek,” which in Dutch means, “A Book in Short Trousers.”

I tried to find it on the Internet — it wasn’t there. I asked John Conway — it took him quite some time to find it. Here is the picture of John Conway searching for a headache-causing problem. Luckily for you and me, he found it. To save you from another headache, I am uploading the scan of it in pdf format here: A Headache-causing Problem by J.H. Conway, M.S. Paterson, and U.S.S.R. Moscow.

I hope that Moscow will not start complaining that I never asked its permission to post the paper. Some might argue that Moscow, U.S.S.R., doesn’t exist anymore, but I would counter that it exists, but with a changed name. If Moscow tries to sue me, I hope it’s not because it is still bitter that I left it behind in 1990.

Hey Moscow, it’s time we were friends again. Would you like to co-author a paper with me?

The Symmetries of Things by John H. Conway, Heidi Burgiel, and Chaim Goodman-Strauss is out. It is a beautiful edition with great pictures.

The first chapter is very nicely written and might be recommended to high school and undergraduate students. It covers symmetries of finite and infinite 2D objects.

The second chapter adds color to the theory. For beautiful colorful pictures with symmetry, there are two symmetry groups: the group that preserves the picture while ignoring its coloring and the group that preserves the picture while respecting its coloring. The latter group is a subgroup of a former group. This second chapter discusses all possible ways to symmetrically color a symmetric 2D picture. The chapter then continues with a discussion of group theory. This chapter is much more difficult to read than the first chapter, as it uses a lot of notations. The pictures are still beautiful, though.

The third chapter is even more difficult to read and the notations become even heavier. This chapter discusses hyperbolic groups and symmetries of objects in the hyperbolic space. Then the chapter moves into 3D and 4D. I guess that some parts of the second and the third chapters are not meant for light reading; they should be considered more as reference materials.

Here are pictures of a musnub cube (multiplied snub cube), built by John H. Conway. It is an infinite Archimedean polyhedron. The description of it is on page 338 and the diagram is on page 339 of the book. This object was glued together from stars and squares. Each corner of the square is glued to a point of one star and to an inside corner of another star. Mathematically, a star is not a regular polygon. If you look at stars with your mathematical eye, each star in the picture is not just a star, but rather the union of a regular hexagon with 6 regular triangles. That means the list of the face sizes around each vertex of a musnub cube officially is represented as 6.3.4.3.3.

The second picture shows a finished musnub cube. You can’t really finish building an infinite structure. Right? It is finished in the sense that John Conway finished doing what he was planning to do: to construct a part of a musnub cube inside a regular triangular pyramid.

Did I mention that I like the pictures in The Symmetries of Things?

Here I repeat the Conway’s Wizards Puzzle from a previous posting:

Last night I sat behind two wizards on a bus, and overheard the following:

— A: “I have a positive integral number of children, whose ages are positive integers, the sum of which is the number of this bus, while the product is my own age.”
— B: “How interesting! Perhaps if you told me your age and the number of your children, I could work out their individual ages?”
— A: “No.”
— B: “Aha! AT LAST I know how old you are!”

Now what was the number of the bus?

It is obvious that the first wizard has more than two children. If he had one child then his/her age would be the number of the bus and it would be the same as the father’s age. While it is unrealistic, in mathematics many strange things can happen. The important part is that if the wizard A had one child he couldn’t have said ‘No’. The same is true for two children: their age distribution is uniquely defined by the sum and the product of their ages.

Here is a generalization of this puzzle:

Last night I sat behind two wizards on a bus, and overheard the following:

— Wizard A: “I have a positive integral number of children, whose ages are positive integers, the sum of which is the number of this bus, while the product is my own age. Also, the sum of the squares of their ages is the number of dinosaurs in my collection.”
— Wizard B: “How interesting! Perhaps if you told me your age, the number of your children, and the number of dinosaurs, I could work out your children’s individual ages. ”
— Wizard A: “No.”
— Wizard B: “Aha! AT LAST I know how old you are!”

Now what was the number of the bus?

As usual with generalizations, they are drifting far from real life. For this puzzle, you have to open up your mind. In Conway’s original puzzle you do not need to assume that the wizard’s age is in a particular range, but once you solve it, you see that his age makes sense. In this generalized puzzle, you should assume that wizards can live thousands of years, and keep their libido that whole time. Wizards might spend so much of their youth thinking, that they postpone starting their families for a long time. The wizards’ wives are also generalized. They can produce children in great quantities and deliver multiple children at the same time in numbers exceeding the current world record.

Another difference with the original puzzle is that you can’t solve this one without a computer.

You can continue to the next step of generalization and create another puzzle by adding the next symmetric polynomial on the ages of the children, for example, the sum of cubes. In this case, I do not know if the puzzle works: that is, if there is an “AHA” moment there. I invite you, mighty geeks, to try it. Please, send me the answer.

In case you are wondering why the wizard is collecting dinosaurs, I need to point out to you that John H. Conway is a superb puzzle inventor. His puzzle includes a notation suggestion: a for the wizard’s age, b for the bus, c for the number of children. Hence, the dinosaurs.

Here is my simplified version of Conway’s wizards puzzle.

Last night when I was coming home from my writing class with Sue Katz, I sat behind two wizards on the bus, and overheard the following:

— Wizard A: “I have a positive integral number of children, whose ages are positive integers, the sum of which is the number of this bus, while the product is the amount of dollars I have in my pocket.”

At this point I interrupted the wizard. “Excuse me, professor, I overheard your conversation and can’t resist asking you a question. Usually when a father says ‘my children’ everyone assumes that he has at least two children. Can I assume that?”

— Wizard A: “No. I stated my assumptions up front. A positive integral number of children means one or more.”

I started thinking. If I were to explain this to a non-mathematician who assumes that ‘my children’ means more than one child, I would need to change the wizard’s statement into the following:

“I have at least one child. The ages of my one-or-more children are all positive integers. The sum of the ages of my children or the age of my only child is the number of this bus. The product of the ages of my children or my only child’s age is the amount of dollars I have in my pocket.”

Hmm. I like that mathematicians use ‘my children’ to indicate any number of children. Makes puzzles faster to type.

Anyway, the wizards continued their discussion:

— Wizard B: “How interesting! Perhaps if you told me the number of your children, I could work out their individual ages”
— Wizard A: “No.”
— Wizard B: “Aha! AT LAST I know how many children you have!”

If I were John Conway, I would have asked you next, “What is the number of the bus?” As I am not John Conway, I’ll ask you, “Why do we presume that Wizard A hasn’t cheated on his wife?”

The answer is that all wizards are notorious for making precise statements. If he cheats a lot, he would have started the conversation with, “The number of children I know about is a positive integer.” Or maybe, more discreetly, “My wife and I have a positive integral number of children.”

If you have already figured out the number of the bus, the bonus question is, “Why did I change the ‘age of the first wizard’ in Conway’s original puzzle into the ‘amount of dollars’ in my puzzle?”

When I left the bus, I started wondering why on earth anyone would ever want to sum up the ages of their children. And I remembered that I once did it myself. I was trying to persuade my sister to apply for U.S. citizenship. My argument was that by moving here the life expectancy of her children would increase by 30 years. Indeed, she has two sons and the male life expectancy in Russia and the U.S. has an astonishing 15-year difference. I have to admit that my argument is not very clean, as we do not know the causes for this difference and, besides, the data is for life expectancy at birth and it changes while our kids age. My sister dismissed my argument, saying that the low male life expectancy in Russia is due to alcoholism and that her family is not in the high-risk group.

So, there could be a reason to sum up the ages of your children, but why would anyone ever want to multiply the ages of their children? In any case, if the first wizard continues to keep an amount of dollars equaling the product of the ages of his children in his pocket, his pocket will do better than mutual funds for the next several years.

John Conway sent me a puzzle about wizards, which he invented in the sixties. Here it is:

Last night I sat behind two wizards on a bus, and overheard the following:

— A: “I have a positive integral number of children, whose ages are positive integers, the sum of which is the number of this bus, while the product is my own age.”
— B: “How interesting! Perhaps if you told me your age and the number of your children, I could work out their individual ages?”
— A: “No.”
— B: “Aha! AT LAST I know how old you are!”

Now what was the number of the bus?

The smallest positive index m such that the Fibonacci number F_m is divisible by the number p is called the rank of apparition of p. If p is prime, one can prove that any Fibonacci number that is divisible by p has an index divisible by m.

Even Fibonaccis have indices divisible by 3. That means that if for some p the rank of apparition of p is divisible by three, all the Fibonaccis that are divisible by p are even. Therefore, no odd Fibonacci divides p. I already discussed this subject in my previous post “9 Divided no Odd Fibonacci.”

Now let’s look more closely at the set of primes that divide no odd Fibonacci. The Fibonacci numbers obey the following identity: F_n+k = (1/2)(F_nL_k + F_kL_n), where L_n are Lucas numbers. From here F_3n = (1/2)F_n(L_2n + L_n²). Like Fibonacci numbers, exactly every third Lucas number is even. Hence, the parity of L_2n is the same as the parity of L_n. Hence, L_2n + L_n² is divisible by 2. Let us denote G_n = (1/2)(L_2n + L_n²).

As we have already discussed before, if no odd Fibonacci is divisible by p, p‘s rank of apparition is of the form 3n which means p divides F_3n and doesn’t divide F_n. Hence, p divides G_n. On the other hand, we can show that G_n = 5F_n² + 3(-1)ⁿ. Hence, the only common divisor that F_n and G_n can have is 3. Let us take any prime divisor s of G_n other than 3. We see that F_3n is divisible by s while F_n is not. The rank of apparition of s must be a divisor of 3n and not a divisor of n. Hence this rank is divisible by 3. Thus we can see that with the exception of 3, the set of prime divisors of elements of G_n is the set of primes that do not divide odd Fibonaccis.

Here’s a bit more info about the sequence G_n. It is sequence A047946 in the Online Encyclopedia of Integer Sequences. It is a recurrence: G_n=2*G_n-1+2*G_n-2-G_n-3. Thus, we have found a recursive sequence, elements of which have a set of prime divisors which with the exception of 3 is the set of primes that do not divide odd Fibonacci numbers.

My favorite puzzle at 2008 MIT Mystery Hunt was the puzzle named Functions. Here is this puzzle:

36 -> 18      A,B
2 -> 1        A,C,G,H,K,L,O
512 -> 256    A,C,H
4 -> 2        A,G,H,Q
320 -> 160    A,R
411 -> 4      B,E,Q
13 -> 3       B,G,K
88 -> 11      C,D
45 -> 9       C,D,F,J,L
48 -> 6       C,G,M,P,Q
4 -> 1        C,K,L,N,O
36 -> 9       D,E,F
66 -> 8       D,E,G,I
10 -> 3       D,G,L
1 -> 3        D,L
150 -> 15     D,M
3 -> 2        E,H,J,K
25 -> 3       E,K,L,N,Q
9477 -> 14    E,M
129 -> 4      E,N,P
55 -> 10      F,J
411 -> 6      F,K,L,M,N
2002 -> 4     F,O,Q
79 -> 8       G,I,L,P
25 -> 20      H,M
176 -> 80     H,R
3665 -> 8     I,N,Q
7 -> 3        K,Q
11 -> 5       L,M
501 -> 2      L,O,P,Q
8190 -> 5     M,O
180 -> 3      O,P
50 -> 10      R

? -> (?)      F,R
(?) -> ?      J,L
(?) -> ?      A,F
(?) -> ?      N,O,Q
? -> (?)      A,D,J
(?) -> ?      D,H
(?) -> ?      G,K,Q
? -> (?)      B,D,M
(?) -> ?      E,H
? -> (?)      D,F,G,L
? -> (?)      C,G,P

Do you know that 1210 is the smallest autobiographical number? You probably do not know what an autobiographical number is. You are right if you think that such a number should be a pompous self-centered number whose only purpose in life is to describe itself.

Here is the formal definition. An autobiographical number is a number N such that the first digit of N counts how many zeroes are in N, the second digit counts how many ones are in N and so on. In our example, 1210 has 1 zero, 2 ones, 1 two and 0 threes.

Let us find all autobiographical numbers using the “zoom-in” method.

1. By definition, the autobiographies can’t have more than 10 digits. It is nice to know that these egotistical numbers can’t be too grand.
2. The sum of the digits in an autobiography equals the number of the digits. Consequently, the sum of the digits will not be more than 10.
3. The first digit is the number of zeroes. As you know, self-respecting integers do not start with a zero. Hence, the number of zeroes is not a zero.
4. Subtracting statement “c” from statement “b” above, we get a resulting statement that the sum of all the digits, except for the first one, is equal to the number of non-zero digits plus 1.
5. That means, other than the first digit, the set of all other non-zero digits consists of several ones and 1 two.
6. Furthermore, the number of ones is either 0, 1 or 2.

Now we continue zooming in in three different directions depending on the number of ones. In this blog entry, I will consider only the case in which there are no ones; I leave the other two cases to the reader.

• If the number of ones is zero, then the only non-zero non-first digit of such a number is 2.
• This 2 should be included in the autobiography; since the third digit of the number is not zero, it must be 2.
• The number has 2 twos.
• It must be 2020.

Here is the full set of autobiographical numbers: 1210, 2020, 21200, 3211000, 42101000, 521001000, 6210001000.

This is the sequence A104786 in the Online Encyclopedia of Integer Sequences (OEIS), where I first encountered the autobiographical numbers.

Autobiographical numbers are very cute numbers. But there is a problem with their name. If there is a notion of an autobiography of a number, then it would be logical to expect that there is a notion of a biography of a number. What would be the logical candidate for a biography of a number? Let us say that given a number N, its biography is another number M such that the first digit of M is the number of zeroes in N, the second digit of M is the number of ones in N and so on.

Of course, for a number to have a biography, we need to assume that none of its digit is present more than nine times. Still there are several problems with the definition of a biography.

The first problem is that if N doesn’t have zeroes, its biography starts with a zero. As numbers don’t start with 0, that biography is not a number! Furthermore, if N starts with 0, it can have a biography but N is not a number. Luckily for this article, a digit string starting with zeroes can’t be an autobiographical string, because the number of zeroes is not a zero. It is a relief that those illegitimate strings that are trying to pretend to be numbers can’t actually be autobiographical.

The second problem with biographies is that a number can have many biographies. Indeed, if a number doesn’t have nines, you can remove or add zeroes at the end of a biography to get another biography of the same number. Since mathematicians like to define things uniquely, we might consider it a problem if a number has several biographies. In real life it is possible to have many biographies of a person. So the second problem is not a big problem. I will call the shortest possible biography of a number the curriculum vitae and the longest possible biography the complete life story.

The third problem is that numbers with the same digits in different permutations have the same biographies. So in a sense a biography follows the life not of a number, but rather the set of its digits.

Suppose for now we allow a biography to start with 0. Also, let us choose the curriculum vitae — the shortest biography in case there could be several. Let us build a sequence of CVs. As an example, we start with 0. Zero’s CV is 1, one’s CV is 01, continuing that we get the following sequence: 0, 1, 01, 11, 02, 101, 12, 011, 12, 011, 12, …. You can see that the CVs’ sequence fell into a cycle in this case. I tried sequences of CVs starting with many numbers. I found that they fall into two cycles. One cycle is described above and another one is: 22, 002, 201, 111, 03, 1001, 22. Can you find another cycle or, alternatively, can you prove that all the numbers that allow the sequence of CVs converge to only these two cycles?

Let us build the sequence of complete biographies, that is, life stories, starting with 0: 0, 1000000000, 9100000000, 8100000001, 7200000010, 7110000100, 6300000100, 7101001000, 6300000100, …. We see that this sequence falls into a cycle of length two. The members of this cycle are legitimate numbers. These numbers are too shy to advertise themselves. But Alice praises Bob, because Bob praises Alice. It’s a very advantageous flattery pattern! I will call such a pair a mutually-praising pair. We’ve already seen mutually-praising strings: 12 and 001. Two other examples of number pairs thriving on each others’ compliments are, first, 130 and 1101, and second, 2210 and 11200.