Tanya Khovanova's Math Blog

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

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

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.

• Bubbly—Combinatorial game theory.
• Rules of Order—Fractals mixed with movies.
• Cubic—A long list of cubic polynomials with integer coefficients.
• Twisty Passages—Famous number properties that remind my of my Number Gossip website.

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

• Lantern festival—A cool mixture of Slitherlinks and Galaxies.
• Invisible Walls.
• Place Settings.
• Middle School of Mines—Minesweeper.
• Moral Ambiguity—Nonograms with a twist.
• Connect Four—Mastermind. There was a strong hint that the extraction step was also mastermind. My team spent some time trying to mastermind the ending, until we backsolved. The extraction step was not mastermind. The final grid in the puzzle had the word CODE written in red. It corresponded to letters CDEO found at that location. Given that the letters were not in alphabetical order, it gave the ordering, which didn’t exist in the puzzle. Anyway, you can see that I have a grudge against this puzzle. This could have been a great puzzle. But it wasn’t.
• Schematics—Tons of Nikoli puzzles of different types.

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?

• Compromised.

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

• True and False².

Now some cryptography.

• Tales From The Crypt.
• You’re Gonna Need a Bigger Gravy Boat.
• The Bill.
• Helvetica Is Only an Okay Font.
• A Good Walk Spoiled—Some decyphering and Vim.
• Have You Seen Me?
• Chain of Commands.
• Picture Book.

And some programming.

• Turtle Power!

Miscellaneous.

• Hexed Adventure II: Hexed Again!—A text adventure game with a lot of logic.
• Loaded—Dice of different shapes.
• The Lives of Π—Large numbers.
• Battle of the Network Stars—A lot of actors in a grid.

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.

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?

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.

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.

• Jan can send the ring in a padlock box that is made of cardboard. Maria can just cut the cardboard with a knife.
• Jan can use the magic of the Internet to send Maria schematics of the key so she can either 3d print it or get a professional to forge it. If they are afraid of the schematics getting stolen Jan can send the schematics after the package has been delivered.
• Jan can use a digital padlock and send the code using the Internet.
• Jan can send it in a secret puzzle box that can be opened without a key.
• Maria can smash the padlock with a hammer.

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?

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

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.

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?