Tanya Khovanova's Math Blog


This blog has a modern version at http://blog.tanyakhovanova.com/, where you can leave comments. This page contains the copies of recent blog entries. The older copies are here:


Content

If you enjoy this page you can support it by shopping at amazon through this link. Thank you.


My Virtual Stars

I like rewarding my students. Before covid, I used to give them star stickers for good ideas. When I started to teach remotely, I wondered what I should do instead. I could tell them that they had won a star, but it felt too weak. The next idea was to show them a star and tell them that it belonged to them. But that still felt insufficient. Then I had an epiphany. I would say to them they earned a star, show it to them, and stick it to my face. So they, and all the other students, would see it for the rest of the class. The photo shows how I looked at the end of a successful lesson.

Tanya getting a prize at a linguistics Olympiad

Another picture shows what my MathRoots students posted on our Discord channel.

Students about Tanya's stars

Now that I am back teaching in person, my students asked me to continue sticking their stars to my face. Sometimes I forget about the stars and, after my class, wander around MIT star-covered.


The Top Fifty Largest Numbers that Start a Sequence in the OEIS

My son, Alexey Radul, wrote a program that finds the largest numbers to start a sequence in the Online Encyclopedia of Integer Sequences (OEIS). To my surprise, the top ten are all numbers consisting of ones only. The largest number is 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111: a number with 128 ones. The sequence is A095646: a(n) is 128 written in base n. It starts with base 1, or more precisely, the unary expansion, which indeed requires 128 ones to express the number 128.

I decided to expand my top list to 50. Again, most of the numbers are bunches of ones: 48 out of the top 50 numbers are unary expansions of numbers 81 through 128. There are two more numbers in the top 50 that are different and belong to awesome sequences.

The first sequence is sequence A033290: Ten consecutive primes in arithmetic progression. It starts with the number 100996972469714247637786655587969840329509324689190041803603417758904341703348882159067229719, which has 93 digits. This number takes 37th place on my list.

The second sequence is sequence A291042: One powerful arithmetic progression with a nontrivial difference and maximal length. The sequence corresponds to a cool puzzle that appeared in the American Mathematical Monthly in 2000. The question was, "What is the length of the longest non-constant arithmetic progression of integers with the property that the kth term is a perfect kth power?" The answer is 5. John P. Robertson proved that such progression can't have 6 terms and provided an example of a sequence with 5 terms, which is the sequence in the OEIS.

Here is how to construct this sequence. Start with an arithmetic progression 1, 9, 17, 25, 33, and multiply each term by 32453011241720: the result is also an arithmetic progression. The first term is trivially a first power. The second term is 32653011241720 = (31351511121710)2 and a square. The third term is 32453011241721 = (38510118177)3 and a cube. The fourth term is 32453211241720 = (3658116175)3 and a fourth power. The fifth term is 32553011251720 = (3556115174)5 and a fifth power.

The sequence starts with the number 10529630094750052867957659797284314695762718513641400204044879414141178131103515625. It has 83 digits, and it takes 48th place on my list.


Joint-Groups Sudoku

My students (Matvey Borodin, Eric Chen, Aidan Duncan, Boyan Litchev, Jiahe Liu, Veronika Moroz, Matthew Qian, Rohith Raghavan, Garima Rastogi, Michael Voigt) and I recently wrote a paper connecting the stable marriage problem and Sudoku. I just blogged about it. By the way, my students are in grades 7-9.

On the way, we invented a new type of Sudoku, which we call joint-groups Sudoku. This type is in contrast to a famous type of Sudoku, called disjoint-groups Sudoku. In a disjoint-groups Sudoku, in a particular place in a 3 by 3 box, all the digits are distinct across all the boxes. For example, the top-left corners of nine boxes have all the digits 1 thought 9. This creates nine additional disconnected regions (depending on the placements inside a 3 by 3 box) to add to columns, rows, and boxes that have to contain distinct digits.

For our new type, we wanted the digits in a particular place in each box, instead of being different, to be the same as much as possible. How much of sameness is possible? The first row contains three top-left corners. Thus, by Sudoku rules, these top-left corners have to be distinct. Thus, the top-left corners in all nine boxes have to contain at least three distinct digits. So here is the rule for the joint-groups Sudoku: the nine digits in a particular place in a 3 by 3 box contain not more than three distinct digits. It is easy to see that it means they contain exactly 3 distinct digits, each of them three times.

Here are two Sudoku puzzles from our paper. Each puzzle, when completed, forms a joint-groups Sudoku.

Joint-groups Sudoku

The Stable Marriage Problem and Sudoku

As you may know, I run PRIMES STEP, a local program where we do mathematical research with students in grades 6-9. Last academic year, we looked at the stable marriage problem and discovered its connection to Sudoku. Our paper The Stable Matching Problem and Sudoku (written jointly with Matvey Borodin, Eric Chen, Aidan Duncan, Boyan Litchev, Jiahe Liu, Veronika Moroz, Matthew Qian, Rohith Raghavan, Garima Rastogi, Michael Voigt) is now available at the arxiv.

Consider 3 men and 3 women who want to be married to each other in heterosexual couples. They rank each other without ties. The resulting 6 permutations of numbers 1, 2, and 3 that describe the six rankings are called the preference profile of this group of people. A matching is unstable if two people would be happier to run away together than to marry into the assigned couples. The two potential runaways are called a rogue couple. A matching is called stable if no rogue couple exists. The Gale-Shapley algorithm, invented by Gale and Shapley, finds a stable matching for any preference profile, implying that stable matching is always possible.

We discovered that preference profiles form a natural bijection with ways to place one digit into a Sudoku grid. So we wrote a paper describing the stable marriage, rogue couples, the Gale-Shapley algorithm, soulmates, and such in terms of Sudoku.

Oops, I forgot to explain who the soulmates are. We invented this term to describe two people who rank each other first. Though it is possible to have several stable matchings for the same preference profile if the soulmates exist, they must always be matched together.

We also invented a new Sudoku type, which I will explain next time.


What's in the Name? Solution

I recently posted my puzzle designed for the MoMath meet-up.

What's in the Name?

Now it is time for the solution.

The solvers might recognize some sequences and numbers. For example, numbers 6, 28, and 496 are famous perfect numbers. Otherwise, the solvers are expected to Google the numbers and the pieces of the sequences with or without X. The best resource for finding the sequences is the Online Encyclopedia of Integer Sequence.

The first “AHA!” happens when the solvers notice that the sequences’ names are in alphabetical order. The order serves as a confirmation of the correctness of the names. It also helps in figuring out the rest of the sequences’ names. The alphabetical order in such types of puzzles hints that the real order is hidden somewhere else. It also emphasizes that the names might be important. The sequences names in order are:

The second “AHA!” moment happens when the solvers realize that the Xs all have different indices. The indices serve as the final order, which in this case is the following:

The third “AHA!” moment happens when the solvers realize that the number of terms is different in different sequences. It would have been easy to make the number of terms the same. This means that the number of terms has some significance. In fact, the number of terms in each sequence matches the length of the name of the sequence. The solvers then can pick the letter from each of the names corresponding to X. When placed in order, the answer reads: NUMBERS.

The answer is related to the puzzle in two ways:

  1. The puzzle is about numbers.
  2. The sequences’ names do actually need the second word: Lucas numbers, composite numbers, and so on.

The advantage of this puzzle for zoomed group events is that the big part of the job — figuring out the sequences — is parallelizable. Additionally, it has three “AHA!” moments, which means different people can contribute to a breakthrough. The puzzle also has some redundancy in it:

  1. Due to the redundancy of the English language, it is possible to solve this puzzle without figuring out the names of all the sequences.
  2. If the solvers can’t figure out the order, they can anagram the letters to get to the answer.
  3. If the solvers do not realize that they have to use the letter indexed by the X, there is another way to see the answer: read the diagonal when the sequences’ names are in order.

1 is the Only Square-free Square

How can a square be square-free? In order for square-freeness to be interesting, it must be, and is, defined in terms of divisibility by non-trivial squares. So to create this particular mathematical oxymoron, one just needs a trivial square, namely 1.

I collect exciting properties of integers on my Number Gossip website. Did you know that forty is the only number whose letters appear in alphabetical order when written in English? Or that the largest amount of money one can have in US coins without being able to make change for a dollar is 119 cents?

Recently I wrote about a weird occasion that motivated me to search for new properties. Here is a sample of some amusing new updates.


What's in the Name?

This is the puzzle I designed for yesterday's event at the Museum of Mathematics. This puzzle is without instructions — figuring out what needs to be done is part of the fun. Solvers are allowed to use the Internet and any available tools. The answer to this puzzle is a word.


Number Gossip on Steroids

I've been too busy lately, so I stopped checking my Number Gossip website. Luckily, my website has fans. So one of them, Neil, notified me that my website was hijacked, and instead of describing properties of numbers, was selling steroids. I emailed Dreamhost, my hosting provider. They requested proof that I owned the domain. Why didn't they request proof from the people selling steroids? Or were they selling steroids themselves?

I fixed my steroid issue and since I was thinking about it anyway, I decided to update Number Gossip. I ended up spending tons of time on it — I had ten years of emails with suggestions for new properties, and I went through all of them and added the interesting ones. For example, Joshua Gray emailed me a cute property of 1331 mentioned on Wikipedia: 1331 was said to be the only cube of the form x2 + x − 1. I didn't see how to prove it, so I posted it as a question on mathoverflow. It turns out that 1331 is actually not the only cube of this form. There are three of them: −1 (for x = 0 or −1), 1 (for x = 1 or −2), and 1331 (for x = 36 or −37). So 1331 is the only non-trivial cube with this property. I had to fix Wikipedia. By the way, did you notice a symmetry? Plugging in x and −x − 1 into the quadratic produces the same value.

After processing all the emails related to Number Gossip, I got excited, so I continued working on it and added tons of new unique properties. Some of them I invented myself, some more were inspired by sequences in the OEIS database. I now have a collection of my new favorite unique properties, which I will post soon.


Continue the Sequence: 742, ...

This is the sequence of numbers n such that 3 times the reversal of n plus 1 is the number itself. In other words, n = 3*reversal(n)+1. For example, 742 = 3*247+1. In fact, 742 is the smallest number with this property. How does this sequence continue, and why?


I am Hooked on Star Battles

I recently published Sergei Bernstein's awesome Star Battle called Swiss Cheese. Another lovely Star Battle from him is called Hooks. You can play it online at puzz.link.

Sergei's Star Battle

Swiss Cheese Star Battle

Star Battle is one of my favorite puzzle types. The rules are simple: put two stars in each row, column, and bold region (one star per cell). In addition, stars cannot be neighbors, even diagonally.

My son, Sergei Bernstein, recently designed a Star Battle with a beautiful solve path. This is my favorite Star Battle so far. I like its title too: Swiss Cheese.

Swiss Cheese Star Battle

You can also solve it at the puzz.link Star Battle player.


Our Familect Story

A familect is a portmanteau word formed by squashing together two words: family and dialect. It means words that a family uses that are not a part of a standard vocabulary. This story is about two words that my son Sergei invented, and twenty years later, my family still uses them.

As you might know, I was married three times, and I have two sons, from two different fathers. These fathers were also married several times and had other children. My two sons are half-brothers, and they also have half-siblings through their fathers. Thus a half-sister of a half-brother became a quarter-sister. Inventing this term was quite logical for a son of two mathematicians.

As you can imagine, our family tree is complicated. One day Sergei pointed out that our tree doesn't look like a standard tree and called it a family bush.


A Splashy Math Problem

A problem from the 2021 Moscow Math Olympiad went viral on Russian math channels. The author is Dmitry Krekov.

Problem. Does there exist a number A so that for any natural number n, there exists a square of a natural number that differs from the ceiling of An by 2?


I Miss John Conway

Yesterday I stumbled upon a picture of John Conway I completely forgot I had: it was saved in a wrong folder. The photo was taken at the MOVES conference in 2015. There is a third person in the original shot, but I do not remember her. I decided to cut her out as I didn't know how to contact her for permission to post this photo.

Conway at MOVES conference 2015.

The Anniversary Coin

Konstantin Knop, the world's top authority on coin-weighing puzzles, suggested the following problem for the 2019 Russian Math Olympiad.

Puzzle. Eight out of sixteen coins are heavier than the rest and weigh 11 grams each. The other eight coins weigh 10 grams each. We do not know which coin is which, but one coin is conspicuously marked as an "Anniversary" coin. Can you figure out whether the Anniversary coin is heavier or lighter using a balance scale at most three times?

Discover the Rule

Found the following cute puzzle on Facebook.

Puzzle. Discover the rule governing the following sequence to find the next term of the sequence: 8, 3, 4, 9, 3, 9, 8, 2, 4, 3.

Build an All-red Cube

This is one of my favorite problems given at the 2017 Moscow Olympiad to grades 6 and 7. It was suggested by one of my favorite problem writers: Alexander Shapovalov.

Problem. We are given eight unit cubes. The third of the total number of their faces are blue, and the rest are red. We build a large cube out of these cubes so that exactly the third of the unit cube's visible faces are red. Prove that you can use these cubes to build a large cube whose faces are entirely red.

Penney's Game and Groups

For the last year, I've been obsessed with Penney's game. In this game, Alice picks a string of coin tosses, say HHH for three heads. After that, Bob picks his string of tosses of the same lengths, say HTH. Then they toss a fair coin. The person whose string shows up first wins. For example, if the tosses are THTTHHH, then Alice wins after the seventh toss. For these particular choices, Bob wins with probability 3/5.

With my PRIMES student, Sean Li, we looked at this game and asked a different question. Suppose Alice picks a pattern of three tosses in a row that are the same. Suppose after that, Bob chooses a pattern of three alternating tosses. Then they toss a fair coin. Alice is hoping for HHH or TTT, while Bob is hoping for HTH or THT. The person whose pattern shows up first wins. For example, if the tosses are THTTHHH, then Bob wins after the third toss. For these particular choices, Bob wins with probability 1/2.

In this example, what actually happens. We assume that the group of two elements acts on the alphabet of two letters. The group's non-identity element swaps letters H and T. We assume that two strings are equivalent if they belong to the same equivalency class under the group action. We call such an equivalency class a pattern.

In the new game we invented, we have an alphabet of any size and any group acting on the alphabet. Then Alice and Bob pick their patterns. After that, they play the Penney's game on these patterns. The answers to all the relevant questions are in our paper, The Penney's Game with Group Action, posted at the math.CO arxiv 2009.06080.


Confirming the Labels of Coins in One Weighing

I wrote a paper Confirming the Labels of Coins in One Weighing together with my PRIMES STEP students Isha Agarwal, Paul Braverman, Patrick Chen, William Du, Kaylee Ji, Akhil Kammila, Shane Lee, Alicia Li, Anish Mudide, Jeffrey Shi, Maya Smith, and Isabel Tu. The paper is available at math.HO arxiv:2006.16797. Below my students describe what happens in the paper in their own words.

Tragedy has struck in an iCOINic land known as COINnecticut. One day, while everyone was minding their own business, the vault door of the bank was found to have been forcefully opened. COINcerns spread amongst the COINmoners that someone had tampered with their n sacred COINtainers of coins! The COINtainers are labeled with the integers 1 through n, which usually describe the weight of each of the countless coins inside that corresponding COINtainer. For example, the COINtainer labeled 1 should only COINtain coins that weigh 1 gram, the COINtainer labeled 2 should only COINtain coins that weigh 2 gram, and so on, you get the COINcept.

The acCOINtants COINclude that someone may have switched around the labels on the COINtainers. To resolve this COINplication, aka to check if the labels have been tampered with, they bought a balance scale for a microsCOINpic amount of money. However, they can only use the scale to COINduct one weighing as the angry COINmoners are impatient and wish to withdraw their money ASAP.

The COINfused acCOINtants COINvinced 11 COINspicuous students from Boston's COINmunity to help them. With their COINbined efforts, they COINcluded that indeed, no matter how many COINtainers there are, their labels can be COINfirmed as correct or incorrect with just one weighing! Unfortunately, sometimes, such a weighing requires the use of many coins or coins with a large COINbined weight, which could potentially break the scale. Seeing this COINundrum, the students wished to be eCOINomical and find the least amount of coins or weight they need to place on the scale.

The acCOINtants and the 11 students COINtinued examining the nature of these weighings and discovered patterns that occur within them. They COINfined their research to special weighings they called downhill. They COINfirmed the effectiveness of such weighings to solve the problem at hand. The students estimated the weight and the number of coins, thus COINpleting their task.


The Blended Game

My PRIMES STEP students invented several variations of Penney's game. We posted a paper about these new games at math.HO arxiv:2006.13002.

In Penney's game, Alice selects a string of coin-flip outcomes of length n. Then Bob selects another string of outcomes of the same length. For example, Alice chooses HHT, and Bob chooses THH. Then a fair coin is tossed until Alice's or Bob's string appears. The player whose string appears first wins. In our example, Bob has a greater probability of winning, namely, 3/4. If the first two flips are HH, then Alice wins; otherwise, Bob wins.

The reader can check that HHT beats HTT with 2 to 1 odds. Thus, the game contains a non-transitive cycle it is famous for: THH beats HHT beats HTT beats TTH beats THH.

I already wrote about the No-Flippancy game that my students invented. It starts with Alice and Bob choosing different strings of tosses of the same length.

However, in the No-Flippancy game, they don't flip a coin but select a flip outcome deterministically according to the following rule: Let in be the maximal length of a suffix in the sequence of "flips" that coincides with a prefix of the current player's string. The player then selects the element of their string with index i + 1 as the next "flip." Alice goes first, and whoever's string appears first in the sequence of choices wins.

My favorite game among the invented games is the Blended game, which mixes the No-Flippancy game and Penney's game.

In the game, they sometimes flip a coin and sometimes don't. Alice and Bob choose their strings as in Penney's game and the No-Flippancy game. Before each coin flip, they decide what they want by the rule of the No-Flippancy game above. If they want the same outcome, they get it without flipping a coin. If they want different outcomes, they flip a coin. Whoever's string appears first in the sequence of `flips' wins.

For example, suppose Alice selects HHT, and Bob selects THH. Then Alice wants H and Bob wants T, so they flip a coin. If the flip is T, then they both want Hs, and Bob wins. If the first flip is H, they want different things again. I leave it to the reader to see that Bob wins with probability 3/4. For this particular choice of strings, the odds are the same as in Penney's game, but they are not always the same.

This game has a lot of interesting properties. For example, similar to Penney's game, it has a non-transitive cycle of choices. Surprisingly, the cycle is of length 6: THH beats HHT beats THT beats HTT beats TTH beast HTH beat THH.


Monetizing My Blog

I spend a lot of time working on my blog, and I used to think it would be nice to get some money out of it.

Years ago I got two emails from different ad agencies at the same time. They wanted to place ads at particular essays for $50 a year. I decided to give them a try.

My first correspondent wanted a link on my "Does Alcohol in Teens Lead to Adult Woes?" essay, connecting to a website offering help to alcoholics. I agreed. But when I read the actual text, I couldn't stop laughing. The text they wanted to use was, "Many studies have already claimed that teenage alcoholism could lead to more problems later in life." How ironic! This ad would follow my essay explaining that one of the studies is completely bogus. I rejected them.

The second agency wanted an ad accompanying the essay "Subtraction Problems, Russian Style." I placed it. They wrote to me (and I reproduce it with all of their errors intact):

I really appreciate your efforts on this. As I checked the text link, I have seen that the text link has been label as "Sponsor ad". Kindly omit or delete the word "Sponor ad:" or you may changed it to "Recommended site or Relevant Site" but I would love to prefer the text link be seen as natural meaning no labeled inserted on it.

They wanted me to pretend that I recommend their product. I was naive enough to think that I was selling space on my page, but what they really wanted was for me to lie that I like their product.

Before this experiment, I hoped to find some honest ads for my blog. After this experiment, I realized how much stupidity and falsehood are involved. Since then, I ignore all offers of ads that come my way. That's why my blog is ad-free.


The No-Flippancy Game

My STEP students invented a coin-flipping game that doesn't require a coin. It is called The No-Flippancy Game.

Alice and Bob choose distinct strings of length n consisting of the letters H (for heads) and T (for tails). The two players alternate selecting the outcome of the next "flip" to add to the sequence by the rule below.

The "flip" rule: Let i < n be the maximal length of a suffix of the sequence of chosen outcomes that coincides with a prefix of the current player’s string. The player then selects the element of their string with index i + 1 as the next term in the sequence.

Alice goes first, and whoever's string appears first in the sequence of choices wins. In layman terms, the game rules mean that the players are not strategizing, but rather greedily finishing their strings.

Suppose n = 2 and Alice chose HH. If Bob chooses HT, then Bob wins. Alice has to choose H for the first flip. Then Bob chooses T and wins. On the other hand, if Bob chooses TT for his string, the game becomes infinite. On her turn, Alice always chooses H, while on his turn Bob always chooses T. The game outcome is an alternating string HTHTHT... and no one wins.

Suppose n = 4, Alice chooses HHTT, and Bob chooses THHH. The game proceeds as HTHHTHHH, at which point Bob wins.

This game is very interesting. The outcome depends on how Alice's and Bob's chosen strings overlap with each other. We wrote a paper about this game, which is available at math.CO arXiv:2006.09588.


2020 MIT Mystery Hunt

Every year I write about latest MIT Mystery Hunt puzzles that might be appealing to mathematicians. Before diving into mathy puzzles, I would like to mention two special ones:

Unfortunately math wasn't prominent this year:

On the other hand, Nikoli-type puzzles were represented very well:

Some computer sciency puzzles:

Cryptography:

A couple of puzzles with the mathy side hidden:


SET Tic-Tac-Toe

The academic year is over and my junior PRIMES STEP group finished their paper about a classification of magic SET squares. A magic SET square is a 3 by 3 square of SET cards such that each row, column, and diagonal is a set. See an example below. The paper is posted at the arXiv:2006.04764.

A magic SET square

In addition to classifying the magic SET squares, my students invented the game of SET tic-tac-toe. It is played on nine cards that form a magic SET square. Two players take turns picking a card from the square. The first player who has a set wins.

One might think that this game is the same as tic-tac-toe, as a player wins as soon at they have cards from the same row, column, or diagonal. But if you build a magic SET square, you might notices that each magic SET square contains 12 sets. In addition to rows, columns, and diagonals, there are sets that form broken diagonals. The picture below shows all the sets in a magic SET square.

Sets in magic SET squares

There are more ways to win in this game than in a regular tic-tac-toe game. My students proved that ties are impossible in this game. They also showed, that, if played correctly, the first player always wins.


Coronavirus and Gender

You probably heard in the news that more men are dying from coronavirus than women. But not in Massachusetts. Here the proportion of women is about 52 percent. Why is this the case? Being a woman, should I be worried that I live in Massachusetts?

We know that coronavirus strikes older people harder than younger ones. Thus, we should take age into account. In the US more boys are born than girls. By the age of 40 the ratio evens out. Starting from 40 there are more women than men. With each next age group, the disparity increases. According to a recent US population report and for ages 85 and over there are about 4.22 million women versus 2.33 men: the proportion is almost 2 to 1.

As the coronavirus targets older people, were it gender-neutral, we would have had way more female deaths than male. This is not the case. So it hits males harder than females. But why are the ratios of female to male deaths different for different countries and states?

One simple explanation is that this is related to life expectancy and the age of the population. The older the population, the bigger the percentage of females. Which in turn increases the proportion of female deaths.

It could also be that Massachusetts has good health care making the average age of dying patients older than the average age for the country. This in turn will increase the proportion of females dying from coronavirus. No, I am not worried about living in Massachusetts.


Among Mathematicians

I grew up in the USSR, where I was clueless about the race issues in the US. I have now lived in the US for 30 years, and still feel that there are many things about race that I do not understand. As a result, I am afraid to speak about it. I am worried that I'll say something wrong. Recent events have encouraged me to say something. This is my first piece about race.

I came back to mathematics 10 year ago and started working at MIT. I love it. With some exceptions.

Many mathematicians are introverts or snobs or gender-biased. They are not usually friendly. I often walk down a corridor and people who are coming towards don't notice me. If I say hello, they might not even reply or raise their eyes. It could be they are thinking about their next great theorem and do not notice me. It could be that I am not faculty and therefore do not deserve their attention. It could be that as a women I am not worth of their hello.

Soon after I started working at MIT, I was reminded of one of the reasons I left academia. It was this unfriendliness. But this time was different. First, I had grown a thicker skin. Second, I was working within a group. People who were working with me were nice to me. It was enough and so I stayed.

With time I adopted the same style: passing people without saying `Hello.' Mostly I got tired of people not replying to my hello.

One day I was passing this man who, as had happened many times before, purposefully didn't look at me. I thought my usual thought: another introverted/snobbish/gender-biased mathematician. Then I suddenly stopped in my tracks. My logic was wrong. This guy was Black. The unfriendliness of mathematicians is surely way worse for him than for me. It could be that he is looking at the floor for the same reason I do it: he is afraid that people will ignore his greeting. I failed to think about race deep enough before this realization. What happened next should have happened years earlier.

I took the initiative and the next couple of times I saw him, I said hello. This was all it took—two hellos—to change the whole feeling between us. The guy has a great smile.


Coronavirus in NYC

It was reported last week that that 37 NYPD members died of covid-19. I assume that they were way below 65. It is known that the coronovirus death rate for people below 65 is a quarter of the total death rate. That means, 37 people in NYPD correspond to at least 150 people in general. Assuming that the mortality rate of coronavirus is 1 percent, the number of infected NYPD members a month ago was 15000.

By now, it could be that more than half of NYPD was infected.

NYPD members have to communicate with people a lot due to the nature of their work. That means they are more prone to being infected. At the same time, they transmit more than people in many other professions.

I can conclude, that about half of the people that are high transmitters in NY have antibodies by now. Assuming they are immune, the covid transmission rate in NY has to be down.

Assuming the immunity stays with people for a while, the second wave in NY can't be as bad as the first one.


Anchored Rectangles

Suppose we want to pack a unit square with non-overlapping rectangles that have sides parallel to the axes. The catch is that the lower left corners of all the rectangles are given. By the way, such rectangles are called anchored. Now, given some points in the unit square, aka the lower left corners, we want to find anchored rectangles with the maximum total area.

Imcreasing permutation

When the given points are close to the right upper corner of the square, the total area is small. When a single point is in the bottom left corner of the square, we can cover the whole square. The problem becomes more interesting if we add one extra assumption: one of the given points has to be the bottom left corner of the square. In the 1960's, it was conjectured by Allen Freedman that any set of points has an anchored rectangle packing with the area of at least one half. The problem is quite resistant. In 2011, Dumitrescu and Tóth showed that every set of points has a packing of area at least 0.09, which was the first constant bound found, and is the best bound currently known.

I gave this problem to my PRIMES student Vincent Bian. He wrote a paper, Special Configurations in Anchored Rectangle Packings, that is now available at the arxiv. When you look at this problem you see that the number of ways to pack depends on the relative coordinates of the points. That means you can view the points as a permutation. Vincent showed that the conjecture is true for several different configurations of points: increasing, decreasing, mountain, split layer, cliff, and sparse decreasing permutations.

An increasing permutation is easy. There are two natural ways to pack the rectangles. One way, when rectangles are horizontal and each rectangle reaches to the right side of the square (see picture above). Another way, when rectangles are vertical. When you take the union of both cases, the square is completely covered, which means at least one of the cases covers at least half of the square. The worst case scenario, that is, the case when the maximum possible area is the smallest is when your points are placed equidistantly on the diagonal.

Decreasing permutation

Other cases are more difficult. For example, Vincent showed that for a decreasing permutation with n points, the worst case scenario is when the points are arranged equidistantly on a hyperbola xy = (1-1/n)n. The picture shows the configuration for 15 points. The total area is more than one half.


John Conway, the Presenter

(I wrote this piece for La Recherche. It was translated into French by Philippe PAJOT. You can find this piece and pieces by others at John Horton Conway: a magician of maths disappears.)

Unlike many other mathematicians I know, John Conway cared a lot about the way he presented things. For example, in the puzzle he invented—known as Conway's Wizards—the wizards had to be riding on a bus. Why was the bus so important? You see, the numbers in the puzzle were related to the age of one of the wizards, the number of the bus, and the number of the wizard's children. It was important to John that the readers be able to use a convenient notation a, b and c for these numbers and remember which number is which.

When I give my lecture on integers and sequences, I show my students a list of different famous sequences. The first question from the audience is almost always: "What are the Evil Numbers?" As you can guess the name for this sequence was invented by John Conway. This name was invented together with the name of another sequence which is called Odious Numbers. These two sequences are complementary in the same sense as even and odd numbers are complementary: every natural number is either evil or odious. The names are good, not only because they attract, but also because they help remember what the sequences are. Evil numbers are numbers with an even number of ones in their binary representation. I assume that you can interpolate what the odious numbers are.

When he was lecturing, John used all sorts of tricks to emphasize important points: From time to time I saw him shouting or throwing his shoes. Once I remember him staring at his statement written on the blackboard for a really long time. My neighbor in the lecture hall got uncomfortable. He assumed that John, who was at that time way over 70, was blanking out and had forgotten what he wanted to say. I calmed my neighbor down. It was my fourth time listening to the same lecture, including the same pause. John Conway didn't forget.


My Last Picture of John Conway

The picture was taken on December 21 of 2019 at Parker Life care facility right before dinner.

John Conway December 21, 2019

Mathy Review of the 2019 MIT Mystery Hunt

Every year I review MIT mystery hunt from a mathematician's point of view. I am way behind. The year is 2020, but I still didn't post my review of 2019 hunt. Here we go.

Many puzzles in 2019 used two data sets. Here is the recipe for constructing such a puzzle. Pick two of your favorite topics: Star Trek and ice cream flavors. Remember that Deanna Troi loves chocolate sundae. Incorporate Deanna Troi into your puzzle to justify the use of two data sets.

On one hand, two data sets guarantee that the puzzle is new and fresh. On the other hand, often the connection between two topics was forced. Not to mention that puzzle solving dynamic is suboptimal. For example, you start working on a puzzle because you recognize Star Trek. But then you have to deal with ice cream which you hate. Nonetheless, you are already invested in the puzzle so you finish it, enjoying only one half of it.

Overall, it was a great hunt. But the reason I love the MIT mystery hunt is because there are a lot of advanced sciency puzzles that can only appear there. For example, there was a puzzle on Feynman diagrams, or on characters of representations. This year only one puzzle, Deeply Confused, felt like AHA, this is the MIT Mystery hunt.

Before discussing mathy puzzles I have to mention that my team laughed at Uncommon Bonds.

I will group the puzzles into categories, where the categories are obvious.

Mathy puzzles.

Here are some logic puzzles, in a sense that Sudoku is a logic puzzle.

Now we have logic puzzles or another type, where you need to draw a grid. These are puzzles of the type: Who lives in the White House?

Now we have logic puzzles or yet another type, where you need to figure out which statements are true and which are false.

Now some cryptography.

And some programming.

Miscellaneous.


US Coronavirus Numbers

Every day I check coronavirus numbers in the US. Right now the number of deaths is 288 and the number of recovered is 171. More people died than recovered. If you are scared about the mortality rate, I can calm you and myself down: our government is incompetent—the testing wasn't happening—that means the numbers do not show people who had mild symptoms and recovered. The real number of recovered people should be much higher.

Scientists estimated the mortality rate of coronavirus as being between 1 and 3.5 percent. Also, they say that it usually takes three weeks to die. That means three weeks ago the number of infected people in the US was between 8,000 and 29,000. The official number of cases three weeks ago was 68. I am panicking again—our government is incompetent—three weeks ago they detected between 0.25 and 1 percent of coronavirus cases. If this trend continues, then the official 19,383 infected people as of today means, in reality, somewhere between 2 million and 8 million infected people.

I can calm you and myself down: the testing picked up pace. This means, the ratio of detected cases should be more than 1 percent today. Probably the number of infected people today in the US is much less than 8 million. I am not calm.


A Game with the Devil

My former student, Dai Yang, sent me the following cute puzzle:

Puzzle. You are playing a game with the Devil. There are n coins in a line, each showing either H (heads) or T (tails). Whenever the rightmost coin is H, you decide its new orientation and move it to the leftmost position. Whenever the rightmost coin is T, the Devil decides its new orientation and moves it to the leftmost position. This process repeats until all coins face the same way, at which point you win. What's the winning strategy?

The Game of Chessnot

My friend Zeb, aka Zarathustra Brady, invented a new game that uses chess pieces and a chessboard. Before the game, the players put all chess pieces on white squares of the board: white pieces are placed in odd-numbered rows and black pieces are in even-numbered rows. At the beginning all white squares are occupied and all black squares are empty. As usual white starts.

On your turn, you can move your piece from any square to any empty square as long as the number of enemy neighbors doesn't decrease. The neighbors are defined as sharing a side of a square. Before the game starts each piece has zero enemy neighbors and each empty square has at least one white and one black neighbor. That means that on the first turn the white piece you move will increase the number of neighbors from zero to something. As usual, the player who doesn't have a move loses.

As you can immediately see, that number of pairs of enemy neighbors is not decreasing through the game. I tried to play this game making a move which minimizes the increase of the pairs of neighbors. I lost, twice. I wonder if there is a simple strategy that is helpful.

It is important that this game is played with chess pieces in order to confuse your friends who pass by. You can see how much time it takes them to figure out that this game is not chess, but rather a Chessnot. Or you can enjoy yourself when they start giving you chess advice before realizing that this is not chess, but rather a Chessnot.


The Padlock Puzzle

I heard this puzzle many years ago, and do not remember the origins of it. The version below is from Peter Winkler's paper Seven Puzzles You Think You Must Not Have Heard Correctly.

Puzzle. Jan and Maria have fallen in love (via the internet) and Jan wishes to mail her a ring. Unfortunately, they live in the country of Kleptopia where anything sent through the mail will be stolen unless it is enclosed in a padlocked box. Jan and Maria each have plenty of padlocks, but none to which the other has a key. How can Jan get the ring safely into Maria's hands?

I don't know whether this puzzle appeared before the Diffie-Hellman key exchange was invented, but I am sure that one of them inspired the other. The official solution is that Jan sends Maria a box with the ring in it and one of his padlocks on it. Upon receipt Maria affixes her own padlock to the box and mails it back with both padlocks on it. When Jan gets it, he removes his padlock and sends the box back, locked only with Maria's padlock. As Maria has her own key, she can now open it.

My students suggested many other solutions. I wonder if some of them can be translated to cryptography.

Now that we've looked at the Padlock Puzzle, let's talk about cryptography. I have an imaginary student named Charlie who doesn't know the Diffie-Hellman key exchange. Charlie decided that he can adapt the padlock puzzle to help Alice send a secret message to Bob. Here's what Charlie suggests:

Suppose the message is M. Alice converts it to binary. Then she creates a random binary key A and XORs it with M. She sends the result, M XOR A, to Bob. Then Bob creates his own random key B and XORs it with what he receives and sends the result, M XOR A XOR B, back to Alice. Alice XORs the result with her key to get M XOR A XOR B XOR A = M XOR B and sends it to Bob. Bob XORs it with his key to decipher the message.

Each sent message is equivalent to a random string. Intercepting it is not useful to an evil eavesdropper. The scheme is perfect. Or is it?


Meta Logic

Here is a logic puzzle.

Puzzle. You are visiting an island where all people know each other. The islanders are of two types: truth-tellers who always tell the truth and liars who always lie. You meet three islanders—Alice, Bob, and Charlie—and ask each of them, "Of the two other islanders here, how many are truth-tellers?" Alice replies, "Zero." Bob replies, "One." What will Charlie's reply be?

The solution proceeds as follows. Suppose Alice is a truth-teller. Then Bob and Charlie are liars. In this situation Bob's statement is true, which is a contradiction. Hence, Alice is a liar. It follows, that there is at least one truth-teller between Bob and Charlie. Suppose Bob is a liar. Then the statement that there is one truth-teller between Alice and Charlie is wrong. It follows that Charlie is a liar. We have a contradiction again. Thus, Alice is a liar and Bob is a truth-teller. From Bob's statement, we know that Charlie must be a truth-teller. That means, Charlie says "One."

But here is another solution suggested by my students that uses meta considerations. A truth-teller has only one possibility for the answer, while a liar can choose between any numbers that are not true. Even if we assume that the answer is only one of three numbers—0, 1, or 2—then the liar still has two options for the answer. If Charlie is a liar, there can't be a unique answer to this puzzle. Thus, the puzzle question implies that Charlie is a truth-teller. It follows that Alice must be lying and Bob must be telling the truth. And the answer is the same: Charlie says, "One."


Recovery Jokes

You might have noticed that my blogging slowed down significantly in the last several months. I had mono: My brain was foggy, and I was tired all the time. Now I am feeling better, and I am writing again. What better way to get back to writing than to start with some jokes?

* * *

The wife of a math teacher threw him out from point A to point B.

* * *

At the job interview at Google.
—How did you hear about our company?

* * * (submitted by Sam Steingold)

50% of marriages end with divorce. The other 50% end with death.

* * *

People say that I am illogical. This is not so, though this is true.

* * *

Humanity invented the decimal system, because people have 10 fingers. And they invented 32-bit computers, because people have 32 teeth.

* * *

When a person tells me, "I was never vaccinated, and, as you can see, I am fine," I reply, "I also want to hear the opinion of those who were never vaccinated and died."

* * *

I will live forever. I have collected a lot of data over the years, and in all of the examples, it is always someone else who dies.

* * *

Just got my ticket to the Fibonacci convention! I hear this year is going to be as big as the last two years put together.

* * *

I am afraid to have children as one day I will have to help them with math.


My New Favorite Probability Puzzle

This is my favorite puzzle in the last issue of the Emissary, proposed by Peter Winkler.

Puzzle. Alice and Bob each have 100 dollars and a biased coin that flips heads with probability 51%. At a signal, each begins flipping his or her coin once per minute, and betting 1 dollar (at even odds) on each flip. Alice bets on heads; poor Bob, on tails. As it happens, however, both eventually go broke. Who is more likely to have gone broke first?
Follow-up question: As above, but this time Alice and Bob are flipping the same coin (biased 51% toward heads). Again, assume both eventually go broke. Who is more likely to have gone broke first?


A Probability Puzzle

Puzzle. You got two envelopes with two distinct real numbers. You chose one of them and open it. After you see the number you are allowed to swap envelopes. You win if at the end you pick the larger number. Find a strategy that gives you a probability more than 1/2 of winning.

What are the Numbers?

Another cute puzzle found on Facebook.

Puzzle. A teacher wrote four positive numbers on the board and invited his students to calculate the product of any two. The students calculated only five of six products and these are the results: 2, 3, 4, 5, 6. What is the last product? What are the original four numbers?

Another Weird Test Question

I found this puzzle on Facebook:

Puzzle. Solve this:
1+4 = 5,
2+5 = 12,
3+6 = 21,
5+8 = ?
97% will fail this test.

Staring at this I decided on my answer. Then I looked at the comments: they were divided between 34 and 45 and didn't contain the answer that initially came to my mind. The question to my readers is to explain the answers in the comments and suggest other ones. Can you guess what my answer was?


Day and Night

Puzzle. The length of the day today in Boston is the same as the length of the coming night tonight. What is the total length of both?


How Old is Everyone?

My friend Alice reminds me of me: she has two sons and she is never straight with her age. Or, maybe, she just isn't very good with numbers.

Once I visited her family for dinner and asked her point blank, "How old are you?" Here is the rest of the conversation:

Alice: I am two times older than my younger son was 5 years ago.
Bob: My mom is 12 times older than my older brother.
Carl: My younger brother always multiplies every number he mentions by 24.
Bob: My older brother is 30 years older than me.
Carl: My mom is 8 times older than me.
Alice: My older son always multiplies every number he mentions by 2.

How old is everyone?


Cube Sudo-Kurve

Last year, when I read an application file of Wayne Zhao to PRIMES, I got very excited because he liked puzzles. And I've always wanted to have a project about puzzles. After Wayne was accepted to PRIMES we started working together. Wayne chose to focus on a variation of Sudoku called Sudo-Kurve.

We chose a particular shape of Sudo-Kurve for this project, which ended up being very rewarding. It is called Cube Sudo-Kurve. The Cube Sudo-Kurve consists of three square blocks. The gray bent lines indicate how rows and columns continue. For example, the first row of the top left block becomes the last column of the middle block and continues to the first row of the bottom right block. As usual each row, column, and square region has to have 9 distinct digits.

Cube Sudo-Kurve

Wayne and I wrote a paper Mathematics of a Sudo-Kurve, which has been published at Recreational Mathematics Magazine.

A Cube Sudo-Kurve needs at least 8 clues to have a unique solution. Here we have a puzzle with 8 clues that we designed for our paper.


Emissary Puzzles

I've been invited to help with the Puzzle Column at the MSRI newsletter Emissary. We prepared six puzzles for the Fall 2018 issue.

I love the puzzles there. Number 2 is a mafia puzzle that I suggested. Number 6 is a fun variation on the hat puzzle I wrote a lot about. Here is puzzle Number 3.

Puzzle. Let A = {1,2,3,4,5} and let P be the set of all nonempty subsets of A. A function f from P to A is a "selector" function if f(B) is in B, and f(B union C) is either equal to f(B) or f(C). How many selector functions are there?

Cave Lioness

(Photo by Rebecca Frankel.)
Cave Lion

When I was in grade school, one of the teachers called me Cave Lioness. She hated my unruly hair, which reminded her of a lion's mane. This teacher was obviously very uninformed, for female lions do not have manes.

This name calling had the opposite to the desired effect. I became proud of my mane and didn't ever want to cut it. When I grew older, I opted for convenience and started to cut my hair short&mdahs;sometimes very short.

Last year I was too busy for barbers, and my hair grew more than I intended. As it turned into a mane, I remembered the story of this nickname.


My Phone

Once I was giving a math lecture and my phone, which I've never quite understood, was on the desk in front of me. Suddenly it rang. I didn't pick it up, as I proceeded with my lecture. The ringing stopped, while I was explaining a particularly interesting mathematical point. After a minute, my phone said, "I do not understand a word you are saying."


The Halfsies

Detective Radstein is investigating a robbery. He apprehends three suspects: Anne, Bill, and Caroline. The detective knows that no one else could have participated in the robbery. During the interrogation the suspects make the following statements:

Detective Radstein also discovered that all three suspects are members of a club called The Halfsies. Every time they speak, they make two statements, one of which is a lie and the other one is true. Who committed the robbery?


Less Annoying Hyperbolic Surfaces

Less Annoying Hyperbolic Surfaces

I already wrote about my first experience crocheting hyperbolic surfaces. In my first surface I added two more stitches per current stitch. It took me hours to crochet the last row: the same hours it took me to crochet the rest.

For my next project, I reduced the ratio. The light blue thingy has ratio 3/2. I continued making my life simpler. The next project, the purple surface on the left, has ratio 4/3. The last project on the right has a ratio of 5/4 and is my favorite. Mostly because I am lazy and it was the fastest to make.


Fast Thinking

How much time will it take you to answer the following question?

Can the equation 29x + 30y + 31z = 366 be solved in natural numbers?

Happy 14 + 24 + 34 + 54 + 64!

Happy 2019, the first 4 digit number to appear 6 times in the decimal expansion of Pi.

By the way, 2019 is the product of two primes 3 and 673. The sum of these two prime factors is a square.

This is not all that is interesting about factors of 2019. Every concatenation of these two prime factors is prime. Even more unusual, 2019 is the largest known composite number such that every concatenation of its prime factors is prime. [Oops, the last statement is wrong, Jan 3,2019]

Happy Happy-go-Lucky year, as 2019 is a Happy-go-Lucky number: the number that is both Happy and Lucky.

In case you are wondering, here is the definition of Happy numbers: One can take the sum of the squares of the digits of a number. Those numbers are Happy for which iterating this operation eventually leads to 1.

In case you are wondering, to build the Lucky number sequence, start with natural numbers. Delete every second number, leaving 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, …. The second number remaining is 3, so delete every third number, leaving 1, 3, 7, 9, 13, 15, 19, 21, …. The next number remaining is 7, so delete every 7th number, leaving 1, 3, 7, 9, 13, 15, 21, …. The next number remaining is 9, so delete every ninth number, etc.


Puzzle Ninja

Puzze Ninja by Alex Bellos

Alex Bellos sent me his new book Puzzle Ninja: Pit Your Wits Against The Japanese Puzzle Masters. What has he done to me? I opened the book and couldn't close it until I solved all the puzzles.

This is a fantastic book. There are many varieties of puzzles, including some types that I've never seen before. Also, the beautifully designed puzzles are great. Often puzzles of the same type target different solving ideas or have varied cool themes.

This book is more than a bunch of puzzles; it also contains poetic stories about puzzle histories and Japanese puzzle designers. Fantastic puzzles together with a human touch: this might be my favorite puzzle book.

Wolf and Sheep Slitherlink Puzzle 1

I present two puzzles from the book. The puzzle type is called Wolf and Sheep Slitherlink. The Slitherlink is a famous puzzle type with the goal of connecting some of the neighboring dots into a single non-self-intersecting loop. A number inside a small square cell indicates how many sides of the square are part of the loop. Wolf and Sheep Slitherlink is a variation of Slitherlink in which all sheep should be kept inside the fence (loop) and all the wolves outside.

Ignore the numbers in the title as they just indicate the order number of Wolf and Sheep Slitherlink puzzles in the book. The number of ninja heads shows the level of difficulty. (The hardest puzzles in the book have four heads.) The difficulty is followed by the name of the puzzle master who designed the puzzle.

The first puzzle above is slightly easier than the second. I like the themes of these two puzzles. In the first one, only one cell—lonely wolf—marks the relationship to the fence. In the second one, the wolf in the center—who needs to be outside the fence—is surrounded by a circle of sheep who are in turn surrounded by a circle of wolves.

Wolf and Sheep Slitherlink Puzzle 2

Two Dice

My friend Alex Ryba uses interesting math questions in the CUNY Math Challenge. For the 2016 challenge they had the following problem.

Problem. Eve owns two six-sided dice. They are not necessarily fair dice and not necessarily weighted in the same manner. Eve promises to give Alice and Bob each a fabulous prize if they each roll the same sum with her dice. Eve wishes to design her two dice to minimize the likelihood that she has to buy two fabulous prizes. Can she weight them so that the probability for Alice and Bob to get prizes is less than 1/10?

The best outcome for Eve would be if she can weight the dice so that the sum is uniform. In this case the probability that Alice and Bob get the prizes is 1/11. Unfortunately for Eve, such a distribution of weight for the dice is impossible. There are many ways to prove it.

I found a beautiful argument by Hagen von Eitzen on the stack exchange: Let ai (correspondingly bi) be the probabilities that die A (correspondingly B) shows i + 1. It would be very useful later that that i ranges over {0,1,2,3,4,5} for both dice. Let f(z) = ∑ aizi and g(z) = ∑ bizi. Then the desired result is that f(z)g(z) = ∑j=010 zj/11. The roots of the right side are the non-real roots of unity. Therefore both f and g have no real roots. So, they must both have even degree. This implies a5=b5=0 and the coefficient of z10 in their product is also 0, contradiction.

Alex himself has a straightforward argument. The probabilities of 2 and 12 have to be equal to 1/11, therefore, a0b0 = a5b5 = 1/11. Then the probability of a total 7 is at least a0b5 + a0b5. The geometric mean of a0b5 and a0b5 is 1/11 (from above), so their arithmetic mean is at least 1/11 and their sum is at least 2/11. Therefore, the uniform distribution for sums is impossible.

So 1/11 is impossible, but how close to it can you get?


My 1975 IMO Team

My IMO Team, 1975

I just got this picture from my friend Victor Gutenmacher, which I never saw before. My 1975 IMO team is posing at our training grounds before the Olympiad trip to Bulgaria.

Left to right: Boris Yusin, Yuri Ionin, Zoya Moiseyeva (front), Gregory Galperin (back), me, Ilya Yunus, Valentin Skvortsov, Aleksandr Kornyushkin, Sergei Finashin, Sergei Fomin (front), Alexander Reznikov (back), Yuri Shmelev (front), Yuri Neretin (back), Victor Gutenmacher.

Our coaches are in the shot as well. Surprisingly, or not surprisingly, all of them moved to the USA. Yuri Ionin, now retired, was a professor at Central Michigan University. Gregory Galperin is a professor at Eastern Illinois University. Sergei Fomin is a professor at the University of Michigan. Victor Gutenmacher worked for BBN Technologies and Siemens PLM Software, and is now retired.

There are two more adults in the picture: Valentin Anatolievich Skvortsov, our leader and Zoya Ivanovna Moiseyeva, our deputy leader. Skvortsov was working at the math department of Moscow State University at that time. The University was angry that he didn't block some students with Jewish heritage from the team thus allowing them to be accepted to Moscow State University without exams. I wrote a story of how Zoya persuaded Alexander Reznikov not to go to Moscow University to help Valentin. It ruined Alexander's live, and didn't even help Valentin. 1975 was Valentin's last trip as the leader.


An Orchestra Puzzle

An orchestra of 120 players takes 70 minutes to play Beethoven's 9th Symphony. How long would it take for 60 players to play the symphony?


The Annoyance of Hyperbolic Surfaces

A hyperbolic surface

I do not like making objects with my hands. But I lived in Soviet Russia. So I knew how to crochet, knit, and sew — because in Russia at that time, we didn't have a choice. I was always bad at it. The only thing I was good at was darning socks: I had to do it too often. By the way, I failed to find a video on how to darn socks the same way my mom taught me.

Then I came to the US. I suddenly found myself in a rich society, where it was cheaper to buy new stuff than to spend the time doing things with my hands. So I happily dropped my craftsmanship.

After not working with my hands for 28 years, one day I needed hyperbolic surfaces for my classes and I couldn't find any to buy. Hyperbolic surfaces are famous for providing an example when the Euclid's Fifth axiom doesn't work. These hyperbolic surfaces look flat locally, so you can continue a line in any given direction. If you draw a line on such a surface and pick a point that is not on the line, then you can draw many lines through the point that are parallel to the given line.

My students are more important than my dislike of crochet, so I decided to just do it myself. I asked my friend Debbie, who knows how to crochet, for advice, and she gave me more than advice. She gave me a hook and a piece of yarn and reminded me how to work the hook. She started me with a small circle. After that all I had to do was add two stitches for each stitch on the perimeter of the circle. The finished product is this green ballish thing that looks like a brain, as in the photo.

Outside the starting circle, each small surface segment of this "brain" looks the same, making the "brain" a surface of constant curvature.

I chose a ratio of 2 to 1, adding two new stitches for each previous stitch. With this ratio, my flattish surface started looking like a ball very fast. The length of the perimeter doubled for every row. Thus each new row I crocheted took the same total amount of time that I had already spent on the whole thing. All the hours I worked on this "brain," I kept thinking: darn, it is so unrewarding to do this. Annoying as it was, the thing that kept me going was my initial decision to continue to use up all the yarn Debbie had given me. In the end, with this ratio, half the time I worked was spent making the final row.


3-Inflatable Permutations

We can inflate one permutation with another permutation. Let me define the inflation by examples and pictures. Suppose we have a permutation 132 which we want to inflate using permutation 21. The result is the permutation 216543 that can be divided into three blocks 21|65|43. The blocks are ordered as the first permutation 132, and within each block the order is according to the second permutation. This operation is often called a tensor product of two permutations. The operation is non-commutative: the inflation of 21 with 132 is 465132.

Inflation Definition

As one might guess this post is related to k-symmetric permutations, that is, permutations that contain all possible patterns of size k with the same frequency. As I mentioned in my recent post 3-Symmetric Permutations, the smallest non-trivial examples of 3-symmetric permutations are 349852167 and 761258943 in size 9.

A permutation is called k-inflatable if its inflation with k-symmetric permutation is k-symmetric. One of my PRIMES projects was about 3-inflatable permutations. The result of this project is the paper On 3-Inflatable Permutations written with Eric Zhang and posted at the arxiv.

The smallest non-trivial examples of 3-inflatable permutations are in size 17: E534BGA9HC2D1687F and B3CE1H76F5A49D2G8, where capital letters denote numbers greater than nine. Another cool property discovered in the paper is that the tensor product of two k-inflatable permutations is k-inflatable.


Symmetries of k-Symmetric Permutations

I am fascinated by 3-symmetric permutations, that is, permutations that contain all possible patterns of of size three with the same frequency. As I mentioned in my recent post 3-Symmetric Permutations, the smallest non-trivial examples are in size 9.

When I presented these examples at a combinatorics pre-seminar, Sasha Postnikov suggested to draw the permutations as a graph or a matrix. Why didn't I think of that?

Below are the drawings of the only two 3-symmetric permutations of size 9: 349852167 and 761258943.

3-Symmetric Permutations

As I already mentioned in the aforementioned essay the set of 3-symmetric permutations is invariant under the reversal and subtraction of each number from the size of the permutation plus 1. In geometrical terms it means reflection along the vertical midline and central symmetry. But as you can see the pictures are invariant under 90 degree rotation. Why?

What I forgot to mention was that the set of k-symmetric permutations doesn't change after the inversion. In geometrical terms it means the reflection with respect to the main diagonal. If you combine a reflection with respect to a diagonal with a reflection with respect to a vertical line you get a 90 degree rotation. Overall, the symmetries of the k-symmetric permutations are the same as all the symmetries of a square. Which means we can only look at the shapes of the k-symmetric permutations.

There are six 2-symmetric permutations: 1432, 2341, 2413, 3142, 3214, 4123. As we can see in the picture below they have two different shapes.

2-Symmetric Permutations

Here is the list of all 22 2-symmetric permutations of size 5: 14532, 15342, 15423, 23541, 24351, 24513, 25143, 25314, 31542, 32451, 32514, 34152, 34215, 35124, 41352, 41523, 42153, 42315, 43125, 51243, 51324, 52134. The list was posted by Drake Thomas in the comments to my essay. Up to symmetries the permutations form four groups. Group 1: 14532, 15423, 23541, 32451, 34215, 43125, 51243, 52134. Group 2: 15342, 24351, 42315, 51324. Group 3: 24513, 25143, 31542, 32514, 34152, 35124, 41523, 42153. Group 4: 25314, 41352. The picture shows the first permutation in each group.

2-Symmetric Permutations of Size 5

3-Symmetric Graphs

In my previous post I described 3-symmetric permutations. Now I want to define 3-symmetric graphs.

A reminder: a k-symmetric permutation is such that the densities of all permutations of size k in it are the same. In particular a 2-symmetric permutation has the same number of inversions and non-inversions. How do we translate this to graphs? I call a graph 2-symmetric if it has the same number of edges as non-edges. 2-symmetric graphs are easy to construct, but they only exist if the number of vertices, n, is such that n choose 2 is even. The simplest non-trivial examples are graphs with 4 vertices and three edges.

The above definition is difficult to generalize. So I rephrase: a graph G is 2-symmetric, if the density of any subgraph H with 2 vertices in G is the same as the expected density of H in a random graph where the probability of an edge equals 1/2. This definition is easy to generalize. A graph G is k-symmetric, if the density of any subgraph H with k vertices in G is the same as the expected density of H in a random graph where the probability of an edge equals 1/2. In particular, here are the densities of all four possible subgraphs with 3 vertices in a 3-symmetric graph:

For a graph G to be 3-symmetric, the number of vertices, n, in G needs to be such that n choose 3 is divisible by 8. The first non-trivial case is n = 8. Here are the pictures of two 3-symmetric graphs. The first one is a wheel, and the second one is its complement.

A Wheel Graph with 8 vertices
A Complement to the Wheel Graph with 8 vertices

3-Symmetric Permutations

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.


Mafia Logic Puzzle

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:

Who is who?


Shapes of Symbols in Latin Squares

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.

Shape 0 Shape 1 Shape 2 Shape 3 Shape 4 Shape 5 Shape 6

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.

Square 12

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.


Another Cool Coin-Weighing Problem

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?

I am on TEDEd

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


A Self-referencing Multiple-Choice Question

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).

Innisfree Garden

Innisfree Garden

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.


Looking for the Cutest Answer

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


Richard Guy

At G4G13 with Richard Guy

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.


My Last Visit with John Conway

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.

John Conway, Aug 11, 2017

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.


A Crypto Word Search for G4G13

Here is the crypto word search I designed as a gift exchange for G4G13 (Gathering for Gardner). The submitted file is here: Crypto Word Search.

A B C D E F G H C I F B B C D I J K L A J C I F M A C K N O O N F B I F J O P P Q G H F A R K J B

The words are: ART IDEA MAGIC MATH NOTE PI PROBLEM PUZZLE RIDDLE TRICK.


Punny Puzzles at the MIT Mystery Hunt

This is a math blog, but from time to time, I write about other things. Today I have something to say about puns, which I adore.

I also like gym, but rarely go there: it doesn't work out. I stopped using stairs, because they are up to something. I wanted to learn how to juggle, but I don't have the balls to do it.

I work at MIT, the work place with the best dam mascot: Tim the Beaver. My salary is not big, and I stopped saving money after I lost interest. I'm no photographer, but I have pictured myself outside of MIT too. I am a mathematician, which is the most spiritual profession: I am very comfortable with higher powers. I praise myself on great ability to think outside the box: it is mostly due to my claustrophobia. I am also a bit of a philosopher: I can go on talking about infinity forever.

I would love to tell you a joke. I recently heard a good one about amnesia, but I forgot how it goes.

My biggest problem is with English. So what if I don't know what apocalypse means? It's not the end of the world!

I never get tired of puns and here is my list of pun puzzles from the MIT Mystery Hunt:


Scam Jokes

* * *

Business plan:

  1. Sign-up for a premium-rate telephone number through which you make money from every call.
  2. Take a loan at the bank.
  3. Do not pay back.
  4. Collection agencies start calling non-stop.

* * *

  1. TMake a full-body selfie.
  2. Eat greedily for a year.
  3. Take a full-body selfie again.
  4. Swap before and after.
  5. Post.
  6. Collect the likes.
  7. Give diet advice.

* * *

A cafe patron ordered a pastry, then changed his mind and replaced it with a cup of coffee. When he finished his coffee, he started leaving without paying. The waiter approached him:
—You didn't pay for coffee!
—But I had it instead of the pastry.
—You didn't pay for the pastry either!
—But I didn't have the pastry.

* * *

At a farmers market stand there is a sign: 1 melon—3 dollars, 3 melons—10 dollars. A client requests one melon and pays 3 dollars, then repeats the procedure two more times. Then he says: "I bought three melons for 9 dollars, while you are trying to sell them for 10 dollars. This is really stupid." The farmer talks to himself: This happens all the time: they buy three melons instead of one, and try to teach me how to make money.

* * *

If the government listens in on my phone conversations, should they be paying half of my phone bill?

* * *

To get to free downloads, please, enter your credit card number.

* * *

The biggest lie of the century, "I have read and agree to the terms of ..."

* * * (submitted by Sam Steingold)

Ignorance: If your poker opponent got lucky cards four times in a row, he must get lousy cards now.
Knowledge: Nope, the deals are independent; prior observations have no bearing on the next deal.
Wisdom: The opponent is cheating; get away from the table now!


Solutions to Geometry Puzzles from the 35-th Lomonosov Tournament

I recently posted two geometry problems. Now is the time for solutions:

Problem 1. Is it possible to put positive numbers at the vertices of a triangle so that the sum of two numbers at the ends of each side is equal to the length of the side?

One might guess that the following numbers work: (a+b-c)/2, (b+c-a)/2 and (c+a-b)/2, where a, b, and c are the side lengths. But there exists a geometric solution: Construct the incircle. The tangent points divide each side into two segment, so that the lengths of the segments ending at the same vertex are the same. Assigning this length to the vertex solves the problem. Surprisingly, or not surprisingly, this solution gives the same answer as above.

Problem 2. Prove that it is possible to assign a number to every edge of a tetrahedron so that the sum of the three numbers on the edges of every face is equal to the area of the face.

The problem is under-constrained: there are six sides and four faces. There should be many solutions. But the solution for the first problem suggests a similar idea for the second problem: Construct the inscribed sphere. Connect a tangent point on each face to the three vertices on the same face. This way each face is divided into three triangles. Moreover, the lengths of the segments connecting the tangent points to a vertex are the same. Therefore, two triangles sharing the same edge are congruent and thus have the same area. Assigning this area to each edge solves the problem.

There are many solutions to the second problem. I wonder if for each solution we can find a point on each face, so that the segments connecting these points to vertices divide the faces into three triangles in such a way that triangles sharing an edge are congruent. What would be a geometric meaning of these four points?


Mathy Puzzles at 2018 MIT Mystery Hunt

I was on the writing team for the 2018 MIT Mystery Hunt. I am pleased that the hunt got very positive reviews from the participants. I spent tons of hours working on the hunt and it is good that folks liked it. I edited and tested a lot of puzzles. Here is my review of these year's puzzles that are math-related.

I already posted an essay about the puzzles I wrote myself. Four of my five puzzles are math-related, so I am including them below for completeness. I will mention the topic of each puzzle unless it is a spoiler.

I start with Nikoli-type puzzles. Four elegant Nikoli-type puzzles were written or cowritten by Denis Auroux. In all of them the rules of the logic are stated at the beginning. That means the logic part doesn't contain a mystery and can be solved directly.

There were several puzzles that were very mathematical.

There were also some math-related or computer-sciency puzzles.

There were also several decryption puzzles:


Trump and Pirates

Here is a famous math problem I never before wrote about:

Puzzle. Five pirates discovered a treasure of 100 gold coins. They decide to split the coins using the following scheme. The most senior pirate proposes how to share the coins, and all the pirates vote for or against it. If 50% or more of the pirates vote for it, then the coins will be shared that way. Otherwise, the pirate proposing the scheme will be thrown overboard, and the process is repeated with the next most senior pirate making a proposal.

As pirates tend to be a bloodthirsty bunch, if a pirate would get the same number of coins whether he votes for or against a proposal, he will vote against so that the pirate who proposed the plan will be thrown overboard. Assuming that all five pirates are intelligent, rational, greedy, and do not wish to die, how will the coins be distributed?

You can find the solution in many places including Wikipedia's Pirate game. The answer is surprising: the most senior pirate gets 98 coins, and the third and the fifth pirates by seniority get one coin each. I always hated this puzzle, but never bothered to think through and figure out why. Now I know.

This puzzle emphasizes the flaws of majority voting. The procedure is purely democratic, but it results in extreme inequality.

That means a democracy needs to have a mechanism to prohibit the president from blatantly benefiting himself. With our current president these mechanisms stopped working. Given that Trump does everything to enrich himself, the pirates puzzle tells us what to expect in the near future.

We, Americans, will lose everything: money, clean air and water, national parks, future climate, health, social security, and so on, while Trump will make money.


My 2018 MIT Mystery Hunt Puzzles

I was on the writing team of this year's hunt, which was based on the movie "Inside Out." One of our goals was to create an easy first round to allow small teams to have a full hunt experience. Our first round consisted of 34 puzzles related to five basic emotions: joy, sadness, disgust, fear, and anger. Each emotion had its own meta puzzle. And the round had a meta-meta puzzle and a runaround. As I tend to write easy puzzles, I contributed three puzzles to this emotions round. The puzzles had references to corresponding emotions that were not needed for the solve path. They were inserted there for flavor.

I also wrote another easy puzzle called A Tribute: 2010-2017 (jointly with Justin Melvin, Wesley Graybill, and Robin Diets ). Though the puzzle is easy, it is useful in solving it to be familiar with the MIT mystery hunt. This is why the puzzle didn't fit the first emotions round.

I also wrote a very difficult puzzle called Murder at the Asylum. This is a monstrosity about liars and truth-tellers.


Why?

In mathematics one of the most important questions is why. Let us consider a problem:

Problem. A number has three hundred ones and three hundred zeroes. Can it be a square?

The solution goes like this. Consider divisibility of this number by 9. The sum of the digits is 300. That means the number is divisible by 3, but not by 9. Therefore, it can't be a square.

Why do we consider divisibility by 9? The divisibility by 9 is a very powerful tool, but why was it the first thing that came to my mind? The divisibility by 9 doesn't depend on the order of the digits. Whenever I see a problem where the question talks about digits that can be in any order, the first tool to use is the divisibility by 9.

The why question, is very important in mathematics. But it is also very important in life. It took me many years to start asking why people did this or that. I remember my mom was visiting me in the US. Every time I came back from work, she complained that she was tired. Why? Because she did the laundry in the bath tub. She wouldn't use my washing machine, because she didn't have such a thing in Russia. I promised her that I'd do the laundry myself when there was a sufficient pile. However, she insisted that the dirty clothes annoyed her. I would point that my water bill went up. And so on.

We argued like this every day. We were both frustrated. Then I asked myself why. Why does she do the laundry? The answer was there. She wanted to be helpful. I calmed down and stopped arguing with her. I sucked it up and paid the water bills. Her time with me turned into the most harmonious visit we ever had. Unfortunately, it was the last.


A Scooter Riddle

Puzzle. Alice, Bob, and Charlie are at Alice's house. They are going to Bob's house which is 33 miles away. They have a 2-seat scooter which rides at 25 miles per hour with 1 rider on it; or, at 20 miles per hour with 2 riders. Each of the 3 friends walks at 5 miles per hour. How fast can all three of them make it to Bob's house?

Mathy Jokes

* * * (submitted by Sam Steingold)

I can count to 1023 on my 10 fingers. The rudest number is 132.

* * *

I kept forgetting my password, so I changed it to "incorrect". Now, when I make a mistake during login, my computer reminds me: "Your password is incorrect."

* * *

—You promised me 8% interest, and in reality it is 2%.
—2 is 8—to some degree.

* * * (submitted by Sam Steingold)

Quantum entanglement is simple: when you have a pair of socks and you put one of them on your left foot, the other one becomes the "right sock," no matter where it is located in the universe.

* * *

Teacher:
—I keep telling my students that one half can't be larger or smaller than the other. Still the larger half of my class doesn't get it.


A Gender-Biased Puzzle

This famous trick puzzle is very old:

Puzzle. The professor is watching across a field how the son of the professor's father is fighting with the father of the professor's son. How is this possible?

This puzzle is tricky only because of gender-bias. Most people assume that the professor is male and miss the obvious intended solution, in which a female professor is watching her brother fighting with her husband.

I just gave this problem on a test. Here are other answers that I received.

Years ago people couldn't figure out this puzzle at all. So there has been progress. I was glad that my students suggested so many ideas that work. Nonetheless, many of them revealed their gender-bias by initially assuming that the professor is a man.

I can't wait until this puzzle stops being tricky.


Who Lives in the White House?

Puzzle. There are five houses of different colors next to each other equally spaced on the same road. In each house lives a man of a different profession.

Who lives in the white house?

Correction Nov 11, 2017. Replaced "the same distance from" with "halfway between" to eliminate the possibility of the plumber living in the yellow house. Thank you to my readers for catching this mistake and to Smylers for suggesting a correction.


A Domino-Covering Problem

I do not remember where I saw this problem.

Problem. Invent a connected shape made out of squares on the square grid that cannot be cut into dominoes (rectangles with sides 1 and 2), but if you add a domino to the shape then you can cut the new bigger shape.

This problem reminds me of another famous and beautiful domino-covering problem.

Problem. Two opposite corner squares are cut out from the 8 by 8 square board. Can you cover the remaining shape with dominoes?

The solution to the second problem is to color the shape as a chess board and check that the number of black and white squares is not the same.

What is interesting about the first problem is that it passes the color test. It made me wonder: Is there a way to characterize the shapes on a square grid that pass the color test, but still can't be covered in dominoes?


More Computer Jokes

* * *

Don't anthropomorphize computers: They don't like it.

* * *

I do not have dreams any more. What did I do wrong to make them delete my account?

* * *

How to restore justice: Create a folder named Justice. Delete it. Go to the trash bin and click restore.

* * *

An asocial network: When you sign up, you are friends with everyone. Then you send un-friend requests.


Derek Kisman's Ex Post Facto

I already wrote about two puzzles that Derek Kisman made for the 2013 MIT Mystery Hunt. The first puzzle is now called the Fractal Word Search. It is available on the Hunt website under its name In the Details. I posted one essay about the puzzle and another one describing its solution. The second puzzle, 50/50, is considered one of the most difficult hunt puzzles ever. Unfortunately, the puzzle is not available, but my description of it is.

Today let's look at the third puzzle Derek made for the 2013 Hunt, building on an idea from Tom Yue. This is a non-mathematical crossword puzzle. Derek tends to write multi-layered puzzles: You think you've got the answer, but the answer you've got is actually a hint for the next step.

Often multi-layered puzzles get solvers frustrated, but the previous paragraph is a hint in itself. If you expect the difficulty, you might appreciate the fantastic beauty of this puzzle.

Welcome to Ex Post Facto.


Fair-Share Sequences

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 2n letters are generated from the first 2n 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 2k+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 Fn + Fn-3 + Fn-5 + Fn-6. Bob will have Fn-1 + Fn-2 + Fn-4. We see that Alice gets more by Fn-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.


2015 Coin Problem Solution

A while ago I posted my second favorite problem from the 2015 All-Russian Math Olympiad:

Problem. A coin collector has 100 coins that look identical. He knows that 30 of the coins are genuine and 70 fake. He also knows that all the genuine coins weigh the same and all the fake coins have different weights, and every fake coin is heavier than a genuine coin. He doesn't know the exact weights though. He has a balance scale without weights that he can use to compare the weights of two groups with the same number of coins. What is the smallest number of weighings the collector needs to guarantee finding at least one genuine coin?

Now it's solution time. First we show that we can do this in 70 weighings. The strategy is to compare one coin against one coin. If the scale balances, we are lucky and can stop, because that means we have found two real coins. If the scale is unbalanced, the heavier coin is definitely fake and we can remove it from consideration. In the worst case, we will do 70 unbalanced weighings that allow us to remove all the fake coins, and we will find all the real coins.

The more difficult part is to show that 69 weighings do not guarantee finding the real coin. We do it by contradiction. Suppose the weights are such that the real coin weighs 1 gram and the i-th fake coin weighs 100i grams. That means whatever coins we put on the scale, the heaviest pan is the pan that has the fake coin with the largest index among the fake coins on the scale.

Suppose there is a strategy to find a real coin in 69 weighings. Given this strategy, we produce an example designed for this strategy, so that the weighings are consistent, but the collector cannot find a real coin.

For the first weighing we assign the heaviest weight, 10070 to one of the coins on the scale and claim that the pan with this coin is heavier. We continue recursively. If a weighing has the coins with assigned weights, we pick the heaviest coin on the pans and claim that the corresponding pan is heavier. If there are no coins with assigned weights on pans, we pick any coin on the pans, assigned the largest available weight to it and claim that the corresponding pan is heavier.

After 69 weighings, not more than 69 coins have assigned weights, while all the weighings are consistent. The rest of the coins can have any of the leftover weights. For example, any of the rest of the coins can weigh 100 grams. That means that there is no coin that is guaranteed to be real.


2014 Math Festival in Moscow

I stumbled upon a couple of problems that I like while scanning the Russian website of Math Festival in Moscow 2014. The problems are for 7 graders.

Problem. Inside a 5-by-8 rectangle, Bart draws closed paths that follow diagonals of 1-by-2 rectangles. Find the longest possible path.

This problem is really very difficult. The competition organizers offered an extra point for every diagonal on top of 16. The official solution has 24 diagonals, but no proof that it's the longest. I'm not sure anyone knows if it is the longest.

Here is another problem:

Problem. Alice and Bob are playing a game. They start with two numbers: 2014 and 2015. In one move a player can do one of two things:
  1. subtract one of the numbers by one of the non-zero digits in any of the two numbers or,
  2. divide one number by two if the number is even.
The winner is the person who is the first to get a one-digit number. Assuming that Alice starts, who wins?

My First Husband with My Third Husband

Bernstein and Goncharov

The year is 1994. The man on the left is my first husband, Alexander Goncharov. Although we were out of touch for a decade, when I married my third husband, Joseph Bernstein (on the right), Goncharov started visiting us. It wasn't me he was interested in: he wanted to talk mathematics with my husband. I found this situation hilarious, so I took this photo.

But that's not all. My second husband, Andrey Radul, is not in the picture. But all four of us were students of Israel Gelfand. In short, my three ex-husbands and I are mathematical siblings — that is, we are all one big happy mathematical family.


The Best Writing on Mathematics 2016

Best Writing on Mathematics 2016

The Best Writing on Mathematics 2016 is out. I am happy that my paper The Pioneering Role of the Sierpinski Gasket is included. The paper is written jointly with my high-school students Eric Nie and Alok Puranik as our PRIMES-2014 project.

At the end of the book there is a short list of notable writings that were considered but didn't make it. The "short" list is actually a dozen pages long. And it includes two more papers of mine: