Tanya Khovanova's Math Blog

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

My goal is to expand my students’ minds. So, though my STEP program is about mathematics, I sometimes give problems from other areas for homework. Here is a recent physics one.

Puzzle. You have a brick of 1 kilogram. How does the weight of the brick change during the year?

As always, my students generated tons of ideas about what can influence the weight.

• The Sun’s gravitational pull can influence the weight.
• The Moon’s gravitational pull can influence the weight.
• It would possibly decrease slightly due to factors such as weathering.
• During rainy days, it could absorb moisture and become heavier.
• Due to thermal expansion, the brick will be larger in the summer than in the winter, which means it displaces more air. As a result, it will weigh less in the summer.

I am not into physics. So, when I got these replies, I contacted a real physicist friend, Levy Ulanovsky. He referred me to Wikipedia: The first operational definition of weight was given by Euclid, who defined weight as: “the heaviness or lightness of one thing, compared to another, as measured by a balance.” This implies that when we talk of “weight”, we need to specify how we measure it. He continued by saying that the above ideas all make sense if we measure the weight force, e.g., by using a spring or pendulum frequency. Yet if our measurement is relative, e.g., by using a lever-like scale, then, for example, the sun’s gravitational pull is not a valid answer.

For example, if we measure the weight using a lever-like scale, with our brick on one side and a known weight combination on the other, then the weight reading on the moon will be the same as on Earth. If you use a spring, the weight will be different.

He added: People often use the words “weight” and “mass” interchangeably. But for teaching, you may wish to clarify that weight force is mg. A change in pendulum frequency shows a change in g, the acceleration due to gravity. A balance (lever-like) can show a change in m, the mass on one of its two plates relative to the mass on the other plate, with g equal at both ends. A spring, a rubber band, or a springboard can show a change in the weight force mg, whether caused by a change in m, in g, or in both m and g. Of the four student answers, the moon and sun change g; weathering and moisture change m; thermal expansion has several effects that interplay in a complicated way, so we’re better off forgetting about it.

I also asked Levy which effect is the strongest. His reply was: assuming a spring, a pendulum, or the like, the strongest effect is due to the Moon.

Here is a probability puzzle I heard from my son Sergei. We even included this puzzle in our book Mathematical Puzzles and Curiosities. Our book includes the answer but omits the details. So, this blog post is devoted to said details.

Puzzle. Alice rolls a die until she gets 6. Then Bob observes that she never rolled a 5.
Question. What is the expected number of times that Alice rolled the die?

The answer depends on Bob’s strategy. Many people assume that Bob loves 5 and is only looking for 5. In this case, the answer is 3. Here is the argument: the expected number of rolls to get 5 or 6 is 3: this is equivalent to rolling a three-sided die and waiting to one side to appear. Only on the rolls without 5 will Bob say something.

However, there are other natural assumptions. In the book, we have two suggestions, where Bob treats every digit that is not 6 equally.

Modeling assumption 1. Suppose Bob lists all the numbers that are missing. Then, when he says that 5 is missing, we are guaranteed that Alice rolled 1, 2, 3, and 4 before 6. Such a strategy by Bob noticeably increases the expected number of rolls, and the answer is 8.7. Let us prove this.

This version of the problem is related to the coupon collector’s problem. Suppose we randomly get coupons, where the total number of coupons is 5, and we get each one with probability 1/5. How many coupons will we need to collect to get 4 different coupons? The first coupon appears immediately after one draw; after that, a different coupon appears with probability 4/5, which means the expected additional wait is 5/4. After we get the second coupon, the expected wait for the third coupon is 5/3. Continuing, the total wait for four different coupons to appear is 5/5 + 5/4 + 5/3 + 5/2 = 77/12.

However, we actually need 4 different coupons, not out of 5, but out of 6 to appear. That means that we need to multiply the answer by 6/5 to get 7.7. Then we add one extra roll for the final 6. The answer is 8.7.

Modeling assumption 2. Suppose Bob randomly chooses one number out of the ones that are missing. For example, if Alice rolled 1, 2, 3, 2, 1, 6, then Bob notices that 4 and 5 are missing, and mentions 5 with probability 1/2. In this case, the number of expected rolls is 4.26.

By using coupon-collecting ideas, we know, for each k, the expected number of rolls until k+1 distinct dice faces appear. To wit, for each k=0,1,2,3,4, the expected number of rolls is 1, 2.2, 3.7, 5.7, and 8.7, respectively.

Now we need to condition on the event that Bob actually says 5. By symmetry among the non-6 faces, the probability that Bob’s announcement is 5, given that he says something at all, is the same for each of the five digits. This conditioning does not bias the waiting time toward any particular missing digit, so the conditional distribution of the stopping time is obtained by averaging these expectations over the five possible values of k. Therefore, the expected number of rolls is (1 + 2.2 + 3.7 + 5.7 + 8.7)/5 = 4.26.

I am grateful to my other son, Alexey, for discussing this problem with me. Probability is a tricky subject, and it is nice to have experts in the family.

I wrote a book. This is my first book, so I am very proud. I wrote it together with two brilliant puzzle lovers, Ivo Fagundes David de Oliveira and Yogev Shpilman. The book is published by World Scientific and is available for pre-order: Mathematical Puzzles and Curiosities. Here is one sample puzzle from the book.

Puzzle. The centers of two opposite faces of a cube are connected by four distinct shortest paths, shown in the picture in different colors. Can you find two points on the surface of a cube such that there are exactly three shortest paths connecting them?

This puzzle appeared in the latest issue of SLMath’s newsletter, 17 Gauss Way. The issue has a puzzle column that I coauthored with Joe Buhler and Pavlo Pylyavskyy. The coolest images in the column were done by Tracy Hicks, and this image is no exception. The picture is better than our original one in the book.