Tanya Khovanova's Math Blog

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.

Who will be Champion?

I stumbled on this puzzle on Facebook the day of the World Cup finals. How timely!

Puzzle. Sixteen teams play a single-elimination tournament, where the losing team is immediately out. The teams have different rankings, and a higher-ranking team always wins against a lower-ranking team. The initial seeding is random.
In the semifinals, A won against B, and C won against D. Given that B is stronger than D, what is the probability that A will become the champion?

Consider a group of people in which some are friends. We assume that friendship is symmetric: if Alice is Bob’s friend, then Bob is Alice’s friend. That means we can build a friendship graph where vertices are people and edges correspond to friendships. Let’s assume that every person has at least one friend, so the friendship graph doesn’t have isolated vertices.

Darla needs to conduct research by surveying random pairs of friends. But first, she has to find those pairs. To ensure that the pairs are randomly selected, she must pick two random people from the group, contact them, and ask them whether or not they are friends. If they are, she gives them her questionnaire. If not, Darla wasted tons of time and had to keep looking.

The group she is surveying is enormous. So, when she picks two random people, they typically have never even heard of each other. Bother!

Darla decides to speed up the process. She would pick a random person, ask them for a list of friends, and then randomly pick one person from the list. Since every person has at least one friend, Darla always ends up with a filled questionnaire.

Puzzle question. Why is Darla’s method wrong? Can you describe the pairs of friends her method favors?

As my readers know, I run a PRIMES STEP program, where we conduct mathematical research with students in grades 6 through 9. Last year, our junior group wrote the paper, The Struggles of Chessland, which is now posted on the arXiv.

This is the funniest paper ever written at PRIMES STEP. In the paper, the King, with his self-centered Queen and their minions, try to protect their lands in the Bermuda triangle, called the Chessland, which consists of square islands of different sizes.

In the first part of their fairy tale, the King, his lazy Queen, and other chess pieces are trying to survey their islands. The first volunteer for this surveying job is the Knight. The Knight starts somewhere on an island and walks around it by using the knight’s moves in chess. The goal is to see every cell, and a Knight can see all cells that are a knight’s move away from where he is standing. In other words, every cell is either visited by the Knight or is one knight’s move away from a visited cell. In mathematical terms, the Knight walks a path that is a domination set on a knight’s graph.

The students found a lot of such paths. The picture shows a surveying path for the Knight for the island of size 7. The students called this pattern a shoelace pattern. They used similar shoelaces to survey any island of size 7 or larger. However, when I look at the picture, I see a cat.

Other chess pieces survey the land too. Funnily, the King surveys better when he is drunk. Do you know why? Take a look at the paper.

After all the islands had been surveyed, enemy spies started to appear in Chessland, and our band of chess pieces tried to trap them. My students invented the rules for trapping enemies. An example of the black Queen being trapped is in the picture below, and the rules are the following. Wherever the black Queen might move, should be under attack by a white queen. Also, white queens can’t directly attack the black Queen, or each other.

Oh! I forgot to mention: the trapping should use as few white queens as possible. Also, if the enemy is not a queen but another kind of chess piece, it can only be trapped by its own kind.

The trapping can be described in terms of graph theory. The black Queen is located at a vertex of the queen’s graph. The white queens should be positioned at vertices in such a way that they are not neighbors of the black Queen or each other. In addition, any vertex that is a neighbor of the black Queen, has to be a neighbor of at least one white queen.

This year’s PRIMES STEP project was a real chess adventure!

The 2018 International Collegiate Programming Contest (ICPC) had a very hard problem which is of interest to mathematicians. The problem was proposed by super-coder Derek Kisman. Here is the problem as it was presented at the contest.

Problem J. Uncrossed Knight’s Tour. A well-known puzzle is to “tour” all the squares of an 8 × 8 chessboard using a knight, which is a piece that can move only by jumping one square in one direction and two squares in an orthogonal direction. The knight must visit every square of the chessboard, without repeats, and then return to its starting square. There are many ways to do this, and the chessboard size is manageable, so it is a reasonable puzzle for a human to solve.

However, you have access to a computer, and some coding skills! So, we will give you a harder version of this problem on a rectangular m × n chessboard with an additional constraint: the knight may never cross its own path. If you imagine its path consisting of straight line segments connecting the centers of squares it jumps between, these segments must form a simple polygon; that is, no two segments intersect or touch, except that consecutive segments touch at their common end point. This constraint makes it impossible to visit every square, so instead you must maximize the number of squares the knight visits. We keep the constraint that the knight must return to its starting square. Figure J.1 shows an optimal solution for the first sample input, a 6 × 6 board.

The input consists of a single line containing two integers m (1 ≤ m ≤ 8) and n (1 ≤ n ≤ 10¹⁵), giving the dimensions of the rectangular chessboard.

Mathematicians know many things about knight tours on a standard 8 × 8 chessboard. But one of the limits in this puzzle is so huge, that the answer to this computational puzzle constitutes a new mathematical discovery. Unsurprisingly, no one solved this puzzle during the contest. A well-written solution summary is available on the ICPC website. The solution requires dynamic programming and a realization that tours have to have repeating patterns.

Since no one solved this problem during the competition, it is useful that, in addition to the solution summary, Derek posted his innovative code online. The two figures below (courtesy of Derek Kisman) show his answer for the longest closed tour on a 6 × 24 board and the longest open tour on a 6 × 26 board.

Derek got interested in uncrossed knight’s tours after reading my blog post, 2014 Math Festival in Moscow, where I presented the following problem given at that festival to 7th graders.

Problem. Inside a 5 × 8 rectangle, Bart draws closed paths that follow diagonals of 1 × 2 rectangles. Find the longest possible path.

The 2014 Math Festival organizers offered an extra point for every diagonal on top of 16. It is funny that the organizers obfuscated that it is useless to try and find 17 diagonals, as the number of diagonals has to be even. The official solution, shown below, had 24 diagonals.

In the solution booklet, the organizers mentioned that they did not know the best answer to their own question. They hoped that the longest possible path matched their official solution.

In Derek’s notation, the above problem is equivalent to finding the largest uncrossed knight’s closed tour on a 6 × 9 grid. And Derek proved that, indeed, 24 is the largest tour. While proving this, he also calculated the answer for gazillions of other boards.

We can go further: beyond gazillions. Let’s consider what happens on m × n boards, where m is fixed, and n is astronomically large. Suppose f_m(n) is the largest size of an uncrossed knight’s closed tour on the m × n board and g_m(n) is the largest size of an uncrossed open tour.

The answer has repeating patterns everywhere except around the ends of the board. We would expect that the number of possible repeating patterns is finite. Moreover, for large boards, only the densest patterns would appear. This means that asymptotically, both functions f and g are linear functions of n. On top of that, as each pattern is periodic, the behavior at the ends of the long boards should become periodic as well. Hence, the difference functions of f and g for fixed m would eventually become periodic. (Here, the f’s difference function, which I denote D(f_m) is defined as follows: D(f_m)(n) = f_m(n+1) – f_m(n).)

That means we can solve a more difficult problem. We do not need the limits for n. It should be possible to calculate these functions for a given m and any n (even if n is way more than a gazillion). I am being over-optimistic here. First, we need some mathematical theory to find the bounds for where the periodic behavior has to start and estimate the size of the period. Suppose we can prove that for D(f₆)(n), the eventual period has to start before n reaches A, and the length of the eventual period is not more than B. Then, we need to calculate the A + 2B values of the function f₆(n) to know the function for any n.

Derek actually calculated the functions f_m(n) and g_m(n) for m up to 9 and n up to infinity. More precisely, he found the cycles I am describing above. What a mindblowing achievement!

My former IMO coach, Gregory Galperin, converted a famous joke into a logic puzzle, adding a variation.

Puzzle. Ten logicians walked into a cafe. Each knew whether they wanted tea or coffee, but no one knew each other’s preferences. When they sat at a table, the waiter asked loudly, “Will everyone be having coffee?” Then the waiter went around the table, writing down each person’s answer.
There were three possible answers: “I don’t know”, “Yes”, and “No”. All answers were truthful and spoken loudly so that all group members heard them.

1. Suppose the first nine people said, “I don’t know”, and the tenth person said, “Yes”. How many of them wanted coffee?
2. Suppose the sixth and the seventh answers were not the same. How many people said, “I don’t know”, how many said, “No”, and how many said, “Yes”. Find the smallest number of people who for sure would have ordered coffee and the smallest number who for sure would have wanted tea?

Here are some problems that I liked from the YuMSh (Youths Math School in St. Petersburg) Olympiad.

Problem for 6th grade. Twenty people from an island of knights and knaves have a party. Knights always tell the truth, and knaves always lie. Each party-goer got a card with a different number from 1 to 20. When they were asked about their numbers, each answered with a number from 1 to 20. The sum of all the answers is 156. What is the minimum possible number of liars that have to be at the party?

Problem for 7th grade. Alice and Bob bought a deck of playing cards (52 cards total) and took turns gluing the cards on the wall one at a time. Alice was first. The game is lost if, after a move, the wall has 4 cards of the same suit or 4 cards of consecutive values (for example, 8-9-10-jack). Can Alice or Bob guarantee themselves a win, regardless of their opponent’s moves?

Problem for 7th grade. Buddhist monks gather in an infinite cave where a finite number of prime numbers are written on the wall. The numbers might not be distinct. Every second, one of the monks performs one of the following operations.

1. Adds to one of the numbers one of its digits.
2. Shuffles the digits of one of the numbers.

Every time they do it, they erase the old number and write the new one. The rule is that the new number has to be greater than the old one. If a composite number gets written on the wall of this cave, then the world collapses into nothingness. Can the monks save the world for eternity?

Problem for 8th grade. The incenter of a triangle is equidistant from the midpoints of the sides of the triangle. Prove that the triangle is equilateral.

Problem for 9th grade. Bob was given 30 distinct natural numbers. He wrote down all the 435 pairwise sums. It appears that among those sums, 230 are divisible by 3. How many of the original 30 numbers are divisible by 3?

I recently posted a cute puzzle about poisoned wine. Today, I would like to discuss this puzzle’s variation with N total glasses, of which two are poisoned.

Puzzle. N glasses of wine are placed in a circle on a round table. S sages are invited to take the following challenge. In the presence of the first sage, N − 2 glasses are filled with good wine and the other two with poisoned wine, indistinguishable from the good wine. After drinking the poisoned wine, the person will die a terrible tormented death. Each sage has to drink one full glass. The first sage is not allowed to give any hints to the other sages, but they can see which glass he chooses before making their own selection. The sages can agree on their strategy beforehand. For which S can you find a strategy to keep them all alive?

What does this have to do with rulers, and what are those? I am grateful to Konstantin Knop for showing me a solution with rulers. But first, let’s define them.

A sparse ruler is a ruler in which some distance marks may be missing. For example, suppose we have a ruler of length 6, with only one mark at a distance 1 from the left. We can still measure distances 1, 5, and 6. Such a ruler is often described as {0,1,6} to emphasize its marks, endpoints, and size.

A complete sparse ruler is a sparse ruler that allows one to measure any integer distance up to its full length. For example, the ruler {0,1,6} is not complete. It can’t measure distances 2, 3, and 4. Thus, if we add the marks at 2, 3, and 4, such a ruler becomes complete.

A complete sparse ruler is called minimal if it uses as few marks as possible. In our previous example, the ruler {0,1,2,3,4,6} is not minimal. The distance between marks 1 and 4 is 3, so if we remove mark 3, we can still measure any distance. We can remove mark 2 too. The ruler {0,1,4,6} with marks 1 and 4 is minimal.

Oops. I forgot that we have a round table. This means we need to look at cyclic rulers: the idea is the same, but the numbers wrap around. For example, consider the cyclic ruler {0,1,4,6} of length 6, where 0 and 6 is the same point. This ruler has three marks at 0, 1, and 4.

Going back to the puzzle, suppose N = 6, aka there are six glasses around the table. The sages need to agree on a complete cyclic ruler, for example, the one described above. As this ruler contains any possible difference between the marks, the first sage can mentally place the ruler on the table so that the marks cover poisoned glasses. He signals the position of the ruler by drinking his glass. The sages can agree that the glass drunk by the first sage corresponds to position −1 on the ruler, and the other sages avoid the first, second, and fifth glass clockwise from the chosen glass.

In this case, three glasses are not covered by the ruler’s marks. This means three sages can be saved.

To summarize, the sages need a complete ruler, as such a ruler can always cover two glasses at any distance from each other with its marks. The number of sages that can be saved by such a ruler is N minus the number of marks. To save more sages, we want to find a minimal ruler.

There are actually more cool rulers. A ruler is called maximal if it is the longest complete ruler with a given number of marks. For example, the non-cyclic ruler {0,1,4,6} is maximal. A ruler is optimal if it is both maximal and minimal. Thus, the ruler {0,1,4,6} is also optimal.

There are other types of rulers called Golomb rulers. They require measured distances to be distinct rather than covering all possibilities. Formally, a Golomb ruler is a ruler with a set of marks at integer positions such that no two pairs of marks are the same distance apart. If, however, a Golomb ruler can measure all the distances, it is called a perfect Golomb ruler. As we can deduce, a perfect Golomb ruler is a complete sparse ruler. I leave it to the reader to show that a perfect Golomb ruler must be a minimal complete sparse ruler.

The rulers rule!

I wrote a lot about the inventiveness of my students. Here is more proof.

Puzzle. A police officer saw a truck driver going the wrong way down a one-way street but didn’t try to stop him. Why?

Many of my students came up with the expected answer:

The truck driver was walking.

They also found some legit ways for a truck driver to not be stopped.

• The police officer was too far away.
• There was construction nearby, so the police officer directed the driver to drive the wrong way.
• The truck was a fire truck responding to an emergency.
• The driver bribed the police officer.
• The driver was a kid playing with a toy truck.

Some more ideas, rather far-fetched.

• The police officer was off duty, so he called another police officer to stop the driver.
• The truck driver was going too fast to stop.
• The police officer was responding to a bank robbery, and stopping the truck driver was not high priority.
• The police officer was driving the wrong way too, and it would be hypocritical to stop the truck driver.
• The street was a dead end, and the only way out was to go the wrong way.

Some funny ones.

• The police officer had a history of hallucinating and thought the truck driver was a figment of his imagination.
• The police officer was a ghost.
• The police officer was the truck driver.
• The police officer was busy eating a donut.
• The truck driver was the police officer’s boss.
• The truck driver was the police officer’s grandma.

I often receive letters from parents of math geniuses — “My twelve-year-old is reading an algebraic geometry book: accept him to PRIMES,” or “My ten-year-old finished her calculus course: here is her picture to post on your blog,” or “My two-year-old knows the multiplication table, can you write a research paper with him?” The last letter was a sarcastic extrapolation.

I am happy to hear that there are a lot of math geniuses out there. They are potentially our future PRIMES and PRIMES STEP students. But, it is difficult to impress me. The fact that children know things early doesn’t tell me much. I’ve seen a student who didn’t know arithmetic and managed to pass calculus. I’ve also met a student claiming the full knowledge of fusion categories, which later appeared to be from half-watching a five-minute YouTube video.

There are a lot of products catering to parents who want to bring up geniuses. My grandson received a calculus book for his first birthday: Introductory Calculus For Infants. Ten years later, he still is not ready for calculus.

Back to gifted children. Once a mom brought us her kid, who I can’t forget. The child bragged that he solved 30 thousand math problems. What do you think my first thought was? Actually, I had two first thoughts: 1) Why on Earth would anyone count all the problems they solved? 2) And, what is the difficulty of the problems he solved 30 thousand of?

From time to time, I receive an email from a parent whose child is a true math genius. My answer to this parent is the same as to any other parent: “Let your child apply to our programs. We do a great job at working with math geniuses.”

Our programs’ admissions are done by entrance tests. Surprisingly, or not surprisingly, the heavily advertised kids often do poorly on these tests. It could be that the parents overestimate their children’s abilities. But sometimes, the situation is more interesting and sad: I have seen children who sabotage the entrance tests so as not to be accepted into our programs. We also had students give us hints on their application forms that they were forced to apply.

In the first version of this essay, I wrote funny stories of what these students did. Then, I erased the stories. I do not want the parents to know how their children are trying to free themselves.

Dear parents, do not push your children into our programs. If they do not want to be mathematicians, you are decreasing their chances of getting into a good college. Imagine an admission officer who reads an essay from a student who wants to be a doctor but wastes ten hours a week on a prestigious math research program. Such a student doesn’t qualify as a potential math genius, as their passion lies elsewhere. Nor does this student qualify as a future doctor, as they didn’t do anything to pursue their claimed passion. In the end, the student is written off as a person with weak character.

On the other hand, the students who do want to be in our programs, thrive. They often start breathing mathematics and are extremely successful. Encourage your children to apply to our programs if they have BOTH: the gift for mathematics and the heart for it.