Tanya Khovanova's Math Blog

Let me begin with labeled chip-firing on an infinite directed binary tree, where the root is at the top. Place 2ⁿ chips, labeled from 0 to 2ⁿ − 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 kⁿ chips, labeled from 0 to kⁿ − 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 kⁿ − 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 2ⁿ chips. Choose any permutation w = w₁w₂…w_n 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 w_i. 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 kⁿ and describes the order of the chips on the last layer. How are these two permutations related?

• The first observation is that the firing strategy corresponding to the identity permutation produces the lexicographically earliest final configuration, in which the labels appear in increasing order.
• At the other extreme, the firing strategy corresponding to the reverse of the identity permutation produces the radix-k digit-reversal permutation. Theorem 3.3 of our paper (link below) shows that this is the lexicographically latest configuration among permutation-based strategies. In fact, although we did not state this stronger result in the paper, a short induction shows something stronger: the digit-reversal permutation is lexicographically latest among all attainable final configurations.
• Two different strategy permutations always produce two different final configurations.

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:

• Both pills are poisonous, but the killer has taken an antidote.
• Both pills are poisonous, but the killer has somehow built up a resistance to the poison.

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.

Coin Parity

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

• A cautious answer: A regular person, as to my knowledge, has fingers on both hands.
• A logical answer: A person with multiple hands, if they don’t have all fingers on one hand, then they must have multiple hands. For example, a human would work in this case.
• A funny answer: The man who puts his eggs in two baskets.

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.

• Human, because I don’t see any difference in the man whether he has fingers or not.

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:

• A chef.

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?