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 homework I give to my students (who are in 6th through 9th grades) often starts with a math joke related to the topic. Once, I decided to let them be the comedians. One of the homework questions was to invent a math joke. Here are some of their creations. Two of my students decided to restrict themselves to the topic we studied that week: sorting algorithms. The algorithm jokes are at the end.

* * *

A binary integer asked if I could help to double its value for a special occasion. I thought it might want a lot of space, but it only needed a bit.

* * *

Everyone envies the circle. It is well-rounded and highly educated: after all, it has 360 degrees.

* * *

Why did Bob start dating a triangle? It was acute one.

* * *

Why is Bob scared of the square root of 2? Because he has irrational fears.

* * *

Are you my multiplicative inverse? Because together, we are one.

* * *

How do you know the number line is the most popular?
It has everyone’s number.

* * *

A study from MIT found that the top 100 richest people on Earth all own private jets and yachts. Therefore, if you want to be one of the richest people on Earth, you should first buy a private jet and yacht.

* * *

Why did the geometry student not use a graphing calculator? Because the cos was too high.

* * *

Which sorting algorithm rises above others when done underwater? Bubble sort!

* * *

Which sorting algorithm is the most relaxing? The bubble bath sort.

There are a lot of puzzles where you need to guess something asking only yes-or-no questions. In this puzzle, there are not two but three possible answers.

Puzzle. Mike thought of one of three numbers: 1, 2, or 3. He is allowed to answer “Yes”, “No”, or “I don’t know”. Can Pete guess the number in one question?

Yes, he can. This problem was in one of my homeworks, and my students had a lot of ideas. Here is the first list were ideas are similar to each other.

• I am thinking of an odd number. Is my number divisible by your number?
• If I were to choose 1 or 2, would your number be bigger than mine?
• If I were to pick a number from the set {1,2,3} that is different from yours, would my number be greater than yours?
• If I have a machine that takes numbers and does nothing to them except have a 50 percent chance of changing a two to a one. Would your number, after going through the machine, be one?
• If I were to choose a number between 1.5 and 2.5, would my number be greater than yours?
• If your number is x and I flip a fair coin x times, will there be at least two times when I flip the same thing?
• I am thinking of a comparison operation that is either “greater” or “greater or equal”. Does your number compare in this way to two?

One student was straightforward.

• Mike, please, do me a favor by responding ‘yes’ to this question if you are thinking about 1, ‘no’ if you are thinking about 2, and ‘I don’t know’ if you are thinking about 3?

One student used a famous unsolved problem: It is not known whether an odd perfect number exists.

• Is every perfect number divisible by your number?

Then, I gave this to my grandchildren, and they decided to answer in a form of a puzzle. Payback time.

• I’m thinking of a number too, and I don’t know whether it’s double yours. Is the sum of our numbers prime?

Here is the homework problem I gave to my PRIMES STEP students.

Puzzle. A man called his wife from the office to say that he would be home at around eight o’clock. He got in at two minutes past eight. His wife was extremely angry at this lateness. Why?

The expected answer is that she thought he would be home at 8 in the evening, while he arrived at 8 in the morning. However, my students had more ideas.

For example, one student extended the time frame.

• The man was one year late.

Another student found the words “got in” ambiguous.

• He didn’t get into his house two minutes past eight. He got into his car.

A student realized that the puzzle never directly stated why she got angry.

• The wife already got angry when he said he would be home around eight, as she needed him home earlier.

The students found alternative meanings to “called his wife from the office” and “minutes.”

• He had an office wife whom he called. But the wife at home was a different wife, and she was angry.
• “Two minutes past eight” could be a latitude.

One of the perks of being a teacher is receiving congratulations not only from family and friends, but also from students. By the way, I do not like physical gifts — I prefer just congratulations. Luckily, MIT has a policy that doesn’t allow accepting gifts of any monetary value from minors and their parents.

Thus, my students are limited to emails and greeting cards.

One of my former students, Evin Liang, got really creative. He programmed the Game of Life to generate a Christmas card for me. You can see it for yourself on YouTube at: Conway Game of Life by Evin Liang.

This is one of my favorite congratulations ever.

I like including warm-up puzzles with every homework.

Puzzle. Farmer Giles has four sheep. One day, he notices that they are all standing the same distance away from each other. How can this be so?

The expected answer: The configuration is impossible in 2D. So, one of the sheep is on a hill or in a pit.

Some students thought big: The sheep could be placed at different locations around the Earth, forming a really big tetrahedron. In this case, we need to explain what it means for the farmer to “notice”, but this minor issue could be resolved in many ways.

Some of the students questioned the meaning of the word distance. They argued that if sheep are all touching each other, they are the same distance 0 from each other. One way this could happen is if the tails of the four sheep were entangled.

My PRIMES STEP program consists of two groups of ten students each: the senior group and the junior group. The senior group is usually stronger, and they were especially productive last academic year. We wrote four papers, which I described in the post EvenQuads at PRIMES STEP. The junior group wrote one paper related to the game SOS. The game was introduced in the following 1999 USAMO problem.

Problem. The game is played on a 1-by-2000 grid. Two players take turns writing an S or an O in an empty square. The first player who produces three consecutive squares that spell SOS wins. The game is a draw if all squares are filled without producing SOS. Prove that the second player has a winning strategy.

The solution is quite pretty, so I do not want to spoil it. If my readers want it, the solution for this grid, and, more generally, for any grid of size 1-by-n, is posted in many places.

My students studied generalizations of this game, and the results are posted at the arXiv: SOS. We tried different target strings and showed that:

• The SOO game is always a draw.
• The SSS game is always a draw.
• The SOSO game is always a draw.

Then, we tried a version where the winner needed to spell one of two target strings. We showed that:

• The SSSS-OOOO game is always a draw.

We tried several more elaborate variations, but I want to keep this post short.

Here is another STEP homework question, which is a famous riddle.

Puzzle. Peter had ten cows. All but nine died. How many cows are left?

The wording is confusing on purpose. So, the students who are in a hurry subtract nine from ten and answer that only one cow is left. This answer is wrong. All but nine means that one cow died. So, the correct answer is nine.

One of my students decided that nine is the name of one of the cows, though it should have been capitalized. This means that all the cows except for Nine died, and only one cow, Nine, is left.

This student managed to find a legitimate explanation for the standard wrong answer.

I love the game of SET, where you have a specialized deck of 81 cards. The image on each card has four features: color, shape, shading, and the number of objects. Each feature can have three possible values. Three cards form a set if, for every feature, the values on the cards are either all the same or all different. One of the best properties of the sets is that, given any two cards, we can calculate the third card that would complete a set.

If we look at the game mathematically, we can assign a number 0, 1, or 2 for every feature value. For example, green could be 0, purple could be 1, and red could be 2. Then, the condition that, given a feature, three cards are either all the same or all different is equivalent to saying that the sum of the values modulo 3 is zero.

A mathematician would wonder, can we make a new game where we take values modulo 4? Each feature value should correspond to 0, 1, 2, or 3. For example, we can add a yellow color corresponding to number 3. The new “set” should be four cards such that the sum of the values modulo 4 is 0. This condition guarantees that any three cards could be uniquely completed into a “set”. But such a game is inelegant. For example, one green, two purple, and one red card will form a set. But one green, one purple, and two red will not. The symmetry between colors is lost.

I decided that there is no good analog for the game of SET that is played modulo 4. I was wrong. Here is a new game called EvenQuads. I heard about it at the 2022 MOVES conference.

The deck consists of 64 cards with three features: color, shape, and the number of objects. There are four values for each feature. Four cards form a quad if, for every feature, the values are all the same, all different, or half-and-half.

For example, the figure above shows a quad where, for each feature, all values are different. To get familiar with quads, here is a puzzle for you. How many quads can you find in the picture below?

The game proceeds in a similar way to the game of SET. You can find out more about EvenQuads at the EvenQuads website.

I picked this game as a research project for my senior STEP group. As many of you know, I have a program where we conduct mathematical research with students in grades 7 through 9. The group started in the fall of 2022 and was extremely productive. We wrote FOUR papers in an academic year, which is obviously our record. The papers can be found at the arXiv.

• In Card Games Unveiled: Exploring the Underlying Linear Algebra, we analyze four games related to linear algebra: SET, EvenQuads, Socks, and Spot It!. The games are so connected to each other that sometimes it is even possible to play one game using the cards from another game.
• In Quad Squares, we study semimagic, magic, and strongly magic quad squares made out of EvenQuads cards. A semimagic quad square is a 4-by-4 square in which each row and column form a quad. You can guess what a magic quad square is. The idea was inspired by magic SET squares: 3-by-3 squares where each row, column, and diagonal form a set. A magic SET square has an additional property: there are always four more sets in such a square located on broken diagonals. In other words, consider three cards and their coordinates in a square. These cards form a set if and only if the values of each coordinate are either all the same or all different. This property is stronger than the definition of a magic SET square. In the case of the game of SET, these two definitions are the same. However, for EvenQuads, we get two different definitions. This is how we ended up defining strongly magic quad squares. You can find the details in the paper.
• In EvenQuads Game and Error-Correcting Codes, we describe error-correcting codes based on a set of EvenQuads cards.
• In Maximum Number of Quads, we calculate the maximum possible number of quads, given n cards from an EvenQuads deck. For example, the puzzle pictured above is actually an example of the maximum possible number of quads among 7 cards. We generalize this idea to decks of any size. Unfortunately, our formula is based on a conjecture. Though, we strongly believe that our formula is correct.

My students did a great job.