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

I recently bought a book by Evdokimov, titled Hundred Colors of Math. The book has lovely math puzzles and cute pictures. The book has answers but doesn’t explain them. Also, the English translation is decent but not perfect. For these two reasons, I am not sure I would recommend the book. However, I do like the puzzles, and here is one of them, called Runaway Cell.

Puzzle. The figure depicted in the picture (a 6-by-6 square, in which the top row is moved by one square) was cut along the grid lines into several identical parts which could be put together to form a 6-by-6 square. The parts are allowed to be turned over. What is the minimal possible number of such parts?

I stumbled upon a cute puzzle on Facebook which originally came from a new book, Creative Puzzles to Ignite Your Mind by Shyam Sunder Gupta.

Puzzle. We have four identical boxes. One of the boxes contains three black balls (BBB), another box has two black and one white balls (BBW), the third box has one black and two white balls (BWW), and the last box has three white balls (WWW). Four labels, BBB, BBW, BWW, and WWW, are put on the boxes, one per box. As is often the case in such puzzles, none of the labels match the contents, and this fact is common knowledge. Four sages get one box each. Each sage sees his label but doesn’t know the other’s labels. Without looking in the box, each sage is asked to take out two balls and guess the color of the third ball. All the sages are in the same room and can hear each other and see the colors of the balls that are taken out.

• The first sage takes out two black balls and says, “I know the color of the third ball.”
• The second sage takes out one black and one white ball and says, “I know the color of the third ball.”
• The third sage takes out two white balls and says, “I don’t know the color of the third ball.”
• The fourth sage says, without taking out any balls, “I know the color of all the balls in my box and also the content of all the other boxes.”

Can you figure out what’s in the boxes?

I got immediately attracted to the puzzle Oleg Polubasov recently posted on Facebook.

Puzzle. A rectangular clearing in a forest is an N-by-M grid, and some of the cells contain a tower. There are no towers in the cells that neighbor the forest. A tower protects its own cell completely and parts of the eight neighboring cells at a depth of half of a cell. Here by neighbors, we mean the cells horizontally, vertically, and diagonally adjacent to the given cell. In particular, if each cell is one square unit, a tower protects four square units. The protected area forms a square with borders that lie in between the grid lines. A tsar knows the towers’ locations and wants to calculate the protected area. Prove that the following formula gives the answer: the number of 2-by-2 subgrids that contain at least 1 tower.

I like this puzzle because it has an elegant solution. But there is more. The puzzle reminds me of one of my favorite novels by Arkady and Boris Strugatsky: The Inhabited Island, also known as Prisoners of Power. This is a science fiction novel where Max Kammerer, a space explorer, ends up on a planet with desolate people who, twice daily, experience sudden bouts of enthusiasm and allegiance to the government. Later, it becomes clear that the love for the rulers comes from towers that broadcast mind-control signals suppressing critical thinking and making people prone to believe propaganda.

The novel was written in 1969 but accurately describes the modern Russian propaganda machine. It appears that there is no need for a secret signal. Just synchronized propaganda on government-controlled TV turns off people’s brains.

I agreed to review the book, The Raven’s Hat, because of the hats. I love hat puzzles. When I give them to my students, I bring hats to class to reenact the solutions.

The book contains eight awesome puzzles as well as ideas for playing with them. I both loved and hated this book. I loved it because it is great, and hated it because it isn’t perfect. Let me start with three places I didn’t like.

Consider a famous hat puzzle when there are hats of N colors. The sages are in a line, and hats are put on their heads. As usual, they are not allowed to give each other signals. Each of them has to announce their hat’s color, and they want to minimize the number of mistakes.

The big idea is to number the colors. The book suggests that the last sage in line calculates the total number of colors they see modulo N and announces the result to the rest. Then the others, starting from the end of the line, one by one, can calculate and name their hat colors. With this strategy, only the last sage in line might be mistaken.

This is a correct solution, but this is the first place I didn’t like. I prefer a different strategy, where everyone assumes that the total sum of the hat colors is 0 modulo N. In this case, every sage makes the same calculation: each sage sums up everything they see or hear and subtract the result from 0 modulo N. This solution is more elegant, since all the sages follow the same rule.

Then the book extends the same puzzle to an infinite number of sages. My second point of contention is that the authors think that, in this case, two sages might be mistaken. No. The answer is still the same, there is a strategy where not more than one sage is mistaken. See my blog post for the solution.

My third pet peeve happened when the authors introduced ballroom dancing in the puzzle on picture hanging. What is the connection between picture hanging and ballroom dancing? I’ll keep the book’s secret. My beef is with how the roles in ballroom dancing are described. Ballroom dancing is usually danced in pairs with asymmetric roles, which, in the past, were designated for males and females. Gender doesn’t play such a big role anymore; anyone can dance any role.

The authors are afraid to be politically incorrect by calling the dancers male and female. Instead, they say that the dancers dance male and female parts. Though formally, this choice of words might be politically correct, it still sounds awkward and draws attention to gender. If the authors ever talked to any person who has ever danced, they would have known that there is a much simpler way to describe dance roles. The dancers are divided into leaders and followers.

Did I ever tell you that reviewing my students’ writing is part of my job? So I am good at it and like critiquing other people’s writing. Now that my complaints are out, the issues with the book are actually minor.

The book is great. I even bought a second inflatable globe because of this book. The game, described in the book, is to rotate two globes randomly and then find a point on the globes in the same relative position towards the center. The game helped me teach my students that any movement of a sphere is a rotation.

My main goal in this post is to describe the only puzzle in the book that I haven’t seen before.

Puzzle. In a group of opera singers, there are two stars who are either friends or enemies. Surprisingly, only the host, who is not an opera singer, knows who the stars are and the nature of their relationship (the stars do not know that they are stars and whether or not they are friends). The group’s common goal is to identify the stars and to determine whether they are friends or enemies. To do so, they send a few of the singers to sing opera on a stage, which is divided into two halves: left and right. During the opera, the singers do not move between the halves. After the opera is over, the host classifies the opera. If there were no stars or only one star on stage, he classifies it as “neutral”. If both stars were on stage, the opera is a big success or a disaster. If both stars are friends and sing on the same half of the stage, or if they are enemies and sing on different halves, then the opera is a big success. Otherwise, it is a disaster.
What is the best strategy for a group of five singers to determine who are the stars and what is their relationship? What is the smallest number of operas they have to sing to guarantee that they can figure everything out?

It is weird that two people do not know whether they are friends. But sacrifices are needed for mathematics. I am excited that there is a nontrivial puzzle related to information theory, and it is ternary based. All other such puzzles I know are about weighing coins on a balance scale. I wrote too many papers about coin weighing. Now I can switch to opera singers with passionate relationships, secret from themselves.

What do you give a mathematician who likes only mathematics if you want to expand her geographical horizon? I just got such a gift: A math book that made me feel that I was in Australia. The book, A Dingo Ate My Math Book: Mathematics from Down Under, written by Burkard Polster and Marty Ross, has lovely essays, nice pictures, and a strong Australian flavor.

Alex Bellos sent me his new book Puzzle Ninja: Pit Your Wits Against The Japanese Puzzle Masters. What has he done to me? I opened the book and couldn’t close it until I solved all the puzzles.

This is a fantastic book. There are many varieties of puzzles, including some types that I’ve never seen before. Also, the beautifully designed puzzles are great. Often puzzles of the same type target different solving ideas or have varied cool themes.

This book is more than a bunch of puzzles; it also contains poetic stories about puzzle histories and Japanese puzzle designers. Fantastic puzzles together with a human touch: this might be my favorite puzzle book.

I present two puzzles from the book. The puzzle type is called Wolf and Sheep Slitherlink. The Slitherlink is a famous puzzle type with the goal of connecting some of the neighboring dots into a single non-self-intersecting loop. A number inside a small square cell indicates how many sides of the square are part of the loop. Wolf and Sheep Slitherlink is a variation of Slitherlink in which all sheep should be kept inside the fence (loop) and all the wolves outside.

Ignore the numbers in the title as they just indicate the order number of Wolf and Sheep Slitherlink puzzles in the book. The number of ninja heads shows the level of difficulty. (The hardest puzzles in the book have four heads.) The difficulty is followed by the name of the puzzle master who designed the puzzle.

The first puzzle above is slightly easier than the second. I like the themes of these two puzzles. In the first one, only one cell—lonely wolf—marks the relationship to the fence. In the second one, the wolf in the center—who needs to be outside the fence—is surrounded by a circle of sheep who are in turn surrounded by a circle of wolves.

The Best Writing on Mathematics 2016 is out. I am happy that my paper The Pioneering Role of the Sierpinski Gasket is included. The paper is written jointly with my high-school students Eric Nie and Alok Puranik as our PRIMES-2014 project.

At the end of the book there is a short list of notable writings that were considered but didn’t make it. The “short” list is actually a dozen pages long. And it includes two more papers of mine:

• Cookie Monster Plays Games—another PRIMES project written jointly with my high-school student Joshua Xiong.
• Mathematical Research in High School: The PRIMES Experience, written jointly with PRIMES Chief Research Advisor Pavel Etingof and PRIMES Program Director Slava Gerovitch.

To continue bragging, I want to mention that my paper A Line of Sages was on the short list for 2015 volume. And my paper Conway’s Wizards was included in the 2014 volume.Share:

I like Odd-One-Out puzzles that are ambiguous. That is why I bought the book Which One Doesn’t Belong? Look at the cover: which is the odd one out? The book doesn’t include answers, but it has nine more examples in each of which there are several possible odd-one-outs.Share:

Alex Bellos wrote a puzzle book Can You Solve My Problems? Ingenious, Perplexing, and Totally Satisfying Math and Logic Puzzles The book contains a mixture of famous puzzles and their solutions. Some of the puzzles are not mathematical in the strictest sense, but still have an appeal for mathematicians. For example, which integer comes up first when you alphabetize all the integers up to a quadrillion?

Recognize the puzzle on that book cover? You’re right! That’s my Odd One Out puzzle. Doesn’t it look great in lights on that billboard in London?

Mine isn’t the only terrific puzzle in the book. In fact, one of the puzzles got my special attention as it is related to our current PRIMES polymath project. Here it is:

A Sticky Problem. Dick has a stick. He saws it in two. If the cut is made [uniformly] at random anywhere along the stick, what is the length, on average, of the smaller part?

Share: