Tanya Khovanova's Math Blog

Here is a new puzzle by Nikolai Chernyatiev.

Puzzle. Five sages, who all know one another, are blindfolded, seated in a row in a dimly lit hall, and then have their blindfolds removed. Each sage can see both of their immediate neighbors, but no farther; the sages at the ends know that they are at the ends. After that, each sage writes down one of the numbers 1, 2, or 3. The complete information — who wrote which number, in seating order — is then announced to everyone.
Before being seated, the sages may agree on a rule for choosing 1, 2, or 3 based on what they see. After the five numbers are announced, each sage must reconstruct the full left-to-right order of all five sages.

I love puzzles related to information theory, and this is a lovely example. Let’s do a quick sanity check. There are 5! = 120 possible orders of the sages. The announced numbers form a ternary string of length 5, giving 3⁵ = 243 possible announcements. That is more than enough in principle; so far, so good.

AI can produce a possible table of answers, but the resulting strategy is not very inspiring. Fortunately, there is a much more elegant solution based on the following neat fact:

Among any three distinct residues modulo 5, exactly one is the average of the other two. Equivalently, any three vertices of a regular pentagon form an isosceles triangle: one of the three vertices lies on the axis of symmetry of the other two.

But wait: Konstantin Knop proved a much tighter result. Each sage can get away with writing down only one of two numbers. Wow!

Alexander Karabegov sends me new puzzles from time to time. This time, however, it is not a puzzle but a math joke.

Joke. If a woman gives birth to a child at the age of 30, then 60 years earlier, her child was twice as old as she was. Whatever that means.

I’ve been staring at my icosahedron, trying to solve the following puzzle by Konstantin Knop.

Puzzle. One face of an icosahedron is special. The numbers 2, 3, and 5 are written at its vertices in some order. All other vertices of the icosahedron are labeled with 1. In one query, we may ask an oracle for the product of the numbers assigned to any subset of icosahedron’s vertices. What is the minimum number of queries needed to determine the special face?

However, I misread the problem. I ended up solving a different puzzle instead—and had quite a bit of fun doing it.

Puzzle. One face of an icosahedron is special. The numbers 2, 3, and 5 are written at its vertices in some order. All other vertices of the icosahedron are labeled with 1. In one query, we may ask an oracle for the product of the numbers assigned to vertices of any one face of the icosahedron. What is the minimum number of queries needed to determine the special face?

I won’t post the solutions just yet, but let me begin with a simple observation: one question cannot possibly be enough. Indeed, with one question, the oracle’s answer must be a divisor of 30, and 30 has only 8 positive divisors. But an icosahedron has 20 faces, so a single question cannot distinguish among all possible choices for the special face.

Puzzle. A ball rolls forever on a frictionless billiard table with no pockets. Can you find a finite convex shape of the table for which no trajectory of the ball ever covers the entire surface?

I gave the following puzzle to my students.

Puzzle. A cowboy rides into town on Friday, stays for three days, then leaves on Friday. How come?

Most of them submitted the standard answer: his horse is named Friday.

One student suggested that the town was named Onfriday. This solution works well when the puzzle is given orally, but my homework was typed, so it feels less elegant.

Here are two more solutions that also work:

• He drank so much that he believed he stayed for three days, while in reality, the other four days were lost in a blackout.
• The cowboy left after three days, then later returned and left again on Friday.

And here is my favorite solution:

• The town has a quirky tradition: they celebrate fried foods and call the day Friday (get it?). The cowboy came for this special event, which happened to be held on a Tuesday.

I am so happy that I met Ivo David and Yogev Shpilman. Together, wrote the book Mathematical Puzzles and Curiosities, and had so much fun on the way. I have already mentioned one of the puzzles from the book on my blog—Two Points on a Cube. Here is another one.

Puzzle. Consider the sequence: O, T, R, F, I, S, ?
What letter should replace the question mark?

Puzzle. Two fathers gave money to their sons. The first father gave $200, and the second father gave $100. Yet the total amount received by the sons was only $200. How come?

Standard answer: There were three people: a son, his father, and his grandfather. The grandfather gave the father $200, and the father gave the son $100.

In many puzzles, my students come up with a surprising variety of alternative solutions—but not for this one. For many years of my teaching, this puzzle stayed untouched by new ideas. Perhaps the puzzle is simply too well known. But recently, I finally heard an alternative answer:

• The money was taxable.

In the homework for my STEP program, I gave the following challenge problem.

Puzzle. My sages each wear a hat of a different color. As in standard hat puzzles, they can see everyone else’s hat color. Unlike in many other hat puzzles, they know the color of their own hat as well. I announce which color each of them should end up wearing; this assignment is a permutation of the original colors. Each sage is allowed one swap of hats with another person per day. They have two days to rearrange the hats so that everyone ends up with the correct color. Can they do it?

Many students noticed that the permutation can be decomposed into disjoint cycles and suggested solving the problem cycle by cycle. A few of them even pushed this idea all the way to a complete solution. However, none of them connected the puzzle to a topic we had discussed in class: dihedral groups.

Here is an elegant way to finish the solution once the permutation is decomposed into cycles. A cyclic permutation on n elements can be viewed as a rotation of an n-gon. Any rotation of an n-gon can be written as a product of two reflections. Each reflection of an n-gon, viewed as a permutation, consists only of 1- and 2-cycles. Ta-da!

In a recent post, Each Point has Three Closest Neighbors, I mentioned the following conjecture.

Karabegov’s Conjecture. Any finite planar point configuration in which every point has exactly 3 closest neighbors must contain at least 16 points.

The conjecture was proposed by my dear friend Alexander Karabegov, whom I met in 1974. Wait. What?! I just realized that this was more than 50 years ago. How is that even possible?

After I posted the conjecture, we couldn’t resist working on it. We wandered through different types of graphs and found many cute definitions related to our problem.

A unit distance graph is formed from points in the plane by connecting two points whenever they are exactly distance 1 apart. A matchstick graph is a unit distance graph that can be drawn in the plane with edges of length 1 that do not cross. In other words, it is a unit distance graph that behaves nicely, by being planar. Think of laying matchsticks flat on a table: no overlaps, no chaos.

Here’s the difference visually: the left graph is a unit distance graph, while the right one is a matchstick graph.

Now for the star of the story. A penny graph connects two vertices if and only if their distance is the minimum distance among all pairs of vertices. The name is delightfully literal: imagine placing identical pennies at each vertex so that they do not overlap. Two pennies touch exactly when the corresponding vertices are connected by an edge. A penny graph is a special kind of matchstick graph: two vertices that are not connected are at a distance that is longer than the length of the matchstick.

Finally, a 3-regular graph is a graph where every vertex has degree 3. Three neighbors. No more, no less. They are also called cubic graphs. Not surprisingly, if the vertices of a cube are the vertices of our graph, and the edges of a cube are the edges of our graph, we get a 3-regular graph, as each vertex is incident to exactly 3 edges. Surprisingly, such graphs are not called tetrahedron graphs, as a tetrahedron, too, has each vertex incident to 3 edges. But the tetrahedron graph is special: it is a minimal 3-regular graph.

We wrote a paper Minimal 3-regular Penny Graph, in which we proved the conjecture. The conjecture has officially graduated to a theorem.

Theorem. The minimal 3-regular penny graph has 16 vertices.

Every year, after the PRIMES program begins, I send a letter to our students about how to read a math paper. The students in my group are juniors just starting their research. They are often required to read advanced math papers—frequently the first research papers they have ever encountered. This year, I decided to post my letter online, in case it might be helpful to other aspiring mathematicians.

Dear PRIMES and PRIMES-USA students,

Reading math papers can be very difficult and overwhelming. I remember trying to understand every single word of my first research paper and getting stuck on the first paragraph for a long time. That was a mistake. I regret that no one ever taught me how to read math papers. As the joke goes, “There are only two kinds of math books: those you cannot read beyond the first page, and those you cannot read beyond the first sentence.”

Math papers are not stories. They are not meant to be read linearly from beginning to end. Depending on your goal, you read different parts in different ways. Here are some examples.

Goal: Decide whether to read the paper.
Read: The abstract and parts of the introduction.

Goal: See what was accomplished.
Read: The introduction, or locate and read the main theorems.

Goal: Learn a method that might be useful.
Read: Find the relevant method and focus only on that section.

Goal: Get a general idea of the topic.
Read: First understand the structure of the paper. Then try to grasp the main statements at a high level.

Goal: Master the topic.
Read: Read the paper several times, going deeper with each iteration. Try not to get stuck on a sentence; you might understand it on another try. Here is a potential list of objectives for each iteration: you can adjust them and change their order according to your needs.

• First read: understand the structure and the big picture.
• Second read: understand the definitions and main notions.
• Third read: understand the main statements and look at small examples.
• Fourth read: understand the ideas behind the proofs.
• Fifth read: go deeper and start reading the referenced papers.
• Sixth read: try to reproduce the proofs.

Goal: Check for acknowledgments.
Read: The acknowledgments and citations.

The main rule is to keep your goal in mind while reading a paper. If you do not have a specific goal, ask your mentor to suggest exercises or questions to guide your reading. Try not to feel discouraged if you don’t understand everything: the joke at the beginning of this essay implies that everyone has trouble understanding math papers.

Tanya