Tanya Khovanova's Math Blog

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.

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

My readers know that I love hat puzzles. This is why I decided to turn a number trick by Konstantin Knop (in Russian) into a hat trick.

Hat Trick. The audience has a bottomless supply of hats in ten different colors. They arrange ten people in a line and put one of the hats on each person. Then the magician’s assistant comes in and removes a hat from one of the ten people. After that, the magician appears and, abracadabra, guesses the color of the removed hat. The magician and the assistant agreed on a strategy beforehand. What is it?

Keep in mind that this trick won’t work with fewer than ten colors. As a bonus, can you explain why?

Sep 18, 2022 Correction: I meant “with fewer than ten people.”

To prepare for this magic trick, take all the spades out of a deck and place them in the following order: seven, ace, queen, two, eight, three, jack, four, nine, five, king, six, and ten. Turn the assembled deck face down, so that the seven is on top. Now you are ready to do the trick.

Magic trick. Transfer the top card to the bottom of your deck and deal the new top card face-up on the table. Repeat this process until all the cards are dealt. And — abracadabra — the cards are dealt in order.

I showed this trick to my grandchildren, and they decided to reproduce it. They tried to calculate where each card goes, without too much success. Then my son showed them another trick: how to arrange the cards without calculation. He started building his arranged deck from the end of the trick with all the cards in order face-up on the table with the king on top. He took the king and put it face-down into his hand. Then he repeated the following procedure until all the cards were in his hand: He took the next card from the table and put it face-down on top of the one in his hand. Then he moved the card from the bottom of his deck to the top. And — abracadabra — the cards are arranged correctly for the trick.

Next time, I should ask my grandkids to show this trick with the whole deck.

Pete McCabe presented his trick, Persistimis Possessiamo, at the Gathering for Gardner in 2018.

Trick. Pete asked for two volunteers, let’s call them Alice and Bob. Bob took out his favorite card, the Queen of Spades, from the deck and put it back following Pete’s instructions. Then Alice dealt the deck alternatively into two piles, Bob’s and hers, starting with Bob’s. Alice took her pile and repeated the same process several times until only one card was left. And, abracadabra: it was Bob’s chosen Queen of Spades.

Pete McCabe is interested in scripting magic. In his blog post, Scripting Magic for Zoom, he describes ways to make sure that Bob inserts his card into the 22nd place without using sleight of hand, but rather using a theatrical script which makes the process magical rather than mathematical. The magic part is related to the fact that the number of letters in the trick title, Persistimis Possessiamo, is 22. As a result, he can do the trick on Zoom without ever touching the cards.

Once a magician knows how to manipulate the volunteer to insert the card into a specific place in the deck, the trick becomes deterministic and works on any-sized deck, as long as the magician can calculate where the card goes. We will now perform this calculation.

We denote our card-inserting sequence as a(n), where n is the size of the deck, and a(n) is the place where the card is inserted. For starters, a(2n+1) = a(2n): when the size of the deck is odd, the last card during the first deal goes to Bob, and doesn’t effect the other deals. Now, we obviously have a recursion. First, we observe that in order to end up in Alice’s pile after the first deal, Bob’s chosen card should occupy an even-numbered place. Suppose we start with 2n cards. After the first deal, Bob’s chosen card is in the place number a(2n)/2 from the bottom in Alice’s pile. That means, the card is in the place number n + 1 − a(2n)/2 from the top. This gives us an equation: a(n) = n + 1 − a(2n)/2, which is equivalent to a recursion: a(2n) = 2(n + 1 − a(n)).

Given that each element of the sequence a(n) is doubled, we are only interested in even-indexed values. Consider b(n) = a(2n) = a(2n+1). Then b(1) = 2, and the recursion for b is b(n) = 2(n + 1 − b⌊n/2⌋).

From here, we get the sequence, which is now sequence A350652 in the OEIS:

2, 2, 4, 6, 8, 6, 8, 6, 8, 6, 8, 14, 16, 14, 16, 22, 24, 22, 24, 30, 32, 30, 32, 22, 24, 22, 24, … .