Tanya Khovanova's Math Blog

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:

• Fortune Cookies—Our team laughed at this one.
• No Clue Crossword—Our team was puzzled by this one.

Unfortunately math wasn’t prominent this year:

• Food Court—This is a probability puzzle that is surprisingly uninspiring. There is no mystery: the puzzle page contains a list of probability problems of several famous types. But this puzzles can find great use in probability classes.
• Torsion Twirl—Mixture of dancing and equations. I love it.
• People Mover—Logical deduction at the first stage.

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

• The Ferris of Them All—Several different Nikoli puzzles on a wheel.
• Toddler Tilt—Not exactly a Nicoli puzzle, but some weird logic on a grid, some music too.
• The Dollhouse Tour—Not exactly a Nicoli puzzle, but some weird logic on a grid, some pictures too.
• The Nauseator—The first part of the puzzle is a huge nonogram.
• Domino Maze—A non-trivial Thinkfun puzzle.
• Backlot—Finding a path on a grid with a fractal structure.
• Whale—Variation on Rush Hour.

Some computer sciency puzzles:

• Hackin’ the Beanstalk—Hidden algorithms.
• Turtle—LogoWriter.
• Bear—Origami.

Cryptography:

• The Scottish Display—You are given trigrams.
• Pig—The pigpen cypher.
• ANDARAC—You are given gibberish looking telegrams.

A couple of puzzles with the mathy side hidden:

• Tunnel of Love.
• Pied Piper—A puzzle type that I like and promoted is hidden here.

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.

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.

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.

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?

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

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?

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.

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?

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?

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?