Tanya Khovanova's Math Blog

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.

The fine tenacious boys nicely joke to hated servant girls sick for (absent) king.

The picture shows John Conway’s notes in my journal. They are the mnemonic for setting up his trick. For example, the word “tenacious” sounds similar to “ten” and “ace”. Hence, we arrange 13 cards in this order: 3, 5, 10, A, J, 9, joker, 2, 8, 7, Q, 6, and 4. We also put the king aside. The trick looks better if the cards are the same suit.

The fun part of the trick is the story he told while showing it. Unfortunately, I do not remember the story. My only other note says:

One, two, three are done by me. Four, five, six: they do the tricks. Seven, eight, play them straight. We all try nine for quite a long time. The king is back.

Here is my attempt to recover the trick. We arrange the cards in the above order. We keep the cards face down so that the three is on top. Now, we spell the word “ACE”, and for each letter, we move one card from the top to the bottom of the pile. Then, we flip the next card from the top of the pile, and “tada”, the card is an ace. We put it aside. Now, we repeat the process by spelling “TWO”, and the next card after that is a two. We do the same for “THREE”.

But, when we try the same process for “FOUR”, we get the joker instead. This is not surprising if you remember that “Four, five, six: they do the tricks”. We put the joker at the bottom of the pile and continue. In the next round, after spelling “FOUR” again, we get 4, which we put aside. We proceed by spelling “FIVE” and getting a joker, then getting 5 after the second spelling. The same happens with “SIX”. Then we continue with “SEVEN” and “EIGHT” without getting the joker.

Then, we try “NINE”, and get the joker. Then, we spell it again and again and keep getting the joker. Clearly, we are in a cycle that can go on forever. If you recall the quote, “We all try nine for quite a long time.” To get out of this cycle, we remember our king and put it on top of the pile when the joker is on the bottom. We start again. And now we can spell “NINE” and get 9. We are back to normal with “TEN”, “JACK”, and “QUEEN”, too. The king, however, appears on the second try after spelling “KING”, getting the joker, and spelling “KING” again.

I do not remember the details of John’s performance. I tried to find the trick online but only saw it briefly mentioned in Mathematics, Magic, and Mischief with John H. Conway.

Have you seen this trick? Any juicy details are welcome in the comments.

Recent Facebook Puzzle from Denis Afrisonov.

Puzzle. 100 students took a test where each was asked the same question: “How many out of 100 students will get a ‘pass’ grade after the test?” Each student must reply with an integer. Immediately after each answer, the teacher announced whether the current student passed or failed based on their answer. After the test, an inspector checks if any student provided a correct answer but was marked as failed. If so, the teacher is dismissed, and all students receive a passing grade. Otherwise, the grades remain unchanged. Can the students devise a strategy beforehand to ensure all of them pass?

(A small piece I wrote on Dec 29, 2009. Edited in 2024.)

They were black, very comfy, and felt like a second skin. The shoes had this shock-absorbing cushioning, so asphalt felt like carpet.

I had them for 10 years. They served me for so long that I started believing our happy relationship would last forever.

First, I noticed that they are not black anymore. They acquired a greenish color. Then, the sound changed. Steps started sounding like farts. I trusted my shoes so much that, at first, I thought I was just getting old. But I realized that I couldn’t be that perfect: I couldn’t possibly fart with such a precise rhythm. Besides, I should have run out of gas from time to time.

When I came home, I took off my shoes and looked at them. The sole of one shoe was gone. My love affair with my shoes was over. Oh well. The divorce was easy. They went to my garbage can. No tears, no broken hearts, just a lost sole.

I recently posted a symmetry puzzle from Donald Bell. He just sent me another one.

Puzzle. Start with a 30-60-90 triangle (half of an equilateral triangle). Divide it into two 30-60-90 triangles of different sizes by dropping a perpendicular from the right-angled corner to the opposite side. Put the resulting two pieces together to form a symmetrical shape. There are two solutions.

It took me some time to find the second solution. I love this puzzle.

Usually, I only post puzzles to which I know the solution. However, I don’t know the solution to this exciting geometry question from Facebook, yet. But I like the puzzle so much that I’d rather post it than wait until I find time to think about it.

Puzzle. A centrally-symmetric figure is cut into two equal polygons: A and B. Is it possible that the center of symmetry is in A but not in B?

I run a program at MIT called PRIMES STEP, where we conduct mathematical research with children in grades 6 through 9. Our first research project was about a funny coin called an alternator. This coin exists only in a mathematician’s mind as it can change weight according to its own will. When you put the alternator on the scale, it can either weigh the same as a real coin or a fake coin (the fake coins are lighter than real ones). The coin strictly alternates how much it weighs each time it is put on the scale. My colleague, Konstantin Knop, recently sent me a fresh alternator puzzle.

Puzzle. There are four identical-looking coins: two real, one fake, and one alternator. How do you find the alternator using a balance scale at most three times?

I am not as excited about the MIT Mystery Hunt as I used to be. So, for this year’s hunt, I didn’t go through all the puzzles but present here only the puzzles that were recommended to me. I start with math, logic, and CS.

• Scan, a bunch of numbers. The puzzle requires some programming.
• Flamingo, several grids that look like Nikoli puzzles.
• Jigsaw Slitherlink.
• Under Pressure, evaluating equations.

Then we have some word puzzles.

• Deposit at the Word Bank.
• Body Language, a crossword.
• Fren Amis, a crossword in many languages.
• Look Before You Leap, a crossword with seemingly meaningless clues.

Now, the rest.

• Queen Marchesa to g4 starts with a Magic-the-Gathering card showing a chess piece: white queen.
• New Rules, weird sentences about games.
• Itineratum de Urbes Universum, looks like Latin.
• Retro Chess Puzzle.