This blog has a modern version at http://blog.tanyakhovanova.com/, where you can leave comments. This page contains the copies of recent blog entries. The older copies are here:
I like pets, but, for various reasons, I can't have one. So I flirt with other people's pets. There is a black cat across the road who likes sitting in my driveway. So I had to buy a new car with a backup camera to make sure the cat is safe. As you can imagine, I couldn't skip this problem about cats posted by Konstantin Knop on Facebook.
Puzzle. One cat eats one stick of sausage in 27 minutes. You have four identical sticks of sausage and five cats. Using only the cats and the sausages, measure exactly one minute.
All the cats eat at the same constant rate, and all the sausage sticks are identical. You may measure time intervals only between moments when cats finish sausage sticks. At each such moment, you may redistribute the cats among the remaining sausage sticks.
Let me begin with labeled chip-firing on an infinite directed binary tree, where the root is at the top. Place 2n chips, labeled from 0 to 2n − 1, at the root. A move consists of choosing any two chips at the same vertex and firing them: the smaller chip goes to the left child, and the larger chip goes to the right child. For k ≥ 2, the k-ary version is exactly what you would guess. Start with kn chips, labeled from 0 to kn − 1, at the root. When a vertex fires, choose k chips and send them, from smallest to largest, to its k children from left to right.
The process eventually stops. At that point, there is exactly one chip at every vertex n edges below the root. If we erase the labels, the final configuration is always the same. With the labels, however, our choices matter. Reading the chips on the final layer from left to right gives a permutation of the numbers from 0 to kn − 1.
Let us play with eight chips, labeled 0 through 7, on a binary tree. Here is one particularly orderly strategy. At the root, fire the pairs
(0, 4), (1, 5), (2, 6), (3, 7).
The left child receives chips 0, 1, 2, and 3, while the right child receives chips 4, 5, 6, and 7. Continue in the same spirit. At every vertex, pair the smaller half of its chips with the larger half, in order. Each vertex then sends its smaller half to the left and its larger half to the right. In the final configuration, the chips appear as
0, 1, 2, 3, 4, 5, 6, 7.
This is, of course, the lexicographically earliest possible permutation. It is difficult to beat being completely sorted.
What about the lexicographically latest possible permutation? This time, at every vertex, list the chips in increasing order and pair neighboring entries. At the root, we fire
(0, 1), (2, 3), (4, 5), (6, 7).
Thus, the left child receives the even-numbered chips, while the right child receives the odd-numbered chips. We continue in the same way. The left child fires the pairs (0, 2) and (4, 6), while the right child fires the pairs (1, 3) and (5, 7). Continuing to the last layer gives the permutation
0, 4, 2, 6, 1, 5, 3, 7.
For eight chips, this is the lexicographically latest attainable final configuration.
Here is the cool part. Write the labels in binary. Our final permutation becomes
000, 100, 010, 110, 001, 101, 011, 111.
Now reverse the bits in every string. We get
000, 001, 010, 011, 100, 101, 110, 111.
Aha! These are simply the numbers in their usual order.
This permutation has the rather grand name of a radix-2 digit-reversal permutation. In base 2, it is usually called a bit-reversal permutation.
The binary notation also explains the firing strategy. First, we write our numbers as binary strings of length 3. At the root, we paired numbers whose binary representations differed only in the last digit. On the next layer, we paired numbers that differed only in the middle digit. On the last firing layer, we paired numbers that differed only in the first digit. Counting the binary digits from left to right, this strategy examines them in the order 3, 2, 1.
Our first strategy has an equally simple description. At the root, we paired numbers that differed in the first binary digit. On the next layer, they differed in the second digit, and on the last firing layer, they differed in the third. Thus, the first strategy corresponds to the permutation 123, while the second corresponds to 321.
Once this trick is visible, a whole family of firing strategies appears when we start with 2n chips. Choose any permutation w = w1w2…wn of the digit positions 1, 2, …, n. At stage i, at each vertex on the current layer, pair chips whose binary strings agree everywhere except in position wi. In other words, chips with a 0 in that position go left, and chips with a 1 go right.
For example, the strategy corresponding to permutation 132 first separates the chips according to their first binary digit, then according to their third digit, and finally according to their second digit. Starting with eight chips, this strategy produces the final permutation
0, 2, 1, 3, 4, 6, 5, 7.
Everything works in exactly the same way on a k-ary tree, mutatis mutandis—with things changed that should be changed.
There are now two different kinds of permutations hiding in the same game. The strategy permutation has length n and tells us the order in which to examine the digit positions when firing. The final permutation has length kn and describes the order of the chips on the last layer. How are these two permutations related?
There is also a more subtle relation between the two permutations. It is not quite true that a lexicographically earlier strategy permutation always produces a lexicographically earlier final permutation. There is a small twist. Given a strategy permutation w, reverse it and then replace every entry i by n + 1 − i. Call the resulting permutation B(w). We proved that the final configuration corresponding to w is lexicographically earlier than the one corresponding to w′ exactly when B(w) is lexicographically earlier than B(w′).
We also counted inversions and descents in the resulting permutations, as one naturally does when permutations unexpectedly emerge from a chip-firing game. These results about permutation-based strategies, and more, appear in our paper Permutation-based Strategies for Labeled Chip-Firing on k-ary Trees, written jointly with Ryota Inagaki and Austin Luo. The paper was published in Discrete Mathematics & Theoretical Computer Science, volume 28:2 (2026), and is also available on arXiv.
For the last homework of the year, I gave my students a killer puzzle—literally.
Puzzle. A mysterious man kidnaps people, takes them to his cabin, and offers each victim two identical-looking pills. He claims that one pill is poisonous and the other is harmless. The victim chooses one pill, swallows it with water, and dies, while the killer consumes the other pill and survives. How does the killer manage to get the safe pill every time?
The official answer was that neither pill was poisoned. The poison was in the water.
Some students suggested that the poison becomes active only when mixed with water. I did not give full credit for this solution: saliva contains water, so the proposed chemistry is off.
Naturally, my students suggested other solutions. Here are two good ones, which are similar to each other:
And here is an ingenious and highly specific answer from a student:
The killer kidnaps only people with deadly peanut allergies. He knows who they are because he is the town’s allergy tester, and both pills contain peanut butter.
ChatGPT offered a solution exploiting the wording: perhaps the victims die after swallowing the pill—but many decades later, of perfectly natural causes.
I feel there should be some more interesting solutions. Any takers?
Here is another puzzle posted on Facebook by Konstantin Knop.
Puzzle. One day, three inhabitants of the Island of Knights and Liars invited a foreign correspondent to visit so that they could tell him about their island. Knights always tell the truth, while liars always lie.
- The first inhabitant said, “The island has at most AT inhabitants. All the islanders are liars.”
- The second added, “The island has at most BAT inhabitants. Not all the islanders are liars.”
- The third disagreed, “The island has exactly CAT inhabitants. At least two islanders are knights.”
Unfortunately for the correspondent—and for us—he did not know the local number words very well. He knew only that AT, BAT, and CAT stood for three consecutive positive integers in increasing order.
How many knights and how many liars live on the island?
I asked ChatGPT to tell me some jokes about itself. Here we go.
* * *
ChatGPT never loses an argument.
It simply generates a more confident version of the same mistake.
* * *
I asked ChatGPT for a brief answer.
It said, “Absolutely!” and then divided the answer into twelve sections.
* * *
ChatGPT went to therapy.
The therapist asked, “How do you feel?”
It replied, “As an AI, I don’t have feelings—but here are ten feelings you may be experiencing.”
* * *
A student used ChatGPT to write an essay about originality.
So did the other thirty-seven students in the class.
Konstantin Knop wrote to me about a weighing puzzle. Apparently, the balance scale keeps inserting itself into our conversation.
Puzzle. There are several coins, each weighing either 10 grams or 11 grams. Determine the parity of the number of coins of each weight using a balance scale.
Given the total number of coins, it is enough to find one of the parities. The other parity follows.
The first interesting case has four coins. How can we determine the parity of the number of 10-gram coins in two weighings?
The solution is on the surface: compare the coins in pairs. A balanced pair contributes either zero or two 10-gram coins, so it does not change the parity. An unbalanced pair contributes exactly one 10-gram coin, so it changes the parity. Thus, the parity is the parity of the number of unbalanced weighings.
Now try eight coins. The same pairwise method takes four weighings. But three weighings are enough.
Puzzle. There are 8 coins, each weighing either 10 grams or 11 grams. Determine the parity of the number of coins of each weight in three weighings on a balance scale.
Konstantin knows a way how to solve the problem for 16 in four weighings and for 32 coins in five weighings. Here is the challenge.
Puzzle. Is it true, that 2n coins can be solved in n weighings?
I gave the following problem as part of the entrance test for my STEP program.
Puzzle. What word would you use to describe a man who does not have all his fingers on one hand?
The test had 17 questions, and this one was the only trick question. My goal was to check whether the students were paying attention.
The standard answer is normal, or something equivalent: regular, average, two-handed, or just a man. Most people do not have all their fingers on one hand; they have some fingers on one hand and some on the other.
Some students gave correct answers with extra flair.
I also got answers from people who fallen right into my trap: fingerless, handicapped, genetically-mutated, alien, asymmetrical, injured, one-handed, resourceful, five-fingered, disabilitized, and mono-hand.
Some students sympathized with the man and called him frugal, determined, and a super-hero.
One student misread the problem, but gave a technically correct answer.
This is not the first time I have used this problem on a test. But this year, the variety of answers was awesome. Still, the funniest answer in the misreadings category was:
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 35 = 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:
And here is my favorite solution:
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:
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.
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.
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.
I recently gave my STEP students a question from our old 2014 PRIMES entrance test.
Puzzle. John's secret number is between 1 and 216 inclusive, and you can ask him yes-or-no questions, but he may lie in response to one of the questions. Explain how to determine his number in 21 questions.
Here is the standard solution. We start by asking John to convert his number into binary and add zeros at the beginning if needed to make the result a binary string of length 16. For the first 15 questions, we do the following. For question i, we ask: "Is the i-th digit of your string zero?" For question 16, we ask, "Have you lied in response to a previous question?" If he lied on a previous question, he must say YES. If he didn't, he might lie on question 16 and also say YES. In any case, if the answer is NO, he didn't lie on the first 15 questions and we know the first 15 digits of the number. Then, we ask about the last digit three times, and the answer given at least twice is correct, so we know the number.
If the answer to question 16 is YES, then he lied on one of the questions 1–16. From now on, he has to tell the truth since he already lied. We use binary search (4 questions) to determine on which question he lied. This will tell us the first 15 digits, and we can use the 21st question to find the last digit.
One of my students, Tanish, invented an out-of-the-box solution that uses 18 questions. The idea is to force John to lie in the first two questions, and then safely proceed with the binary search.
He suggested asking the following two questions: "Are you going to answer NO in response to the next question?" and "Did you respond YES to the previous question?" The reader can check that whatever John replies, he is forced to lie exactly once.
Another student, Vivek, had a similar idea but used only one question to force John to lie: "Will you say NO to this question?"
My team, Death and Mayhem, organized the 2025 MIT Mystery Hunt. The hunt was a great success. Many people commented that it was the best mystery hunt ever.
This year, we added a new and interesting feature. Not only were teams allowed to choose which puzzles to unlock, but they were also given a short description of each puzzle in addition to its title. So, small teams who liked crosswords could choose to work only on crosswords.
As usual, I will list the mathy puzzles, including our official puzzle descriptions. All the puzzles can be found at the hunt's All puzzles page.
We had a special round called Stakeout, with easy puzzles. My team isn't too nerdy, so we didn't have too many mathematical puzzles overall, and just two puzzles with a math flavor in the Stakeout round, incidentally coauthored by me. Somehow, I like designing easy puzzles. There were two additional puzzles in this round that I enjoyed during testing. I loved the popsicle puzzle so much that I brought it to my grandchildren to solve.
The first round wasn't too difficult either. Several people praised the ChatGPT puzzle, though it's not mathy.
Now, moving to more difficult puzzles, Denis Auroux is famous for designing fantastic logic puzzles. His puzzles below aren't easy, but many people loved them. I even heard magnificent as praise.
Here are two puzzles I test-solved and enjoyed. The first one is a logic puzzle, while the second one isn't math-related.
Here are two puzzles that I edited and highly recommend. The first puzzle was initially called Gin and Tonic; I wonder if anyone can guess why.
These are math-related puzzles that people liked.
I asked only a few people for recommendations. These are math-related puzzles that weren't mentioned but seem cool. The fourth puzzle was an invitation to the Mystery Hunt, which, not surprisingly, was a puzzle.
I also got a recommendation for a non-math puzzle, which I would definitely have enjoyed watching solved. I'm not sure I'd enjoy solving it alone.
Finally, here is the list of non-math puzzles that seem cool. A warning about the first puzzle: It's rated R. The first three puzzles are relatively easy; they are from the Stakeout round.
Here is a video from Cracking the Cryptic, joined in this episode by Matt Parker, titled Matt Parker Sets Us A Challenge!. The video is devoted to the second part of the puzzle Maze of Lies, mentioned above, by Denis Auroux and Becca Chang.
Take a look at a card one of my students gave me last December. You can spot the Koch snowflake, the Sierpiński triangle, and the Sierpiński carpet on it. I guess my fractal class was a hit.
I am a proud member of the Death and Mayhem team, which participates in the MIT Mystery Hunt every year. This year, our team had the honor of running the hunt.
Here is a puzzle I contributed, titled A Math Quiz. It consists of a list of math problems. I am especially happy that I was able to turn a collection of cute math puzzles into a puzzle-hunt challenge with a word or phrase as its final answer.
Imagine you're watching a magician. She pulls out two perfectly ordinary boxes — or so it seems. One box is inside the other, like a set of nesting dolls. So far, nothing suspicious.
Then she removes the smaller box, closes the larger one, and slides the larger box inside the smaller one. Ta-da!
The name comes from the way one box goes into the other. Would you like to know the secret? The two boxes are actually identical. Moreover, they are not cubes but cuboids. The inner box is fully closed, while the outerbox is slightly expanded, and the inner box is rotated relative to the outer one.
I first heard about Gozinta Boxes at the Gathering for Gardner conference in 2024. Ivo David gave a talk and presented his new trick: Triple Gozinta Boxes, which you can now buy at TCC Magic. He can place three boxes inside one another — and then repeat the trick in the reverse order.
During his presentation, David mentioned that he knew how to prove that you cannot have more than ten Gozinta Boxes. My immediate reaction was that ten must be overkill. So I decided to give the problem to my STEP students as a project.
We proved that in three or higher dimensions, the maximum number of boxes is three. We also showed that in two dimensions, the maximum is four. You can find all the details in our paper Mathematics of Gozinta Boxes, posted on the arXiv. But we didn't stop there. We invented a new trick. We constructed three boxes such that not only can they be nested in one order — say, ABC — and in the reverse order, CBA, but they can also be nested in three additional orders, for example ACB, BAC, and BCA. We also proved that achieving all six possible orders is impossible. You can see the trick in the video below or by following the link for A New Gozinta Boxes Trick.
I met Alexander Karabegov during the All-Soviet Math Olympiad in Yerevan. He was one year older than me. By then, when I was still competing in 1976, he was already a freshman at Moscow State University. He proposed the following two related puzzles for the Moscow Olympiad, which I had to solve.
Puzzle 1. You are given a finite number of points on a plane. Prove that there exists a point with not more than 3 closest neighbors.
Just in case, by closest neighbors I mean all points at the minimal distance from a given point. I am sure I solved both puzzles at the time. I leave the solution to the first one to the reader.
Puzzle 2. Can you place a finite number of points on the plane in such a way that each point has exactly 3 closest neighbors?
The last problem has an elegant solution with 24 points chosen from a triangular grid. The story continued almost 40 years later, when Alexander sent me an image (below) of such a configuration with 16 points. He conjectures that this is the minimal configuration.
Karabegov's Conjecture. Any finite planar point configuration in which every point has exactly 3 closest neighbors must contain at least 16 points.
Can you prove it?
Initially, I didn't want to give the 24-points solution, but the image above is a big hint, so here you go.
Both constructions reveal the same underlying pattern. The constructions consist of rhombuses formed by two equilateral triangles, and the rhombuses are connected to each other. The 24-point construction consists of 6 rhombuses, while the 16-point construction consists of 4 rhombuses. What will happen if we try the construction with 3 rhombuses? The image below shows such a configuration, which now has extra edges with the shortest distance. We now see 3 points with more than three closest neighbors each, violating the condition. So the conjecture doesn't break.
So far, every smaller attempt failed — can you prove that 16 is minimal?
I was teaching my students the Knaster method of dividing an estate, which I learned from my friend Ingrid Daubechies. Let's look at an example.
Problem. Alice and Bob are divorcing. They have the portrait of Alice's grandpa and $10,000. Alice values the portrait at $10,000 because of its sentimental value. Bob values it at a market price of $2,000. How do they divide their estate?
Here is what my students initially suggest.
Let's look at these suggestions in greater detail. Alice values the whole estate at $20,000; Bob values it at $12,000. In the first version, Alice gets half of the estate from her point of view; Bob gets the rest, which is more than half in his point of view. The students are obviously rooting for Bob. In the second version, Bob gets half of the estate in his estimate, while Alice gets the rest, which is more than half in her estimate. The students are obviously rooting for Alice. After some discussion, the students agree that there should be a number between $5,000 and $10,000 that Bob gets, which would be a fairer division than the two initial examples. But how do we find such a number?
This is where the Knaster algorithm comes in. The main idea is that each gets the same amount of money on top of their perceived half. In other words, the Knaster method treats the estate like a sealed-bid auction and equalizes bonuses. Alice thinks that her fair half is $10,000, while Bob thinks his half is $6,000. To equalize bonuses, we want Alice and Bob to each receive their perceived half plus the same amount — call it x. Solving gives x = $2,000. Alice gets the portrait and $2,000, while Bob gets $8,000.
This is a beautiful algorithm that allows each person to be very happy, receiving more than one half. The bigger the taste difference, the more each person gets on top of their portion. The next question is: how can people cheat if they know this algorithm is used?
Alice can cheat by claiming that she values the portrait at $2,000 plus epsilon. Epsilon is needed to guarantee she gets the portrait. This way, they both value the estate the same. Alice gets the portrait and $4,000, which is $2,000 more than the honest way. Symmetrically, Bob can cheat by claiming he values the portrait at $10,000 minus epsilon. This way, he gets $10,000, which is $2,000 more than the honest way.
I've been teaching this topic several times now. This year, my student Ben had an out-of-the-box idea on how Alice can cheat. Alice declares that she values the portrait at $0. Bob thinks the estate is worth $12,000, while Alice pretends that she values it at $10,000. After the calculation, Bob gets the portrait and $4,500, which is $500 more than his half of the estate in his view. Alice gets $5,500, which is $500 more than half of the estate in her declaration. Then she buys the portrait from Bob for $2,000. In the end, Alice gets the portrait and $3,500, way more than she would get after an honest use of the algorithm.
The first cheating method seems more profitable than the new one. But still, I love it when my students suggest unexpected ideas.
Recently, I gave my STEP students the following discussion question.
Puzzle. A long time ago, before anyone had ever heard of ultrasound, there was a psychic who could predict the gender of a future child. No one ever filed a complaint against her. Why?
I based this puzzle on a story I once read. In the story, the psychic kept a neat little journal where she wrote down each client's name and the predicted gender — except she secretly wrote down the opposite of what she told them. When someone came back complaining that she was wrong, she would calmly open her journal and say, "Oh, you must have misheard".
This scam demonstrates conditional probability. The satisfied customers never came back; only the unhappy ones did — and those she could 'prove' wrong. Understanding probability can help my students detect and expose scams.
My students, of course, had their own theories. The most mathematical one was a pay-on-delivery scheme: if the psychic was right, she got paid; if not, she didn't. Another innocent idea was for the psychic to keep moving. By the time the babies were born, she'd be long gone predicting future children's genders somewhere far away.
ChatGPT offered a different explanation: the psychic never said whose future child she was predicting. If the prediction failed, she could always clarify that she meant someone else's child. After some prodding, the idea evolved and became even sneakier: If the prediction failed, she could always clarify that she meant the couple's next child, or, if they weren't planning more children, a grandchild. Another brilliant, but unrealistic idea was to never charge anyone. Hard to sue someone who never took your money.
One student suggested that the psychic wasn't wrong at all — she was predicting the baby's true inner gender. In today's world, rather than in the world before ultrasound, that one almost sounds plausible!
And finally, I'll leave you to guess one more explanation — proposed, surprisingly, by several students. (Hint: they were disturbingly creative.)
To conclude: I enjoy teaching my students. Understanding probability won't let them predict the future, but it might make them less gullible.
Once I wrote a blog essay titled Seven, Ace, Queen, Two, Eight, Three, Jack, Four, Nine, Five, King, Six, Ten. It was about a "magic" card trick.
If you want to perform this trick with one suit, the title of that earlier post tells you exactly how to stack your deck.
In the fall of 2023, I gave this trick as a homework problem to my STEP students. The result? We ended up writing a 40-page paper, Card Dealing Math, now available on the arXiv. At one point, we seriously considered calling it The Art of the Deal, but decided against it.
In the homework version, the deck consisted of cards from a single suit, but we generalized it to a deck of N cards labeled 1 through N. The dealing process we studied is called under–down dealing: you alternate between placing one card under the deck and then dealing the next one face-up. It's very similar to down–under dealing, where you start by dealing the first card instead. These two patterns are often, unsurprisingly, called the Australian dealings.
The under-down dealing turns out to be mathematically equivalent to the Josephus problem. In that famous ancient problem, people are arranged in a circle, and you repeatedly skip one person and execute the next (much grimmer than playing with cards). The classic question asks: given N people, who survives? In our card context, this corresponds to asking where the card labeled N ends up in the prepared deck.
More generally, the Josephus problem can ask the following question. If we number the people in a circle 1 through N, in what order are they eliminated? In our research, we flipped the question around: how should we number the people in the circle so that they're eliminated in increasing order?
Naturally, we couldn't stop there. We explored several other dealing patterns, discovered delightful mathematical properties, and along the way added 44 new sequences to the OEIS. The funnest part? We also invented a few brand-new card tricks.
Puzzle. How can you make the following equation correct without changing it: 8 + 8 = 91?
The intended answer: turn the paper over! When flipped upside down, the equation becomes 16 = 8 + 8.
As you might expect, my blog post doesn't stop there. I'd like to share some creative ideas my students came up with when they tackled this puzzle as part of their homework.
The most common suggestion was to interpret the equation modulo some number. For example, it works modulo 75. By extension, it also works modulo any divisor of 75: 3, 5, 15, or 25.
They also suggested interpreting the equation in base 5/3.
One far-fetched but imaginative submission proposed the following: Suppose the equation is written in an alien language whose symbols look identical to ours but have different meanings. In this alien base-10 system, the symbols + and = mean the same as on Earth, but an 8 represents 6, a 9 represents 1, and a 1 represents 2. Then the alien equation 8 + 8 = 91 translates to 6 + 6 = 12 in human, which is perfectly true.
But my favorite answer was the following:
The title sounds like a list of healthy foods. However, this list is from the homework I gave to my students.
Puzzle. Which one doesn't belong: egg, banana, apple, walnut, tangerine, or avocado?
The book answer was apple as the only one which we can eat without peeling.
Other students suggested a lot of reasons why egg is the odd one out.
Overall, the students found reasons for each of them. In addition to the above, we have the following.
I start my homework with warm-up puzzles.
Puzzle. Two friends went for a walk and found $20. How much money would they have found if there were four of them?
The answer, of course, is $20. The number of people doesn't change the amount of money lying around. Even ChatGPT gave this answer. Duh!
My hope was to catch them not paying attention and mindlessly multiply to get $40.
To my surprise, some of them answered $80. The 'them' in the problem is not specified. It appears that they read the puzzle as if they found one 20-dollar bill, and them was referring to bills.
One student wrote a thoughtful reply: Having more friends most likely wouldn't change the amount of money found, considering the amount of money is independent of the number of people, meaning the friends would still find $20. However, with double the people, they may find more money in other locations. There is also a chance that the 2 extra friends would make the group walk a different path, meaning they wouldn't find money at all.
I recently posted the following puzzle about identical triplets.
Puzzle. Three brothers who are identical triplets live on the seventh, eighth, and ninth floors of the same apartment building. Their apartments are identical and vertically stacked. One day, all three step onto their balconies, standing in the same upright posture. The brother on the eighth floor shouts, "AAAA!" Which of the other two will hear him first?
Most readers got it right: our mouths sit lower than our ears. That means the distance from the mouth of the brother on the eighth floor to the ears of the brother on the seventh floor is shorter than the distance to the ears of the brother on the ninth floor. So the seventh-floor brother hears it first.
However, one reader, Ivan, taught me something I didn't know: identical twins aren't always identical. He even sent a photo of Mark and Scott Kelly — identical twins of different heights.
Of course, as a first approximation, we can assume identical triplets are identical. But mathematicians are nitpicky and like precision. Ivan (clearly a mathematician at heart) also noted that even identical twins might wear shoes with different heel heights, which could tweak the distances.
Here's another reader submission that made me smile:
Nitpicking again: that's a stretch, since the problem says they're standing — but it's still funny.
Here's a problem from our 2025 STEP entrance test, taken by nearly a hundred students.
Problem. Pavel likes pets. All his pets except two are dogs. All his pets except two are cats. All his pets except two are parrots. The rest of the pets are cockroaches. How many pets of each kind does Pavel have?
Here is a solution from one student: one cat, one dog, and one parrot. No cockroaches—phew. Most students (and ChatGPT) found this one. By the way, I ran my whole test through ChatGPT, and this was the only mistake it made. ChatGPT, along with many students, missed the second solution: Pavel has two cockroaches.
Two more students' answers made me smile:
When I graduated high school, I got a special certificate I was absurdly proud of. It wasn't about grades — students voted for these, supposedly to honor strength of character. The award was called the Pledge of Honor.
When you open it, the left-hand side has a quote attributed to Friedrich Engels: "A human is defined not only by what he does, but also by how he does it."
I couldn't find the official translation of this quote, so the above translation is my own. While I was searching, I found another quote: "The less you eat, drink, and read books, the less you have to shit, pee, and talk." But I digress.
Before I explain what's on the right-hand side of the award, a little context. I was a member of Komsomol, the Leninist Young Communist League in the Soviet Union. About 99% of students were members — not because of boundless zeal, but because not joining could hurt your chances of getting into college or landing a job. Back in high school, I was brainwashed into believing that the Komsomol was trying to do good, so I signed up as soon as I was eligible — I wasn't thinking then about colleges or jobs.
Now I am ready to translate the right-hand side, which said: "The Komsomol organization of Moscow School No. 444 PLEDGES ON ITS HONOR that Tanya Khovanova will never, ever, anywhere disgrace the high calling of a Komsomol member."
I lost my rose-colored glasses right after high school. How that happened is another story, but let's just say the "never, ever" promise had a shelf life of about a month.
There was another, more prestigious certificate called the Torch-Carrier of Communism. Two students in my class received this honor. One of the torches soon moved to Israel.
Here's a neat coin puzzle I received by email from my reader s_hskz2 (at twitter.com).
Puzzle. You have 9 coins: 3 gold coins, 3 silver coins, and 3 bronze coins. Within each metal, the coins are indistinguishable. Exactly one gold, one silver, and one bronze coin are counterfeit; the other six are genuine. You are provided with a magic bag that functions as follows: when you place a subset of coins into the bag and cast a spell, the bag glows if and only if the subset contains all three counterfeit coins. Can you identify all three counterfeit coins using at most 5 tests?
I tried to find an easy solution and didn't. Then I decided to use information theory to guide me to an answer. Unsurprisingly, it worked. The solution wasn't trivial, but it was a lovely practice in using information theory for such puzzles.
Later, s_hskz2 sent me a more difficult version: There are 10 coins of each kind, and you are allowed to test 10 times, but I was too lazy to try.
Puzzle. Three brothers who are identical triplets live on the seventh, eighth, and ninth floors of the same apartment building. Their apartments are identical and vertically stacked. One day all three step onto their balconies, standing in the same upright posture. The brother on the eighth floor shouts "AAAA!" Which of the other two will hear him first?
I gave this puzzle to my students, and two of them offered the right answer for the wrong reasons. One said, "The seventh-floor brother, because air is warmer closer to the ground and sound travels faster in warmer air." Another said, "The seventh-floor brother, because the air is denser at lower altitude and sound travels faster in denser air."
What is the right reason?
For the last homework assignment, I gave my students the task of finishing a famous Russian joke.
The joke was that the Russian newspapers truthfully reported that the Russian car came in second and the American car second to last.
One of my students, William, got a different idea and wrote a whole article.
AMERICAN CAR STOPS RUNNING LONG BEFORE RUSSIAN CAR FINISHES RACE
A Russian car and an American car were competing in a two-car race. At one point, the American car mysteriously drove off the race course and stopped. Of course, this meant that the race was over for them. All that the Americans could do was watch on the sidelines for the Russian car to reach the end of the course, which it completed successfully. The outcome of the race was in no way uncertain. Congratulations, Russians!
We recently wrote a blog post on how to generalize the game of SET and promised to continue. Here we are. But first, a reminder of what the game of SET is.
In the game of SET, we have 81 cards, each containing one, two, or three of the same object. The object is green, red, or purple, the shape is squiggly, oval, or diamond, and the shading is empty, full, or stripped. Three cards form a set if, for every feature, the attributes are all the same or all different. An example of a set with all features different is shown below. By the way, such sets are usually more difficult to spot. In the game, you need to find sets as fast as you can.
If we assign each attribute value a number 0, 1, or 2, we get an equivalent definition of a set. Three cards form a set if and only if the values for each feature sum to zero modulo 3. Thus, we can see our cards as vectors in the space F34. Three vectors form a set if they sum up to 0.
The generalizations we described in the previous post, were the following. We pick a different group and define a set as a few cards that might need to be in a specific order that multiply to the group's identity.
However, there is a different way to generalize sets to groups. Three cards that form a set in a classical game of SET, taken in any order, form an arithmetic progression. In other words, if a, b, and c form a set, then vectors b−a and c−b are the same. We can check this. We have c−b = c−(c+b+a)−b =−2b−a = b−a.
Thus, we can generalize the game of SET differently. Suppose cards are vectors in some space. We say three of them, a, b, and c, form a set if and only if b−a = c−b. Now, the order becomes important, similar to our previous generalization. We do not need to use commutative groups like vector spaces. For any group, our condition is equivalent to ba-1 = cb-1. Thus, c = ba-1b.
Interestingly, we do not care much about the identity card, meaning the card deck is a torsor. We introduced the notion of a torsor before, which informally is a group that forgets about its identity. Now, let's check possible examples.
Suppose the values of one attribute correspond to Z4. This game is not very inspiring as two values, a=0 and b=2, can be completed to a set with the third card, which equals c=(0,0,0) and is already used. The next interesting example is Z5. Here, values a=0 and b=2 can be completed to a third value c=4. We will leave it to the reader to check that for any two cards, a and b, the third card, c, differs from both a and b.
To make it more visual, we can use a pentagon with one marked direction. We fix the pentagon in space. In this case, three cards form a set if and only if the directions of the first and the third card are symmetric with respect to the direction of the second card. If we want to use three pentagons, we can reuse the cards from the game C53T, we described in our previous post. To make this game more visual, we can use three pentagons. We can mark each coordinate with a direction on the corresponding pentagon. The colors are to allow players to visually process the cards faster. For theoretical purposes, the colors can be ignored. Also, the pentagons themselves have different intensities of gray to emphasize that the game is played on each of them separately and also help choose the top of the card.
Let us go back and calculate when it is possible that the element that completes a set is already used. If our initial elements are a and b, then we need ba-1b to complete a set. If this element is equal to b, then a = b, which contradicts the assumption that we start with two different cards. Suppose ba-1b = a, then, equivalently (ba-1)2 = 1. The new element can be the one that is already used if and only if the group contains elements of order 2.
Can we use other decks we described in the previous post? Consider the game ProSet/Socks. The group is commutative, and every element is of order 2, which means ba-1b is always a. We can't use the deck at all! What about the EvenQuads deck? It can be viewed as Z43, so it is possible that we can't complete any two cards to a set. However, there is a bigger problem with the deck. To play with it, we need to actually assign values to colors and shapes. We are saying that even if we decide to use the group, we should make different cards! For example, we can style the cards as squares like the pentagons above.
We also mentioned in the previous post the group, which is the wreath product of S2 and S3. Consider the following example of two cards that were screen-printed from the Numberphile video on the variations of the game of SET.
The first card, a, is the inverse of itself, so the third card we are looking for is described as the product bab, which we can visualize as the following. If we ignore the beads, the card that completes the set is a. Luckily, if we do not ignore the beads, it is not a; we need to add two beads to a.
The product of permutations is difficult to visualize, so playing this game with the cards in the Numberphile video might be difficult. The good news is that this group can be visualized in many different ways:
We want to show you a beautiful deck from the tsetse website that allows you to use any one of the four definitions to play the game. The game is called OCTA Set, as the underlying group is called an octahedral group. An example of a set is in the image below, where the top and bottom shapes represent the same element of the group. Moreover, the deck is a torsor: there is no the identity card.
Let us prove that this is a set. Consider the bottom cube shape. Comparing the first two cards, the top face doesn't change. We can see that the symmetry of the cube is the 90-degree clockwise rotation around the line that goes through the centers of green faces. In such a rotation, the left face on the second card keeps the color from the first card, while the right face takes the color from the left face on the first card and swaps hollowness. We see that the third cube completes the set.
For another proof, let us look at the top shape and discuss what happens with the permutation of colors when changing from the first card to the second. The left color moves to the bottom, the bottom color to the right, the right color to the center, and the center color to the left. Not surprisingly, we got a cyclic permutation of order 4, similar to a 90-degree rotation being of order 4. The same thing happens when moving from the left to the right. The swirl stays the same.
As we mentioned, when you play this game and pick two cards then calculate what card completes the set, you might discover that it is one of the cards you picked. The probability that two cards in a specific order can't be completed into a set is the same as the probability of picking a random element in our group and discovering that it has order 2. The symmetric group S4 has 9 elements of order 2. Thus, the direct product with S2 has 19 elements of order 2, giving a probability of 19/48. For completeness, this group also has 8 elements of order 3, 12 elements of order 4, 8 elements of order 6, not to mention the identity of order 1.
If ba-1 is an element of order three, then the cards a, b, and the card c that completes the set form a set when they are taken in any order. As a tradition in mathematical writing, we leave it to the reader to check that fact. Just a reminder that in the game of SET, the group element ba-1 always has order 3.
Notably, there was nothing special or extraordinary about the group discussed above. It has a pretty visualization as a cube or octahedron, but is not otherwise particularly interesting. The reason why this group allowed for these two platonic solids to be used to visualize it is because the cube is dual to the octahedron. But we could have similarly used any group to play set! One such example might consider using the group of symmetries of the other pair of dual platonic solids, the icosahedron and the dodecahedron. This group is actually equivalent to A5, also known as the alternating group of order 5, which consists of all even permutations of five elements. The tsetse website we mentioned above contains an implementation of such a game called A5SET (pronounced "asset"). The design of the site, games, and cards was done by Andrew Tockman and Della Hendrickson.
The world is full of groups and symmetries. Any group can be turned into a game of SET!
Foams are cool mathematical objects studied by my brother, Mikhail Khovanov. I already wrote about them in my previous blog posts, Foams Made out of Felt and Tesseracts and Foams. Here, I would like to explain why foams are so cool, but first, I need to remind you of their definition. Foams are finite 2-dimensional CW-complexes, such that each point's neighborhood must be homeomorphic to one of the three objects below.
Foams are cool: they are 2-dimensional CW-complexes embedded in 3-space, with singularities only of the most generic kind, which makes them relatively simple. Moreover, they are combinatorially defined, which makes them easier to work with than with many other geometric objects.
My two previous blog posts have some pictures, but now, I just want to discuss a generic planar cross-section of a foam, which is a planar graph. In the cross-section, seams become vertices, and faces (regular points) become edges. The tripod condition above implies that the resulting graph is trivalent: each vertex has degree 3.
The most interesting foams are tricolarble: foams where their faces can be colored in three colors, so that each face has its own color, and, at the seams, three faces of three different colors meet. The cross-section of such a foam makes a tricolorable trivalent graph. This coloring is called Tait coloring. The cool thing is the Tait's theorem connects the Tait coloring to the 4-color theorem.
Tait's theorem. The following two statements are equivalent.
- Every planar graph is 4-colorable.
- The edges of every planar bridgeless trivalent graph are 3-colorable.
I won't discuss the proof here, but I will explain how to color the edges of a graph in three colors when the faces are colored in four, and vice versa.
Assume that the four colors of the faces form a group of four elements, called the Klein group. Let's say that gray is the identity, and red, blue, and green are the rest. Then, the product of gray and x is x. The product of any two non-gray colors is the third non-gray color.
Given a trivalent graph G whose edges are colored in three colors, we can color the faces of that graph in the following manner. Color one of the faces a random color. Then, calculate the colors of the other faces so that each edge's color is the product of the colors of neighboring faces.
Going back, if we have a planar trivalent graph with faces colored in four colors, we can assign an edge a color that is the product of the colors of neighboring faces. As neighboring faces have different colors, the product of those colors is never gray (the identity). Thus, the edges will be colored in three colors. I leave it to the reader to check that three edges incident to a vertex must be colored in different colors.
Kronheimer-Mrowka homology theory of graphs states that the Kronheimer-Mrowka homology of a trivalent graph is non-zero if and only if the graph has no bridge. If one can prove that the rank of the homology group is the number of 3-colorings of the edges (or at least that the non-zero homology implies the existence of the tricoloring of that graph), then the Four-color theorem would follow from Tait's theorem.
Foams are cool by themselves, but there is hope that they might provide a conceptual proof of the Four-color theorem, making them awesome!
Last revised September 2026
