Tanya Khovanova's Math Blog

Once John Conway showed me a cute way to enumerate Latin squares of size 4, up to the movements of the plane. It was a joint result with Alex Ryba, which is now written in a paper Kenning KenKen.

For starters, I want to remind you that a Latin square of size n is an n by n table filled with integers 1 through n, so that every row and column doesn’t have repeated integers. KenKen is a game that John Conway likes, where you need to recover a Latin square given some information about it.

Let me start by describing a particular shape of four cells that one digit can occupy in a Latin square of size 4. There are only seven different shapes. To get to the beautiful result, we need to number these seven shapes in a particular order starting from zero. The shapes are shown below.

There are 12 different Latin squares up to movements of the square and relabeling the digits. Here is how Conway and Ryba matches shapes and squares. For each Latin square, take the shapes of all four digits, remove the duplicate shape numbers and sum the leftover shape numbers. You will get a unique number from 1 to 12 that represents a particular Latin square. For example, consider the square on the picture below.

Digit 1 is shape 4, digits 2 and 4 form shape 2, and digit 3 forms shape 6. Shape 2 is used twice, and we ignore multiplicities. So we have shapes 2, 4, and 6 used. The resulting Latin square is number 2 + 4 + 6, that is 12. It is a fun exercise to try to find all the squares. For example, square 1 can only use shapes 0 and 1. But shape 1 uses exactly one corner. So the first square should use each of the digits in shape 1.

John likes finding interesting ways to remember which shape is which. You can find his and Alex’s suggestions in the paper which Alex submitted to the arxiv.

Oops! While I was writing this essay, arxiv rejected the paper.

John Conway came to the 2017 MOVES conference and told me that he wanted to talk to me about subprime fibs. The subprime Fibonacci sequence was invented by John Conway, and I wrote a paper about it. The paper, Conway’s Subprime Fibonacci Sequences, wasn’t written with John, but rather with Richard Guy and Julian Salazar, and is published in Mathematics Magazine.

I wanted to visit my friend Julia, who lives in Princeton, and this was a good opportunity to discuss the mysteries of subprime fibs with John. On my second day in Princeton, I came to the math department around 3:00 pm carrying some apples. John never goes out for lunch, as he has trouble walking, so he is always hungry by the end of his work day. Thus, each time I go visit him, I come with food. We have very different tastes in apples: unlike me, he likes his apples unwashed.

Anyway, by the time I arrived to the department, John had already left. This was somewhat unusual, so I called him. He sounded weird and not very coherent, as if he wasn’t feeling well. Considering also that he had left early, I started to worry. Unfortunately, there was a lot of background noise during our conversation and I only understood that he was at a pizza place. John walks very slowly, so he couldn’t have gone too far away from campus. I found him in the second pizza place I checked. It was Tiger’s Pizza. He told me that he felt very sleepy and tired. However, I was gratified to see how much having an interested listener gave him energy. He started telling me stories of his trip to Germany a long time ago. He had already eaten, but decided to have some more fries. As a perfect gentleman he offered me some, but I didn’t want any.

At some point he dropped a couple of fries on the floor. He tried to reach them and I jumped to help. That was a mistake. I actually know that he likes proving to me and to himself that he can do stuff independently. He accepts my help when I am subtle about it, or when it is unavoidable. Anyway, he looked at me angrily and I backed off. He picked up his fries from the floor and ate them.

I liked his T-shirt and tried to take a picture of it. As you can see, I am no photographer. The T-shirt shows a test question: Name the triangles. Then it features three triangles: an equilateral, isosceles, and right. It also provides someone’s answers to this naming test: Geoffrey, Frederick, Eugene.

John asked me if I am more scared of Donald Trump or Kim Jong Un. We agreed that Trump is scarier. At this time he seemed his usual self.

I offered John a ride home, as I do whenever I visit him. He was very glad as he felt very tired. He started to get up. This time, I remembered not to try to help. He couldn’t get up, I waited. He tried to push his weight off the table top, but the table was wobbly. I leaned on the table, as if to rest. We often play this sort of game in which he welcomes my help as long as we both pretend that I’m not helping.

My car was a block away and he wanted to walk the block. But after making two steps out of the pizzeria he changed his mind and asked me to bring the car to him. This was the first time ever. This visit he was so much worse than ever before.

On the drive to his place, he gave me a puzzle:

John’s puzzle. Given a Mebius strip with a hole, how do you embed it in 3-D so that the two circular borders of the surface are equivalent?

I dropped him off at his house and offered to walk him to the door. He refused. I sat in my car and watched him walking very slowly along his path. I had this sinking feeling in my gut that I was seeing John for the last time. I drove away, once he disappeared behind his door.

On my way back to Boston I visited my friend Vitaly in East Brunswick, and the next day my high school friend Olga in Edison. In Edison, my car started beeping and I panicked. I was far away from home, and didn’t want to be stuck in NJ. I started to look for the source of the sound. It was John’s phone. As always, my gut feeling deceived me: I had to go back to Princeton.

I drove back to John’s apartment. His door was unlocked and I entered. He was resting in bed. He was greatly annoyed at being disturbed. I explained the reason, and gave him his phone. He took the phone and said, “Off you go.” I had this sinking feeling in my gut that these words would be the last words that I would hear from John.

Every time I visit Princeton, or otherwise am in the same city as my friend John Conway, I invite him for lunch or dinner. I have this rule for myself: I invite, I pay. If we are in the same place for several meals we alternate paying. Once John Conway complained that our tradition is not fair to me. From time to time we have an odd number of meals per visit and I end up paying more. I do not trust my memory, so I prefer simplicity. I resisted any change to our tradition. We broke the tradition only once, but that is a story for another day.

Let’s discuss the mathematical way of paying for meals. Many people suggest using the Thue-Morse sequence instead of the alternating sequence of taking turns. When you alternate, you use the sequence ABABAB…. If this is the order of paying for things, the sequence gives advantage to the second person. So the suggestion is to take turns taking turns: ABBAABBAABBA…. If you are a nerd like me, you wouldn’t stop here. This new rule can also give a potential advantage to one person, so we should take turns taking turns taking turns. Continuing this to infinity we get the Thue-Morse sequence: ABBABAABBAABABBA… The next 2ⁿ letters are generated from the first 2ⁿ by swapping A and B. Some even call this sequence a fair-share sequence.

Should I go ahead and implement this sequence each time I cross paths with John Conway? Actually, the fairness of this sequence is overrated. I probably have 2 or 3 meals with John per trip. If I pay first every time, this sequence will give me an advantage. It only makes sense to use it if there is a very long stretch of meals. This could happen, for example, if we end up living in the same city. But in this case, the alternating sequence is not so bad either, and is much simpler.

Many people suggest another use for this sequence. Suppose you are divorcing and dividing a huge pile of your possessions. A wrong way to do it is to take turns. First Alice choses a piece she wants, then Bob, then Alice, and so on. Alice has the advantage as the first person to choose. An alternative suggestion I hear in different places, for example from standupmaths, is to use the Thue-Morse sequence. I don’t like this suggestion either. If Alice and Bob value their stuff differently, there is a better algorithm, called the Knaster inheritance procedure, that allows each of them to think they are getting more than a half. If both of them have the same value for each piece, then the Thue-Morse sequence might not be good either. Suppose one of the pieces they are dividing is worth more than everything else put together. Then the only reasonable way to take turns is ABBBB….

The beauty of the Thue-Morse sequence is that it works very well if there are a lot of items and their consecutive prices form a power function of a small degree k, such as a square or a cube function. After 2^k+1 turns made according to this sequence, Alice and Bob will have a tie. You might think that if the sequence of prices doesn’t grow very fast, then using the Thue-Morse sequence is okay.

Not so fast. Here is the sequence of prices that I specifically constructed for this purpose: 5,4,4,4,3,3,3,2,2,2,2,1,1,0,0,0. The rule is: every time a turn in the Thue-Morse sequence switches from A to B, the value goes down by 1. Alice gets an extra 1 every time she is in the odd position. This is exactly half of her turns. That is every four turns, she gets an extra 1.

If the prices grow faster than a power, then the sequence doesn’t work either. Suppose your pieces have values that form a Fibonacci sequence. Take a look at what happens after seven turns. Alice will have pieces priced F_n + F_n-3 + F_n-5 + F_n-6. Bob will have F_n-1 + F_n-2 + F_n-4. We see that Alice gets more by F_n-3. This value is bigger than the value of all the leftovers together.

I suggest a different way to divide the Fibonacci-priced possessions. If Alice takes the first piece, then Bob should take two next pieces to tie with Alice. So the sequence might be ABBABBABB…. I can combine this idea with flipping turns. So we start with a triple ABB, then switch to BAA. After that we can continue and flip the whole thing: ABBBAABAAABB. Then we flip the whole thing again. And again and again. At the end we get a sequence that I decided to call the Fibonacci fair-share sequence.

I leave you with an exercise. Describe the Tribonacci fair-share sequence.

John Conway told me a story about the book Winning Ways for Your Mathematical Plays that he wrote jointly with Elwyn Berlekamp and Richard Guy. The book includes the birthdays of each of the book’s three authors. The book has short author bios, each of which mentions that author’s birthday. But in addition, each birthday is hidden inside the book.

Elwyn Berlekamp was born on September 6, 1940, and this date is pictured on a tombstone on page 318 of Volume 2. That chapter is about suiciding moves.

John Conway was born on December 26, 1937. The Doomsday algorithm to calculate the day of the week for a given date is discussed on page 903 of Volume 4. Boxing Day in 1937 is chosen as an example. Boxing Day is a British holiday that originated when wealthy people gave gift boxes to servants the day after Christmas. John Conway was born on Boxing Day. Hidden behind this calculation that it was a Sunday, is the fact that it was Conway’s day of birth.

Richard Guy was born on September 30, 1916. He often uses his initials RKG for Richard Kenneth Guy. Maybe because of that he got the nickname Archangel. If you look into the index pages of Volumes 3 and 4, you will find an entry for Archangel that refers to pages 9, 30, 1916. Not only are there no mentions of “Archangel ” on pages 9 and 30, the book only has 1004 pages.

The trio of Berlecamp, Conway, and Guy will be the topic of an upcoming MOVES (Mathematics Of Various Entertaining Subjects) conference at the Museum of Mathematics.

The last time I visited John Horton Conway, he showed me a book, Genius At Play: The Curious Mind of John Horton Conway by Siobhan Roberts. It had nothing to do with him wanting to brag about the book. Nothing, nothing at all.

He just wanted to show me a picture from the book. While he was browsing this book about himself, I took a photo of him (featured on the left). The picture he was looking for was on page 314. I am reproducing it here (Photo by Michael A. Stecker, courtesy of Stephen D. Miller).

When we finally found the picture, he asked me how many tennis balls were in it. I smelled a trick question right away and didn’t bite. I shrugged. It appears that one of the balls at the far corner at the base of the pyramid had rolled away. So there was one less ball than I would have calculated. So, how many balls are there?

John Conway likes playing with the Fibonacci sequence. He invented many new sequences using the following trick. The next number in the sequence is the sum of the two previous number adjusted in some way. Free Fibonacci sequences were invented this way. Here is the recurrence for an n-free Fibonacci sequence: the next number in the sequence is the sum of the previous two numbers divided by the highest possible power of n.

Let us calculate a 2-free Fibonacci sequence starting with 5 and 4: 5, 4, 9, 13, 11, 3, 7, 5, 3, 1, 1, 1, …. I leave it to the reader to show that any 2-free sequence ends with a cycle of length one.

Let us try a 3-free Fibonacci sequence starting with 5 and 6: 5, 6, 11, 17, 28, 5, 11, 16, 1, 17, 2, 19, 7, 26, 11, 37, 16, 53, 23, 76, 11, 29, 40, 23, 7, 10, 17, 1, 2, 1, 1, 2, and so on. We are now in the cycle of length 3. Is this always the case? Not quite. If there is a 1-1-2 cycle there should be a 2-2-4 cycle, or any cycle k–k-2k, where k is coprime with 3. But the question remains: does it always end in a cycle of length 3?

I published a paper Free Fibonacci Sequences with Brandon Avila. We conjecture that a 3-free Fibonacci sequence always ends in a cycle and support this conjecture with a probabilistic argument. We were amused by how the behavior changes when we move to 4-free Fibonacci sequences. It seems that in this case sequences never cycle. We were even more amused when we moved to 5-free Fibonacci sequences and discovered that the behavior changes again.

When n equals 5 there are some sequences that cycle. Can you find the cycles? There are also sequences that grow indefinitely and we do not need a probabilistic argument to prove that. Consider Lucas numbers: 2, 1, 3, 4, 7, 11, and so on. This is a Fibonacci-like sequence that never has a term divisible by 5. Thus Lucas numbers form a 5-free Fibonacci sequence. We made a probabilistic argument that most of the starting terms converge eventually to a Lucas-like sequence that grows indefinitely because there are no terms divisible by 5.

What happens for larger n? We didn’t manage to find any cycles there. Would you like to try?

Each time I see John Conway he teaches me something new. At the Gathering for Gardner he decided to quiz me on how well I know a regular six-sided die. I said with some pride that the opposite sides sum up to 7. He said, “This is the first level of knowledge.” So much for my pride. I immediately realized that the next level would be to know how all the numbers are located relative to each other. I vaguely remembered that in the corner where 1, 2, and 3 meet, the numbers 1, 2, and 3 are arranged in counter-clockwise order.

Here’s how John taught me to remember every corner. There are two types of corners. In the first type numbers form an arithmetic progression. John calls such numbers counters. He chose that name so that it would be easy to remember that counters are arranged in counter-clockwise order. The other numbers he calls chaos: their increasing sequence goes clockwise.

Once I grasped that, I relaxed thinking that now I know dice. “What about the third level?” he asked. “What third level?” “Now that you know which number goes on which side, you need to know how the dots are arranged.” Luckily, there are only three sides on which the dots are not placed with rotational symmetry: 2, 3, and 6. And they all meet in a corner, which John calls the home corner. The rule is that the diagonals formed by the dots on the sides with 2, 3, and 6, meet in the home corner. You might argue that 6 doesn’t have a diagonal. But if you look at 6, you can always connect the dots to form the letters N or Z, depending on the orientation of the die. When you lay the letter N on its side, it becomes the letter Z. Thus they define the same diagonal. This diagonal has to meet the diagonals from 2 and 3 in the corner.

When I came home from the conference I picked up a die and checked that the rules work. There are 8 corners. It is enough to remember one corner of numbers to recover the other numbers by using the opposite sum rule. But it is nice to have a simple rule that allows us to bypass the calculation. Four of the corners have numbers in arithmetic progression: 1:2:3, 1:3:5, 2:4:6, and 4:5:6. They are counters and they are arranged counter-clockwise. The other four corners are: 1:2:4, 1:4:5, 2:3:6, and 3:5:6, and they are arranged clockwise.

I wanted to provide a picture of a die for this post and went online to see if I could grab one. Many of the graphic images of dice, as opposed to photographs, were arranged incorrectly. Clearly these visual artists did not study dice with John Conway.

Then I decided to check my own collection of dice. Most of them are correct. The ones that are incorrect look less professional. Here is the picture. The ones on the right are correct.

The Fibonacci sequence is all about addition, right? Indeed, every element F_n of the Fibonacci sequence is the sum of the two previous elements: F_n = F_n-1 + F_n-2. Looking closer we see that the Fibonacci sequence grows like a geometric progression φⁿ, where φ is the golden ratio. In addition, the Fibonacci sequence is a divisibility sequence. Namely, if m divides n, then F_m divides F_n.

My point: we define the sequence through addition, and then multiplication magically appears by itself. What would happen if we tweak the rule and combine addition and multiplication there?

John Conway did just that: namely, he invented a new sequence, or more precisely a series of sequences depending on the pair of the starting numbers. The sequences are called Conway’s subprime Fibonacci sequences. The rule is: the next term is the sum of the two previous terms, and, if the sum is composite, it is divided by its least prime factor.

Let me illustrate what is going on. First we start with two integers. Let’s take 1 and 1 as in the Fibonacci sequence. Then the next term is 2, and because it is prime and we do not divide by anything. The next two terms are 3 and 5. After that the sum of two terms is 8, which is now composite and it is divided by 2. So the sequence goes: 1, 1, 2, 3, 5, 4, 3, 7, 5, 6, 11 and so on.

The subprime Fibonacci sequences excite me very much. Not only does adding some multiplication to the rule make sense to me, but also, the sequences are fun to play with. I got so excited that I even coauthored a paper about these sequences titled, not surprisingly, Conway’s Subprime Fibonacci Sequences. The paper is written jointly with Richard K. Guy and Julian Salazar, and is available at the arXiv:1207.5099.

We can start a subprime Fibonacci sequence with any two positive numbers. You can see that such a sequence doesn’t grow fast, because we divide the terms too often. We present a heuristic argument in the paper that allows us to conjecture that no subprime Fibonacci sequence grows indefinitely, but they all start cycling. The conjecture is not proven and I dare you to try.

Meanwhile, the sequences are a lot of fun and I suggest a couple of exercises for you:

• Prove that there are no cycles of length two or three.
• Prove that the maximum number in a non-trivial cycle is prime.
• Prove that the smallest number in a non-trivial cycle is more than one. You can prove that it is more than 6 for extra credit.

By the way, a trivial cycle is the boring thing that happens if we start a sequence with two identical numbers n bigger than one: n, n, n, n, ….

Have fun.

by Sergei Bernstein, Tanya Khovanova and Alexey Radul

Here is a game that John Conway popularizes. It is called “Finchley Central,” which is a station of the London Underground. The game goes as follows. Alice and Bob take turns naming London Underground stations, in any order. The first person to say “Finchley Central” wins.

Alice, who starts, can just name the station. But then Bob will give her a look. It is not fun to win a game on the first turn. To avoid appearing rude, Alice will not start with “Finchley Central.” It would be impolite of Bob to take advantage of Alice’s generosity, so he also won’t say “Finchley Central.” The game might continue like this for a while.

The game has a hidden agenda: winning it after 10 turns will supply many more bragging rights than winning it right away would. We can make this hidden agenda explicit by assigning a value to the honor of continuing the game. For example, suppose every time Alice (or Bob) says a station, she puts one dollar into the pile. The person who says “Finchley Central” first takes all the money from the pile. The implicit goal of the game becomes explicit: you want to say “Finchley Central” right before your opponent says it.

By the way, Finchley Central is not actually a particularly central station — it is the station between Finchley East and Finchley West, serving the relatively small place called Finchley; and is not even under ground. It has the distinction of being one of the oldest still-standing pieces of London Underground physical plant, because plans to rebuild it were interrupted on account of World War II and never resumed. It also has the distinction of having served the home of the guy (an employee of the Underground system) who had the brilliant idea that since the Underground was, indeed, mostly under ground, the right way to map it was topologically, rather than geographically.

Here is another way to model the game. Alice writes an odd number on a piece of paper, and Bob writes an even number. When they compare, the person who wrote a smaller number wins that number of dollars. This version loses the psychological aspect. When you take turns, it is to your advantage to read the non-verbal signs of your opponent to see when s/he is getting ready to drop the bomb.

People play this game in real life. Here are Alice and Bob looking at the last piece of a mouth-watering Tiramisu:

• Alice: You look like you want this piece of cake. Why don’t you take it?
• Bob: You seem to like it too. Please, go ahead.
• Alice: I am fine. You take it.
• Bob: You have it; I insist.

At this point Alice wins with some extra brownie points for being polite.

We can model the honor points differently. We can say you will be the most proud of the game if you name the station write before you opponent is about to do so. Then the model is: everyone writes down their next move; if your move is Finchley Central when your opponent’s next move was going to be Finchley Central, then you win.

Here we suggest another game that we call “Reverse Finchley Central.” Alice and Bob name London Underground stations in turns and the person who names “Finchley Central” first loses. This game can continue until all the stations are exhausted, if the players are forbidden to repeat them, or it can continue indefinitely otherwise. But this is quite tiresome. The hidden agenda would be to not waste too much time. Clearly the person who values time less will win.

But let us model this game. We want to fix the value of winning. Let us set aside ten dollars for the winner. On their turn, each player puts one dollar into the pile, and as soon as one of the players says “Finchley Central,” the other one wins and takes the ten dollars. The pile goes to charity. Alternatively, Alice and Bob can each write a number. The person with the larger number wins the prize, while both have to pay the smaller number to charity.

We play this game with our parents. They nag us to do the dishes. We resist. Then they give up and do the dishes themselves. They lose, but we all pay with our nerves for nagging or being nagged at. Later our parents get their revenge when we have children of our own.

John Conway taught me how to tell time at night. But first I need to explain the notions of the “time in the sky” and the “time in the year.”

The clock in the sky. Look at Polaris and treat it as the center of a clock. The up direction corresponds to 12:00. Now we need to find a hand. If you find Polaris the way I do, first you locate the Big Dipper. Then you draw a line through the two stars that are furthest away from the Big Dipper’s handle. The line passes through Polaris and is your “hour” hand. Now you can read the time in the sky.

The hand of the clock in the sky makes a full rotation in approximately 24 hours. So if you stare at the sky for a long time, you can calculate the time you spent staring. Keep in mind that the hand in the sky clock is twice as slow as the hour hand, and it turns counter-clockwise. So to figure out how long you’re looking into the sky, take the sky-time when you start staring, subtract the sky-time when you stop staring and multiply the result by 2.

To calculate the absolute time, we need to adjust for the day in the year.

The clock in the year. A year has twelve months and a clock has twelve hours. How convenient. You can treat each month as one hour. In addition as a month has about 30 days and an hour has exactly 60 minutes, we should count a day as two minutes. Thus, January 25 is 1:50.

Fact: on March 7^th at midnight the clock in the sky shows 12:00. March 7^th corresponds to 3:15. So to calculate the solar time you need to add up the time in the sky and the time in the year and multiply it by 2. Then subtracting the result from 6:30, which is twice 3:15, you get the solar time.

You are almost ready. You might need to adjust for daylight savings time or for peculiarities of your time zone.

This time formula is not very precise. But if you are looking into the sky and you do not have your watch or cell phone with you, you probably do not need to know the time precisely.