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.

---

Share: