Tanya Khovanova's Math Blog

I want to study patterns inside permutations. Consider a permutation of size 4: 1432. Today I am excited by ordered subset of size 3 inside this permutation. For example, I can drop the last number and look at 143. The ordering in 143 is the same as in 132, or, as a mathematician would say, 143 is order-isomorphic to 132. In my example of 1432, I have four subsets depending on which number I remove: 432 is order-isomorphic to 321, while 132, 142 and 143 are all order-isomorphic to 132.

The density of a pattern 123 in the permutation 1432 is the ratio of subsets of size 3 that are order-isomorphic to 123 to all subsets of size 3. As I already calculated, the density of 123 in 1432 is zero, while the density of 321 is 1/4, and the density of 132 is 3/4.

A permutation is called 3-symmetric if the densities of all patterns of size 3 (123, 132, 213, 231, 312, 321) are the same. The reason I love this notion, is that 3-symmetric permutations are similar to random permutations with respect to patterns of size 3.

My example permutation, 1432, is not 3-symmetric. Thinking about it, no permutation of size 4 can be 3-symmetric. The number of subsets of size 3 is four, which is not divisible by 6.

I wanted to find 3-symmetric permutations. So the size n of the permutation needs to be such that n choose 3 is divisible by 6. The numbers with this property are easy to find. The sequence starts as 1, 2, 9, 10, 18, 20, 28, 29, 36, 37, 38, 45, 46. The sequence is periodic with period 36.

Any permutation of sizes 1 or 2 is 3-symmetric as all densities are zero. Duh!

The next interesting size is 9. My student, Eric Zhang, wrote a program and found that there are two 3-symmetric permutations of size 9: 349852167 and 761258943. These numbers are so cool!. First, they are reverses of each other. This is not very surprising: if a permutations is 3-symmetric, then its reverse must also be 3-symmetric. There is another property: the permutations are rotational symmetries of each other. That is, the sum of two digits in the same place is 10. You can see that rotating a 3-symmetric permutation produces a 3-symmetric permutation.

I decided to write a program to find 3-symmetric permutations of the next size: 10. There is none. I do not trust my programming skills completely, so adjusted my program to size 9 and got the same result as Eric. I trust Eric’s programming skills, so I am pretty sure that there are no 3-symmetric permutations of size 10. Maybe there are some 3-symmetric permutations in size 18.

Let’s find 2-symmetric permutations. These are permutations with the same number of ascends and descends inversions and non-inversions. For n to be the size of such permutation n choose 2 needs to be divisible by 2. That means n has to have remainder 0 or 1 modulo 4. The first nontrivial case is n = 4. There are six 2-symmetric permutations: 1432, 2341, 2413, 3142, 3214, 4123. We can also group them into reversible pairs: 1432 and 2341, 2413 and 3142, 3214 and 4123. If we look at rotational symmetry we get different pairs: 1432 and 4123, 2341 and 3214, 2413 and 3142.

You can try to find non-trivial 4-symmetric permutations. Good luck! The smallest nontrivial size is 33. Finding 5-symmetric permutations is way easier: the smallest nontrivial size is 28. The sequence of nontrivial sizes as a function of n is: 1, 4, 9, 33, 28, 165, 54, 1029, 40832, 31752, 28680, 2588680, 2162700, and so on. My computer crashed while calculating it.

I found this puzzle on the Russian QWERTY channel.

Five people sit around a table playing Mafia. Among them are two innocent people, two Mafiosos, and one detective. The Mafia people know each other; the detective knows who each of them is; and the innocent people have no information whatsoever about anyone at the table.

During this particular game, the innocents and the detective always tell the truth, while mafia people always lie. They start by going around the circle making the following statements:

• A: I know who B is.
• B: I know who the detective is.
• C: I know who B is.
• D: I know who E is.

Who is who?

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.

My coauthor, Konstantin Knop, sent me a coin-weighing problem that is really good. Surprisingly, it is old: it first appeared in a Russian math journal, Kvant, in 1973.

Puzzle. At a trial, 14 coins were presented as material evidence. The expert tested the coins and discovered that seven of them were fake, the rest were real, and he knew exactly which coins were fake and which were real. The court only knows that counterfeit coins weigh the same, real coins weigh the same, and fake ones are lighter than real ones. The expert wants to use not more than three weighings on a balance scales without weights to prove to the court that all the counterfeit coins he found are really fake, and the rest are real. Could he do it?

A cartoon based on my script is posted on TEDEd: Can you solve the Leonardo da Vinci riddle?.

There is only one correct answer to this puzzle. Choices:

1. The correct answer is B).
2. The correct answer is C).
3. The correct answer is A).
4. The correct answer is D).

My mom died in April of 2017. I didn’t even consider flying to Russia for her funeral. April-May is my most demanding work period. We were preparing for the annual PRIMES conference. Four of the projects that I personally mentor were presented at the conference. As a head mentor, I was also helping on all the other projects. During these months, I do not have time to breath.

I felt intensely guilty missing the funeral, but I blocked my emotions and worked. I didn’t shed a tear. Come June-July, I have another busy work period running Mathroots and RSI. August is often a slow month, which I usually use to finish papers that I am writing with my students. But in August, 2017, I needed to put the papers aside and give myself time to grieve. My mood was getting darker and darker. At some point I realized that I was depressed. Surprisingly, I still didn’t shed a tear.

I had been depressed before, and I do not ever want to be in that place again. I ordered myself to stop mourning, and with some positive self-talk, I was able to get myself out of the depression. In the process I didn’t work much in August, leaving me with a huge backlog of papers: I had about 20 papers that needed my immediate attention.

When the academic year began in September, my work was more stressful than ever. On one hand I had a pile of unfinished papers, and on the other hand our programs were growing bigger and more taxing. I limped along and did my best until April of this year. Because I had more stress than ever before. Because April-May is my most intense work time, I had to cancel my social life, stop watching TV, and drop my exercise regime to be able to prepare for our annual PRIMES conference. I was so busy I completely missed the first anniversary of my mom’s death. In the year since her death I had been mourning, but I was still unable to cry. When I realized that I had forgotten this date, I felt more severe guilt than ever. I called my sister in Moscow. She told me that she had ignored the death anniversary too. She had done it on purpose. It is better to celebrate life than death, she told me, and it made me feel better.

When the PRIMES conference was over, it was clear that my work was overtaking my life. I decided to go away for a day to rethink my priorities.

I googled Googled around for a place to go, and found the Innisfree garden. The website claimed that the garden is recognized as one of the world’s ten best gardens. Sounded fitting for rethinking a life.

The Innisfree Garden is different from other gardens that I have seen. With my untrained eye, I couldn’t distinguish what was man-made and what was nature. Slowly it became clear that things that look like nature are in reality a work of genius. The human touch amplified the natural beauty of the land and transformed it into something out of this world: beautiful, peaceful, and serene.

I spent hours in the garden. When I was about to leave, my floodgates were open. I started crying. Mom, I love you; please forgive me.

Puzzle. A boy fell off of a 30 meter ladder, but didn’t get hurt. Why not?

I was very happy to hang out with my oldest coauthor, Richard Guy, at the Gathering for Gardner conference in Atlanta in April 2018. By the way, Richard Guy is 101 years old.

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.