Tanya Khovanova's Math Blog

A while ago I took writing lessons with Sue Katz. Below is my homework from 2010 (lightly edited). If I remember correctly, this piece was inspired by Sam Steingold.

—My friend Sam installed six locks on his door to protect himself from burglars.
—I know. I visited your friend. He has six very cheap locks. Any professional could open one in a second, so Sam’s door will only resist for six seconds.
—Yeah, but those locks aren’t completely identical. Three of them unlock with a clockwise motion, and three with a counterclockwise motion.
—So what? The thieves will just turn the lock mechanism whichever way it can be turned.
—Not so fast. Sam never locks all of them. Every time, he randomly picks which ones to lock.
—That might work, but what if he forgets which ones he locked?
—That’s okay, He remembers which way to turn every lock to unlock.

I love hat puzzles, and this one, posted on Facebook by Konstantin Knop, is no exception.

Puzzle. The sultan decided to test his three sages once again. This time, he showed them five hats: three red and two green. Each sage was blindfolded and had one hat placed on their head. When the sages removed their blindfolds, they could see the hats on the other sages but not their own. The twist in this puzzle is that one of the sages is color-blind and cannot distinguish red from green. The sages are all friends and are aware of each other’s perception of color. The sages are then asked, in order, if they know the color of their hats. Here’s how the conversation unfolded:

• Alice: I do not know the color of my hat.
• Bob: Me too, I do not know the color of my hat.
• Carol: Me too, I do not know the color of my hat.
• Alice: I still do not know the color of my hat?

The question is: Who is color-blind?

From time to time, the homework for my PRIMES STEP students includes questions that are not exactly mathematical. Last week, we had the following physics puzzle.

Puzzle. A fisherman needed to move a heavy iron thingy from one river’s shore to another. When he put the thingy in his boat, the boat lowered so much that it wasn’t safe to operate. What should he do?

The expected answer: He should attach the thingy to the bottom of the boat. When the object is inside the boat, the boat needs to displace enough water to account for the entire weight of the boat and the thingy. When the thingy is attached to the bottom of the boat, the thingy experiences its own buoyancy. Thus, the water level rises less because the thingy displaces some water directly, reducing the boat’s need to displace extra water. Thus, the amount of weight the fisherman saves is equal to the amount of water that would fit into the shape of this thingy.

As usual, my students were more inventive. Here are some of their answers.

• The fisherman could cut the iron thingy and transport it piece by piece.
• He can swim across and drag the boat with a rope with the thingy inside.
• He can use a second boat to pull the first boat with the thingy in it.
• It is another river’s shore, so he can just take the iron with him to a different river without going over water.
• If the fisherman has extra boat material, heightening the boat’s walls would keep it from sinking.

Also, some funny answers.

• He could fast for a few days, making him lighter.
• He could tie helium balloons to the boat to keep it afloat even after he gets in.
• Wait until winter and slide the boat on ice.

And my favorite answer reminded me of a movie I recently re-watched.

• You’re gonna need a bigger boat.

Before moving to the US, I attended the Gelfand seminar and took some pictures. I was a regular participant and have some bittersweet memories from that time. I’ve written about my experiences in several blog posts related to Gelfand, who was my advisor.

The year was 1990, and I just acquired my first camera. I was about to leave the USSR for the US and took a bunch of pictures of family, friends, and other moments. I wasn’t happy with the photos I captured at the seminar due to the poor quality of the camera and the dim lighting in the lecture hall. For context, the seminar was held on Mondays from 7 to 10 pm. So I put the pictures away and forgot about them.

Recently, I decided to digitize all of my old pictures. While the seminar photos are still grainy, they feel more precious now. Perhaps it’s the fact that they’ve survived for over 30 years, or maybe I’ve just grown more sentimental.

A big part of the seminar was the networking that happened beforehand. Although the seminar was scheduled to start at 7 pm, it often began at random times, anywhere between 7 and 8:30 pm. Gelfand disliked tardiness, so everyone would arrive by 7 and hang. All of my photos were taken before the seminar: some in the hallway and some in the seminar room.

In the last three pictures, the socializing had ended, and the seminar was about to start.

The term fibonometry was coined by John Conway and Alex Ryba in their paper titled, you guessed it, “Fibonometry”. The term describes a freaky parallel between trigonometric formulas and formulas with Fibonacci (F_n) and Lucas (L_n) numbers. For example, the formula sin(2a) = 2sin(a)cos(a) is very similar to the formula F_2n = F_nL_n. The rule is simple: replace angles with indices, replace sin with F (Fibonacci) and cosine with L (Lucas), and adjust coefficients according to some other rule, which is not too complicated, but I am too lazy to reproduce it. For example, the Pythegorian identity sin²a + cos²a = 1 corresponds to the famous identity L_n² – 5F_n² = 4(-1)ⁿ.

My last year’s PRIMES STEP senior group, students in grades 7 to 9, decided to generalize fibonometry to general Lucas sequences for their research. When the paper was almost ready, we discovered that this generalization is known. Our paper was well-written, and we decided to rearrange it as an expository paper, Fibonometry and Beyond. We posted it at the arXiv and submitted it to a journal. I hope the journal likes it too.

Consider the following Fibonacci trick. Ask your friends to choose any two integers, a and b, and then, starting with a and b, ask them to write down 10 terms of a Fibonacci-like sequence by summing up the previous two terms. To start, the next (third) term will be a+b, followed by a+2b. Before your friends even finish, shout out the sum of the ten terms, impressing them with your lightning-fast addition skills. The secret is that the seventh term is 5a+8b, and the sum of the ten terms is 55a+88b. Thus, to calculate the sum, you just need to multiply the 7th term of their sequence by 11.

If you remember, I run a program for students in grades 7 through 9 called PRIMES STEP, where we do research in mathematics. Last year, my STEP senior group decided to generalize the Fibonacci trick for their research and were able to extend it. If n=4k+2, then the sum of the first n terms of any Fibonacci-like sequence is divisible by the term number 2k+3, and the result of this division is the Lucas number with index 2k+1. For example, the sum of the first 10 terms is the 7th term times 11. Wait, this is the original trick. Okay, something else: the sum of the first 6 terms is the 5th term times 4. For a more difficult example, the sum of the first 14 terms of a Fibonacci-like sequence is the 9th term times 29.

My students decided to look at the sum of the first n Fibonacci numbers and find the largest Fibonacci number that divides the sum. We know that the sum of the first n Fibonacci numbers is F_n+2 – 1. Finding a Fibonacci number that divides the sum is easy. There are tons of cute formulas to help. For example, we have a famous inequality F_4k+3 – 1 = F_2k+2L_2k+1. Thus, the sum of the first 4k+1 Fibonacci numbers is divisible by F_2k+2. The difficult part was to prove that this was the largest Fibonacci number that divides the sum. My students found the largest Fibonacci number that divides the sum of the first n Fibonacci numbers for any n. Then, they showed that the divisibility can be extended to any Fibonacci-like sequence if and only if n = 3 or n has remainder 2 when divided by 4. The case of n=3 is trivial; the rest corresponds to the abovementioned trick.

They also studied other Lucas sequences. For example, they showed that a common trick for all Jacobsthal-like sequences does not exist. However, there is a trick for Pell-like sequences: the sum of the first 4k terms (starting from index 1) of such a sequence is the (2k + 1)st term times 2P_2k, where P_n denotes an nth Pell number.

You can check out all the tricks in our paper Fibonacci Partial Sums Tricks posted at the arXiv.

Have you heard of Grigori Perelman? If you like math, you probably have. He is one of the most renowned mathematicians in the world. I recently got a book on the Leningrad Mathematical Olympiads (scheduled for publication in English in 2025) and found Grigori’s name there. He authored one of the Olympiad problems from 1984. For context, he was born in 1966. Here it is.

Puzzle. You are given ten numbers: one “1” and nine “0”s. You are allowed to replace any two numbers with their arithmetic mean. What is the smallest number that can appear in place of the “1” after a series of such operations?

The famous 5-card trick begins with the audience choosing 5 cards from a standard deck. The magician’s assistant then hides one of the chosen cards and arranges the remaining four cards in a row, face up. Upon entering the room, the magician can deduce the hidden card by inspecting the arrangement. To eliminate the possibility of any secret signals between the assistant and the magician, the magician doesn’t even have to enter the room — an audience member read out the row of cards.

The trick was introduced by Fitch Cheney in 1950. Here is the strategy. With five cards, you are guaranteed to have at least two of the same suit. Suppose this suit is spades. The assistant then hides one of the spades and starts the row with the other one, thus signaling that the suit of the hidden card is spades. Now, the assistant needs to signal the value of the card. The assistant has three other cards than can be arranged in 6 different ways. So, the magician and the assistant can agree on how to signal any number from 1 to 6. This is not enough to signal any random card.

But wait! There is another beautiful idea in this strategy — the assistant can choose which spade to hide. Suppose the two spades have values X and Y. We can assume that these are distinct numbers from 1 to 13. Suppose, for example, Y = X+5. In that case, the assistant hides card Y and signals the number 5, meaning that the magician needs to add 5 to the value of the leftmost card X. To ensure that this method always works, we assume that the cards’ values wrap around. For example, king (number 13) plus 1 is ace. You can check that given any two spades, we can always find one that is at most 6 away from the other. Say, the assistant gets a queen of spades and a 3 of spades. The 3 of spades is 4 away from the queen (king, ace, two, three). So the assistant would hide the 3 and use the remaining three cards to signal the number 4.

I skipped some details about how permutations of three cards correspond to numbers. But it doesn’t matter — the assistant and the magician just need to agree on some correspondence. Magically, the standard deck of cards is the largest deck with which one can perform this trick with the above strategy.

Later, a more advanced strategy for the same trick was introduced by Michael Kleber in his paper The Best Card Trick. The new strategy allows the magician and the assistant to perform this trick with a much larger deck, namely a deck of 124 cards. But this particular essay is not about the best strategy, it is about the Cheney strategy. So I won’t discuss the advanced strategy, but I will redirect you to my essay The 5-Card Trick and Information, jointly with Alexey Radul.

63 years later, the 4-card trick appeared in Colm Mulcahy’s book Mathematical Card Magic: Fifty-Two New Effects. Here the audience chooses not 5 but 4 cards from the standard deck and gives them to the magician’s assistant. The assistant hides one of them and arranges the rest in a row. Unlike in the 5-card trick, in the 4-card trick, the assistant is allowed to put some cards face down. As before, the magician uses the description of how the cards are placed in a row to guess the hidden card.

The strategy for this trick is similar to Cheney’s strategy. First, we assign one particular card that the magician would guess if all the cards are face down. We now can assume that the deck consists of 51 cards and at least one of the cards in the row is face up. We can imagine that our 51-card deck consists of three suits with 17 cards in each suit. Then, the assistant is guaranteed to receive at least two cards of the same imaginary suit. Similar to Cheney’s strategy, the leftmost face-up card will signal the imaginary suit, and the rest of the cards will signal a number. I will leave it to the reader to check that signaling a number from 1 to 8 is possible. Similar to Cheney’s strategy, the assistant has an extra choice: which card of the two cards of the same imaginary suit to hide. As before, the assistant chooses to hide the card so that the value of the hidden card is not more than the value of the leftmost face-up card plus 8. It follows that the maximum number of cards the imaginary suit can have is 17. Magically, the largest possible deck size for performing this trick is 52, the standard deck of cards.

Last academic year, my PRIMES STEP junior group decided to dive deeper into these tricks. We invented many new tricks and calculated their maximum deck sizes. Our cutest trick is a 3-card trick. It is similar to both the 5-card trick and the 4-card trick. In our trick, the audience chooses not 5, not 4, but 3 cards from the standard deck and gives them to the magician’s assistant. The assistant hides one of them and arranges the other two in a row. The assistant is allowed to put some cards face down, as in the 4-card trick, and, on top of that, is also allowed to rotate the cards in two ways: by putting each card vertically or horizontally.

We calculated the maximum deck size for the 3-card trick, which is not 52, as for the 5- and 4-card trick, but rather 54. Still, this means the 3-card trick can be performed with the standard deck. The details of this trick and other tricks, as well as some theory, can be found in our paper Card Tricks and Information.

The famous 5-card trick begins with the audience choosing 5 cards from a standard deck. The magician’s assistant then hides one of these cards and arranges the remaining four cards in a row, face up. On entering the room, the magician can deduce the hidden card by inspecting the arrangement. To eliminate the possibility of secret signals between the assistant and the magician, the magician needn’t even enter the room — an audience member can call them and read out the row of cards.

We will not delve into the mechanics of the trick, which are widely available online. Instead, we will explore the information theory underlying it. Michael Kleber’s paper, The Best Card Trick, provides an information-theoretic argument that works as follows:

For a deck of N cards, the number of different messages the magician can receive is N(N-1)(N-2)(N-3). The magician must guess the hidden card, which is equivalent to determining the set of five cards chosen by the audience. The number of such sets is N choose 5. For the trick to work, the number of messages must not exceed the number of possible answers, leading to the inequality: (N choose 5) ≤ N(N-1)(N-2)(N-3). After some manipulation, we get that (N-4)/120 doesn’t exceed 1. This implies that the deck can have at most 124 cards. The bound turns out to be tight: as discussed in Kleber’s paper, the trick can still be performed with such a huge deck. The paper expands this argument to a trick with K instead of 5 cards and shows that the maximum deck size for such a trick is K! + K – 1.

Here, we want to present a more direct, intuitive argument. We will make the argument for the 5-card trick, which is easily generalizable to the K-card trick. The assistant has 5 ways to choose which card to hide and 24 ways to arrange the remaining four cards, so they only have 120 actions in any given situation. Ergo, the magician should only be able to extract 120 alternatives’ worth of information from knowing what action the assistant would take.

This is a bit fishy, because of course even with N > 120, the trick could happen to work sometimes. That is, if the magician tells the assistant the strategy by which they will guess the missing card, the assistant may, for some sets of 5 cards drawn even from a large deck, manage to show an arrangement of four that will lead the magician to guess correctly.

The crux of formalizing the argument is to move to the global view, but we can do that without additional computations. Consider the space of all states reachable by any strategy of the assistant. In our case, this is equivalent to ordered sequences of five cards, with the last face down. There are obviously (N-4)M of these, where M is the number of states the magician observes (four-card sequences, in our case), however many of those there are. When the assistant and the magician choose a strategy for the assistant, they make most of these impossible. Indeed, since the assistant always has exactly 120 options, after they have chosen one to take in each situation, we have exactly (N-4)M/120 states that remain possible with that strategy. For the trick to always work, this last expression must be no more than M; M cancels, saving us the trouble of computing it, and we are left with N-4 ≤ 120 as desired.

By the way, one of the authors of this essay, Tanya Khovanova, taught this trick to her PRIMES STEP students, who were students in grades 7 through 9. They found and studied interesting generalizations of this trick and wrote the paper Card Tricks and Information available at the arXiv. They studied many variations of the trick, including the ones where the assistant is allowed to put the cards face down. This interesting variation is outside the scope of this essay.

We would like to use as an example one of the tricks described in the paper: the K-card trick, where the assistant hides one card and arranges the rest in a circle. The implication is that when the audience member describes the arrangement to the magician, they describe the circle clockwise in any order. Our argument works here as follows. We count the number of the assistant’s actions: K ways to choose the hidden card and (K-2)! ways to arrange the cards in different circles up to rotation. Thus, the number of different actions is K(K-2)!. Hence, the deck size doesn’t exceed K(K-2)! + K – 1, as we can exclude the K-1 cards in the circle, as they aren’t hidden. Not surprisingly, this is the same formula as in the paper.

The puzzle In the Details by Derek Kisman is one of my favorite MIT Mystery Hunt puzzles of all times. I even wrote a blog post advertising it and another post with comments on the solution. This puzzle type became known as fractal word search.

In the standard word search, you have a grid of letters and a list of words. You need to find the words written in the grid in all eight directions. The unused letters provide the answer, or a clue to the answer, of the word search puzzle.

In the fractal word search, you have a grid of letters and a list of words. It looks like a regular word search, but you will not find all the words inside the given grid. The given grid is only a snapshot of the whole grid on some particular level k. To go to level k+1, you have to use replacement rules: each letter is replaced by a 2-by-2 block of letters. This creates a much bigger grid where you might find more words from the given list.

An interesting question is, where do you find the replacement rules? In Derek’s puzzle, the rules were not given, but the initial grid was level 2. So you could notice that this grid can be decomposed into 2-by-2 squares, and there are only 26 different squares, implying that each square corresponds to a letter. Assuming that replacing the 2-by-2 squares with correct letters will allow you to find more words from the list, you can decipher the replacement rules. This will allow you to get to level 1 as well as any other level. Small levels are easy to search, but on large levels, the grid gets so huge that it might not fit in the memory of a computer, or a million computers. That is why this puzzle was presented at the MIT mystery hunt, but not at any other puzzle hunt. It is quite difficult: one of the given words is hiding on level 86.

I liked the puzzle so much, I included it in one of my lectures. After I gave my talk at Brown University, a student, Klára Churá, approached me. She got as fascinated with the puzzle as I was. We ended up collaborating on the paper Fractal Word Search: How Deep to Delve. As the title suggests, we focused on finding the upper bound of the level where we could find a word of a given length. We had two parameters: the size of the alphabet n and the block size b used in the replacement rules.

For different reasons, the most interesting case is words of length 3. I will leave it to the reader to figure out why this is the most interesting case, or the reader can check our paper. We showed that any word of length 3 appears no later than level n³ + n² + 1.

When we posted the paper, I sent the link to Derek. He immediately wrote a program and showed that our bound is fairly tight. His code is available at GitHub. He created a configuration that puts a 3-letter word at depth LCM(a,b,c)+1, where a,b,c ≤ n-3. If n is even, this gives us a lower bound of (n-3)(n-4)(n-5) + 1. If n is odd, this gives us a lower bound of (n-4)(n-5)(n-6) + 1. In any case, asymptotically, it is very close to our upper bound.