State of Play

Today we shall celebrate Children’s Day (with the painful observation that I no longer qualify as a child) and the two-year anniversary of this blog (time has flown…) by looking at an extremely useful idea which comes up repeatedly in problems involving algorithms or processes.

A state graph of an operation $\mathcal{O}$ is a labeled directed graph that can be used to indicate the directed connectivity between the set of possible states under $\mathcal{O}$ . The concept of the state graph can be utilized in two main ways: firstly, we may bound the number of operations that can be performed before we reach a certain state (usually an end or neutral state) and secondly, we may use it to show that a certain state can be reached from some other state (and maybe bound the number of operations it takes to do so).

One of the most important things to check right away on problems of this sort is whether the edges are directed, i.e whether the operation is reversible. If it is, showing state $X$ can be reached from state $Y$ is equivalent to the converse.

Unless stated otherwise, all distances below are taken in a connected component of an undirected state graph (which shall usually be the case in olympiad contexts). When an operation is reversible, we replace the two opposite directed edges by a single undirected edge.

Before moving on, we need to review several key terms from graph theory. The distance $d(u, v)$
between two vertices $u$ and $v$ is the number of edges in the shortest path connecting these two vertices. The diameter $d(G)$ of a graph is the maximum shortest distance between any pair of vertices in a graph. The eccentricity $\epsilon (v)$ is the greatest distance from a specific vertex $v$ to any other vertex in the graph. The radius $r(G)$ is the minimum value of all eccentricities in the graph.

We shall informally call a particularly convenient intermediate configuration a home state.¹ In graph-theoretic language, we are selecting a vertex through which we can construct short paths between many pairs of states.

A very important result that we shall use time and time again is the relationship between the diameter and radius of a graph.

Theorem 1 (Diameter-Radius)

The radius of a graph is at least half its diameter.

Proof. For the other inequality, choose a vertex $w$ whose eccentricity is minimal, and let $u, v$ be vertices satisfying $d(u,v)=d(G).$

By the triangle inequality,

$d(G)=d(u,v)\leq d(u,w)+d(w,v)\leq 2\epsilon(w)=2r(G).$

Therefore, $r(G)\geq \frac{d(G)}{2},$ as required.

The basic recipe for many problems here is almost repetitive:

Step 1 Pick a suitable state graph and identify the vertex and edge set (usually states and states connected by a single operation). Check whether edges are directed.

Step 2A Determine the home state(s), based on a rough intuition of ‘distance’.

Step 2B Rigorously define distance between states. This parameter will almost always depend on which home state you are looking at, and is usually extreme at the home state, so expect to deal with several definitions concurrently.

Step 3 Bound! Bound! Bound!

Steps 2A and 2B can be performed in either order, but you can always use one of them to motivate the other. This motif will make a lot more sense looking at a contest example.

Problem 2 (IMO Shortlist 2017 C2)

Let $n$ be a positive integer. A chameleon is a sequence of $3n$ letters with exactly $n$ occurrences of each of the letters $a$ , $b$ , $c$ . Define a swap to be the transposition of two adjacent letters in the chameleon. Prove that for any chameleon $X$ there exists a chameleon $Y$ such that $X$ cannot be changed to $Y$ using fewer than $3n^2/2$ swaps.

Swaps are clearly reversible, and the state graph² is connected since adjacent swaps can ‘sort’ every chameleon.

Here, since we are working with swapping pairs of adjacent letters, we can look at the number of inversions (pairs of letters whose order in the chameleon is opposite to their alphabetical order) of our chameleon.

Each swap switches two adjacent letters, so the number of inversions of chameleon $S$ changes by one (if the letters are distinct) or zero (if the letters are identical) in each move.

Thus, in order to find two chameleons which are far apart from each other, we need to maximize the difference in the number of inversions. This naturally leads us to consider the pair of chameleons $A= \underbrace{aa\dots a}_{n} \underbrace{bb \dots b}_{n} \underbrace{cc\dots c}_{n}$ and $B= \underbrace{cc\dots c}_{n}\underbrace{bb\dots b}_{n}\underbrace{aa\dots a}_{n}$ .

Clearly, the difference in the number of inversions is $3n^2$ , so the diameter of the state graph is at least $3n^2$ . Moreover, our theorem above implies that the radius of the graph is at least $\frac{3n^2}{2}$ , and we win.

This framework also appears in some approaches for China 2024/6 and IMO Shortlist 2018 C3.

A common trick involves using a vertex with low eccentricity as a ‘home state’. Hence, an algorithm will involve moving to and from this home state, which cuts down the number of operations required.

One of the shortcomings of this approach is that it requires the state graph of the desired process to be in some sense compact. In fact, in the case where there exist states which are ‘further away’ from the home state, it might be efficient to travel through a different path. To counter this challenge, it is often convenient to define multiple home states and use the path which is closest to the starting/ending state.

We shall look at this generalization in action, with the following two beautiful problems, given at the Iran Team Selection Tests in consecutive years.

Problem 3 (Iran TST 2025/11)

There are $n$ cups labeled $1, 2, \dots, n$ , where the $i$ -th cup has capacity $i$ liters. In total, there are $n$ liters of water distributed among these cups such that each cup contains an integer amount of water. In each step, we may transfer water from one cup to another. The process continues until either the source cup becomes empty or the destination cup becomes full.

Prove that from any configuration where each cup contains an integer amount of water, it is possible to reach a configuration in which each cup contains exactly 1 liter of water in at most $\frac{4n}{3}$ steps.
Prove that in at most $\frac{5n}{3}$ steps, one can go from any configuration with integer water amounts to any other configuration with the same property.

Let $C$ denote the number of non-empty cups in the starting state. We first look at how this parameter relates to the distance to the equidistributed (all cups have $1$ liter of water) state.

Algorithm 1. Pour all the non-empty cups into the $n-$ th cup. Now, pour the $i-$ th cup into the $(i-1)$ -th cup for all $n \ge i \ge 2$ in descending order starting with $n$ .

Observe that the first part takes at most $C$ steps and the second takes $n-1$ steps, for a total of less than $n+C$ steps. The second part ensures that each cup contains $1$ liter of water.

Algorithm 2A. Until all the cups contain water, select a cup with at least 2 liters of water, and pour it into the $1$ -st cup (if the $1$ -st cup is not empty pour it into any empty cup). Then, pour the water in the $1-$ st cup into any empty cup.

Clearly this takes at most $2(n-C)$ steps to pour 1 liter of water into all the empty cups.

Now, it is clear that if $C\le \frac{n}{3}$ , then algorithm 1 ensures that in less than $n+C \le \frac{4n}{3}$ steps each cup contains 1 liter of water. Further, if $C > \frac{n}{3}$ then algorithm 2A ensures that in at most $2(n-C) < 2(n- \frac{n}{3})=\frac{4n}{3}$ steps each cup contains 1 liter of water.

For the second part, our first question is regarding the choice of home state. The most natural option is of course to simply use the one given to us in part (a). We can try using the equidistributed state (or any other single home state), but some playing around with that should convince you that the bounds obtained as such are far too weak.

As before, this is due to the presence of two clearly antipodal states: the equidistributed and extremal (the $n-$ th cup has $n$ liters of water) ones. We shall have to deal with this by selecting both of them to be home states.

Naturally, this introduces the additional parameter $C'$ of non-empty cups int he final configuration. We strengthen algorithm 2A slightly.

Algorithm 2B. Pour all the cups with water into the $n-$ th cup. Now, say the final configuration includes non-empty cups (other than the $n-$ th) whose indices are $c_1<c_2<\dots < c_m<n$ and desired amounts of water are $l_1,l_2,\dots , l_m$ liters. Now, pour the $n-$ th cup into the $l_i-$ th cup until it becomes full and then pour the $l_i-$ th cup into the $c_i-$ th cup for all $m \ge i \ge 1$ , in descending order starting from $m$ .

The difference is that this does not waste the interim moves which pour water into cups which are supposed to be empty in the final state.

The first part takes at most $C$ steps, and the second part takes at most $2C'$ steps for a total of $C+2C'$ steps. Most importantly, this algorithm can be executed (please don’t forget to check this each time you introduce an algorithm) since the only cups other than the $n-$ th cup that will be non-empty after round $i$ are $c_m, \dots , c_{m-i+1}$ . Since $l_{m-i} \le c_{m-i} < c_{m-i+1}<\dots c_m$ , previous rounds of the algorithm do not interfere with later ones.

This time, we have three possibilities.

If we perform algorithm 1 followed by pouring water from any cup which is empty in the final configuration, into any cup which has less water in it than required, then $2n+C-C'$ steps suffice.
If we perform algorithm 2A followed by pouring water from any cup which is empty in the final configuration, into any cup which has less water in it than required, then $3n-2C-C'$ steps suffice.
If we perform algorithm 2B then $C+2C'$ steps suffices.

It is not hard to see that at least one of these choices requires at most $\frac{5n}{3}$ moves, which finishes the proof.

Problem 4 (Iran TST 2026/2)

A trick is defined on a $n-$ vertex tree as follows. Starting on a tree $T$ , first add an edge which forms a triangle (cycle of length three). Then, a different edge from that cycle is deleted, producing a new tree. The new tree is the result of a trick on $T$ . Prove that there exists a positive integer $N$ such that for all integers $N$ and any two $n$ vertex trees $T_1$ and $T_2$ , we can reach $T_2$ from $T_1$ by using at most $2n-1405$ tricks.

Again, we scout for our choice of home states. The most natural pair of antipodal states with respect to this operation are the $n-$ path and $n-$ star, simple enough graphs, so we shall use them. What about defining distance?

We can let $\text{lp}(T)$ denote the length of the longest path $L$ of $T$ , and use that to relate to the $n-$ path. Think about this as how smoothed out (and hence close to being a path) the graph is.

We can let $\Delta(T)$ denote the maximum degree $\deg(v)$ of $T$ , and use that to relate to the $n-$ star. Think about this as how dense (and hence close to being a star) the graph is.

It is clear that tricks are reversible.

Some tricks. Added edges in blue, and deleted ones in red. Left : increasing $\Delta$ Right: increasing $L$

Some tricks. Added edges in blue, and deleted ones in red. Left : increasing $\Delta$ Right: increasing $L$

Clearly, any vertex which is a neighbour of a vertex in $L$ can be added to $L$ using a trick, increasing $\text{lp}(T)$ by one, and any vertex which is a neighbour of a vertex adjacent to $v$ can be connected to $v$ using a trick, increasing $\Delta(T)$ by one.

By repeatedly applying these two tricks, we can thus transform any tree $T$ on $n$ vertices into either the $n-$ path using at most $n - 1 - \text{lp}(T)$ tricks or into the $n-$ star using at most $n - 1 - \Delta(T)$ tricks.

Thus, at most

$\min\Big(2(n-1)-(\text{lp}(T_1)+\text{lp}(T_2)),2(n-1)-(\Delta(T_1)+\Delta(T_2))\Big)$

tricks are required to move between $T_1$ and $T_2$ , by passing through one of the common states.

What remains now is to show that for all sufficiently large $n$ , any $n-$ vertex tree $T$ must satisfy at least one of $\text{lp}(T)\ge 1405$ or $\Delta(T) \ge 1405$ . This is a simple exercise in graph theory, and is left as an exercise³.

This terminology is by no means standard, and you should always explain what you mean by ‘home state’ during an actual contest. ↩︎
The state graph of such a ‘swapping’ process is commonly referred to as an adjacent-transposition graph. ↩︎
Hint: think of the tree as rooted. How many generations can we have? How many vertices in each generation? ↩︎

State of Play

Share this:

Comments

Leave a Reply Cancel reply