Angular Momentum

State of Play

October 1, 2026
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$

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

September 17, 2026
This blog post corresponds to my recent camper talk at MBL Poland on tetrahedra¹.

Today, we shall take a look at the three-dimensional analogue of the triangle — the tetrahedron. On the way, we shall answer the question of whether the standard triangle centers also exist for tetrahedra, with particular attention on the orthocenter.

Throughout our work, we consider a tetrahedron $ABCD$ in the three-dimensional Euclidean space.

Recall that the locus of points equidistant to a line segment $XY$ , is the perpendicular-bisector plane of $XY$ — the plane passing through the midpoint of the segment, which is perpendicular to it. Now, the perpendicular bisector planes of segments $AB$ , $BC$ and $CD$ have a unique common point $O$ , which is equidistant to each of the vertices. This, is the circumcenter of tetrahedron $ABCD$ .

Now, what about the orthocenter. Sure, we could try defining it to be the point of concurrence of the four altitudes from each vertex to the opposite face. The only issue is that this point does not necessarily exist.

Before we get into the gory details of how to fix this, it is best to have a quick refresher on how perpendicularity works in three dimensions.

We know that a line is said to be perpendicular to another line if the two lines intersect at a right angle, and it is fairly intuitive that two planes in space are said to be perpendicular if the dihedral angle at which they meet is a right angle. Moreover, a line is said to be perpendicular to a plane if it is perpendicular to every line in the plane that it intersects (play around with this if it feels awkward).

Our escape route shall be to define a new object called the Monge plane as the plane perpendicular to one edge of a tetrahedron which contains the midpoint of the opposite edge. In what follows, assume the circumcenter of the tetrahedron lies at the origin.

Theorem 1 (Monge Point)

The six Monge planes of a tetrahedron are concurrent.

Proof. We shall begin by making the seemingly unrelated observation that the segments connecting the midpoints of opposite edges of a tetrahedron bisect each other. Indeed, the midpoint of the segment joining the midpoints of $AB$ and $CD$ has position vector,

$G=\frac{\frac{A+B}{2}+\frac{C+D}{2}}{2}=\frac{A+B+C+D}{4}$

which is symmetric in $A$ , $B$ , $C$ and $D$ , settling the claim.

Now, let $\pi_{AB}$ denote the perpendicular-bisector plane of side $AB$ . Consider the reflection $\pi_{AB}'$ of $\pi_{AB}$ across point $G$ . This plane must be parallel to $\pi_{AB}$ and pass through the reflection of the midpoint of $AB$ across $G$ , which is the midpoint of segment $CD$ . Thus, $\pi_{AB}'$ is precisely the Monge plane of side $AB$ .

Since the perpendicular bisector planes concur at the circumcenter of $ABCD$ , it follows that the Monge planes concur at the reflection of $O$ across $G$ , the Monge point $M$ of the tetrahedron.

It also happens that the point $G$ above is the centroid of the tetrahedron, and the proof is similar to the two-dimensional case. Thus, the circumcenter, centroid and Monge point of a tetrahedron lie on a straight line known as the Euler line of the tetrahedron.

Moreover, the Monge point has position vector

$M = \frac{A+B+C+D}{2}$ .

To see why this point is considered the three-dimensional analogue of the orthocenter, note that the definition of a Monge plane reduces directly to an altitude for a triangle. Moreover, whenever the crude definition for the orthocenter exists, it coincides with the Monge point of the tetrahedron.

The next step obviously is to determine when the orthocenter of a tetrahedron does exist.

Theorem 2 (Orthocentric tetrahedra)

A tetrahedron has an orthocenter if and only if its opposite edges have perpendicular directions. Moreover, such a tetrahedron is said to be orthocentric or rectangular.

Proof. Suppose the altitudes concur at $H$ . Since $AH \perp BCD$ , line $AH$ is perpendicular to side $CD$ . Similarly, line $BH$ is perpendicular to side $CD$ . It then follows that line $AB$ is perpendicular to plane $ABH$ so it is also perpendicular to side $CD$ . The proof for the other pairs is similar.

Repeat the same argument for the other direction.

Moreover, it is also true that if any two pairs of opposite sides are perpendicular, then so is the last pair.

The next problem provides an alternative characterization for orthocentric tetrahedra.

Problem 3 (IMO Shortlist 1972/5) Prove that the four altitudes of a tetrahedron $ABCD$ are concurrent if and only if $AB^2 + CD^2 = BC^2 + AD^2 = CA^2 + BD^2$ .

It is not hard to see that

$AB^2+CD^2-AC^2-BD^2=-2 \,\overrightarrow{AD}\cdot\overrightarrow{BC}$ .

Thus,

$AB^2+CD^2=AC^2+BD^2 \iff \overrightarrow{AD}\cdot\overrightarrow{BC}=0 \iff AD\perp BC$ .

Repeating the argument for the other sides and applying the above theorem solves the problem.

When the orthocenter of a tetrahedron does exist, it is related to the orthocenters of the faces as follows.

Theorem 4 Suppose $ABCD$ is orthocentric, and $H_a$ is the foot of the altitude from $A$ to face $BCD$ . Then, $H_a$ coincides with the orthocenter of triangle $BCD$ .

Proof. Orthogonally project line $AB$ to side $BCD$ . Point $B$ stays fixed, and $A$ maps to $H_a$ . Thus, $BH_a \perp CD$ (confirm why!). Repeating the argument for the two other sides implies that $H_a$ is the orthocenter of $\triangle BCD$ .

Problem 3 from the 1983 IMO Longlist shows the converse result that if at least one altitude passes through the orthocenter of the opposite face, then the tetrahedron must be orthocentric.

You can also take this one step further and show that the tetrahedral Euler line maps to the Euler line of triangle $BCD$ under orthogonal projection at $A$ . Hint: first try showing that the orthogonal projection of the centroid is the nine-point center of the respective face.

The similarities with the two-dimensional case continue with the following result which shows that the orthocenter of a tetrahedron forms a five-point orthocentric system when it exists.

Theorem 5 Suppose $ABCD$ is orthocentric with orthocenter $H$ . Then any four of $A$ , $B$ , $C$ , $D$ and $H$ form an orthocentric tetrahedron.

Proof. For example, consider tetrahedron $HBCD$ . Since $AH \perp BCD$ the altitude from $H$ passes through $A$ . Furthermore, since $AB \perp CD$ and $AB \perp CH$ , it follows that $AB$ is the altitude from $B$ to $CHD$ . The other vertices work identically, implying that $A$ is this tetrahedron’s orthocenter.

Let us wrap up with an application of the above observations to a recent Olympiad problem. This is in a sense the three-dimensional analogue of the famous ‘Reflecting the orthocenter’ lemma from configurational geometry.

Problem 6 (Polish MO Finals 2011/5) In a tetrahedron $ABCD$ , the four altitudes are concurrent at $H$ . The line $DH$ intersects the plane $ABC$ at $P$ and the circumsphere of $ABCD$ at $Q\neq D$ . Prove that $PQ=2HP$ .

We shall use several results about circumspheres that you should feel free to look up if you have not encountered them before.

We know that $P$ must in fact be the orthocenter of face $ABC$ , so let $BP$ hit $AC$ again at $M$ , and let $CP$ hit $AB$ and $(ABC)$ again at $N$ and $R$ respectively.

Since $R$ lies on the circumsphere $\Omega$ of $ABCD$ (why?) we may consider the power of a point at $P$ with respect to $\Omega$ (think about why this is well defined) to note,

$\overline{PQ} \cdot \overline{PD}=\overline{PR} \cdot \overline{PC}= 2 \cdot \overline{PM} \cdot \overline{PC}=2 \cdot \overline{PB} \cdot \overline{PN}$

since $P$ and $R$ are symmetric about $\overline{AB}$ .

Now, let $DP$ hit the circumcircle of $\triangle BDM$ again at $S$ . Since $H$ is the orthocenter of $\triangle BDN$ (why?), due to the power of a point at $P$ with respect to $(BDM)$ we may similarly note,

$\overline{PB} \cdot \overline{PN}=\overline{PD} \cdot \overline{PS}=-\overline{PD} \cdot \overline{PH}$

since $H$ and $S$ are symmetric about $\overline{BM}$ . Combining these two relations solves the problem.
1. Here’s the link to the original slides which include diagrams. ↩︎
A pictorial proof of the Schroeder-Bernstein Theorem

August 30, 2026

Today we shall look at an interesting pictorial proof of the Schroeder-Bernstein Theorem which states that if $A$ and $B$ are sets and $f:A \to B$ and $g:B \to A$ are injections then there exists a bijection $h:A\to B$ .

Note that this is roughly saying $\text{card} A \le \text{card} B$ and $\text{card} B \le \text{card} A$ , so the two sets must have the same cardinality (and indeed this would be a complete proof for the case where sets $A$ and $B$ are both finite).

The intuitive way to think about this proof is to picture the two sets $A$ and $B$ and imagine mapping parts of each set until they are completely matched up. Our key idea will be to split the sets $A$ and $B$ into a series of ‘rings’.

First, separate the disk $gfA$ from $A$ , which is the image of $A$ under the map $g \circ f$ . Now, the area inside $A$ but outside this disc splits into two regions — the set of points in $A$ that do not lie in the image of $g$ (call it $A_0$ ) and the points that do lie in the image of $g$ but do not lie in $gfA$ (call it $A_1$ ). Do the same for $B$ , as shown in the diagram below.

To see why this separation is helpful, look at the image of $A_0$ under $f$ . They lie in the image of $f$ but outside the disc $fgB$ since $A_0$ is disjoint from the image of $g$ . Hence, $f$ is a natural bijection from $A_0$ to $B_1$ . Similarly, $g$ is a natural bijection from $B_0$ to $A_1$ .

So what the separation is really doing is pairing up two pairs of regions in each of the sets $A$ and $B$ which are mapped to each other under a bijection, just as we planned.

Moreover, the image of $gfA$ under $f$ must clearly lie within the disc $fgB$ and vice versa because the codomain of $f$ is $B$ , and similarly for the other set. Hence, we can apply the same argument for these smaller discs.

To be precise, we look at $gfA$ instead of $A$ and look at $fgB$ instead of $B$ . Then, the next two rings in $A$ and $B$ are,

$A_2 = gfA \setminus gfgB \ \ \ \ \ \ \ A_3 = gfgB \setminus gfgfA$

and

$B_2 = fgB\setminus fgfA \ \ \ \ \ \ \ B_3 = fgfA \setminus fgfgB$ .

As before, $f$ maps $A_2$ to $B_3$ and $g$ maps $B_2$ to $A_3$ .

Moreover, the rings $A_i$ and $B_i$ are disjoint and we have a bijection $\phi: \bigcup A_i \to \bigcup B_i$ defined by

But the issue is that this itself is not enough. To see why, consider the degenerate case where $A\equiv B \equiv \mathbb Z$ and $f \equiv g \equiv \text{id}$ . Clearly $A$ and $B$ are non-empty, but none of their elements lie in either of the rings $A_i$ (why?) — they appear to exist in an infinitely deep ‘core’.

To deal with these elements, let $A_* = A \setminus (\bigcup A_i)$ and $B_* = B \setminus (\bigcup B_i)$ . Observe that $f$ bijects $A_*$ to $B_*$ precisely since these elements do not lie in any of the rings. Hence, we can extend $\phi$ to a bijection $h:A \to B$ defined by
Prime Supports

August 22, 2026

Today we shall look at a fairly standard type of argument concerning prime divisors of integer sequences.

Given a sequence $(a_n)_{n\ge 1}$ , we say a prime $p$ is a prime divisor of $(a_n)$ if $p$ is a factor of some term of the sequence. The set of all prime divisors of $(a_n)$ is known as its prime support and is denoted $\mathcal{P}(a)$ . Our goal is to determine the nature of the prime support of a given sequence, and in most cases we wish to show that it is infinite.

The most direct way to approach such problems is to assume that the number of prime divisors of the sequence is only finite, say $\{p_1,p_2,\dots , p_k\}$ and explicitly construct a term of the sequence which has bounded $\nu_{p_i}$ with respect to each of these primes (in practice, usually just relatively prime). As a toy example, to see why the set of all prime divisors of $\mathbb{N}$ is infinite, note that $N=p_1p_2\dots p_k+1$ is relatively prime to all $p_1,\dots , p_k$ .

Problem 1 (Schur’s Theorem)

Prove that for all non-constant polynomials $P$ with integer coefficients the prime support of $\{P(i)\ne 0 : i\in \mathbb{N}\}$ is infinite.

Assume that the prime support is in fact finite, say $\{p_1,\dots , p_k\}$ and let $m_i$ denote the term such that $p_i \mid P(m_i)$ and say $e_i = \nu_{p_i}(P(m_i))$ .

But now, consider a positive integer $N$ such that $N \equiv m_i \pmod{p_i^{e_i+1}}$ . Then, $\nu_{p_i}(P(N))=e_i$ (why?) for all such $N$ . However, by the Chinese Remainder theorem, there exists infinitely many such $N$ implying that there exists some such $N$ for which $|P(N)| > \prod_{i=1}^kp_i^{e_i}$ (why?). This choice of $P(N)$ must then have a prime factor outside our assumed set, a contradiction.

Try showing that the prime support of the set $\{2^i+3^i : i\in \mathbb{N}\}$ is infinite using the same approach, with Fermat’s Little Theorem as the construction tool.

This is also where our heavyweights Zsigmondy’s and Kobayashi’s reign supreme, so it is often useful to have them at the back of your mind when trying these problems. 2000 IMO Problem 5 and 2018 USA TSTST Problem 8 are a couple of great examples.

Next, we will look at the interplay between $p-$ adic valuations and size arguments, which is one of the most common tropes throughout problems of this species.

We begin with one of the most classical examples. The method below generalizes to other polynomial recurrences of first order and can be used to solve 2016 China Team Selection Test Problem 4, 2023 Silk Road MO Problem 3, 2018 MEMO Team Round Problem 7, and 2018 Bulgarian MO Problem 5 among others.

Problem 2 (IMO Shortlist 2014 N7)

Let $c \ge 1$ be an integer. Define a sequence of positive integers by $a_1 = c$ and $a_{n+1}=a_n^3-4c\cdot a_n^2+5c^2\cdot a_n+c$ for all $n\ge 1$ . Prove that for each integer $n \ge 2$ there exists a prime number $p$ dividing $a_n$ but none of the numbers $a_1 , \ldots , a_{n -1}$ .

In order to facilitate our observations, we first normalize the sequence by setting $(x_n)$ be the sequence such that $x_0=0$ and $x_n=\frac{a_n}{c}$ for all $n\ge 1$ . It is not hard to see that this sequence satisfies the recurrence relation

$x_{n+1}=c^2(x_n^3-4x_n^2+5x_n)+1$

for all integers $n\ge 0$ . Since $x_n$ is clearly coprime to $c$ , it suffices to show that $x_{n+1}$ has a prime factor which does not divide any of $x_1,\dots , x_n$ for all $n \ge 1$ .

We begin by making two observations. First, we wish to show that $x_i \equiv x_j \pmod{x_m}$ if $i \equiv j \pmod{m}$ . To see why, we proceed via induction, for fixed $m$ . Since $x_0 \equiv x_m \pmod{x_m}$ for all $m$ , the base case is clear and for the inductive step simply note,

$x_{m+i+1} \equiv c^2(x_{m+i}^3-4x_{m+i}^2+5x_{m+i})+1 \equiv c^2(x_i^3-4x_i^2+5x_i)+1 \equiv x_{i+1}$

modulo $x_m$ . In fact, if $i,j \ge 2$ we can take the claim one step forward and prove the same result modulo $x_m^2$ . The approach is once again induction, with the inductive step following trivially from the prior equation. For the base case simply note $x_{m+1}\equiv 5c^2x_m+1 \pmod{x_m^2}$ so,

$x_{m+1}^3-4x_{m+1}^2+5x_{m+1} \equiv (5c^2x_m+1)^3-4(5c^2x_m+1)^2+5(5c^2x_m+1)$

$\equiv (15c^2x_m+1)-4(10c^2x_m+1)+5(5c^2x_m+1) \equiv 2 \pmod{x_m^2}$

which immediately implies $x_{m+2} \equiv x_2 \pmod{x_m^2}$ as desired.

Second, we observe that the sequence $(x_n)$ is pretty fast-growing. In particular, we claim that $x_n>x_1x_2\dots x_{n-1}$ for all $n \ge 2$ . The base cases $x_2$ and $x_3$ being clear, we tackle the inductive step by noting that $(x_n)$ is strictly increasing so,

$x_{n+1}>x-n^3-4x_n^2+5x_n>7x_n^2-4x_n^4>x_n^2$

for all $n\ge 3$ , and the inductive hypothesis applies.

Now, we are in a position to tackle the problem. By our second observation, there must exist some prime $p$ for which $\nu_p(x_n)>\max{\nu_p(x_1),\dots , \nu_p(x_{n-1})}$ (why?) and if it is not a new prime factor of the sequence, let $x_k$ denote the earliest term such that $p \mid x_k$ . Since $x_{n-1}$ and $x_n$ are clearly coprime by the nature of our recursion and $x_1=1$ , we have $n-2 \ge k \ge 2$ .

Now, due to the minimality of $k$ it follows that $k \mid n$ (why?) so we further have that $x_n \equiv x_k \pmod{x_k^2}$ . However, this is a clear contradiction since if $\alpha = \nu_p(x_k)$ we must have $p^{\alpha +1} \mid x_n$ and $p^{\alpha+1}\mid x_k^2$ which implies $p^{\alpha+1} \mid x_k$ as well, absurd.

Problem 3 (Brazil Undergraduate MO 2017/2)

Let $a$ and $b$ be fixed positive integers. Show that the set of primes that divide at least one of the terms of the sequence $a_n = a \cdot 2017^n + b \cdot 2016^n$ is infinite.

Here, we assume that the sequence has only finitely many prime divisors say $\{p_1,\dots , p_k\}$ . Observe that $\gcd(a\cdot 2017^n,b\cdot 2016^n)$ is bounded above by some constant $M$ since $\gcd(2016,2017)=1$ . The trick is to consider the index of the largest prime power dividing a term $a_n$ and call it $f(n)$ .

Now by the Pigeonhole principle, among any block of $k+1$ consecutive terms of the sequence, there must exist $i$ and $j$ in the range such that $f(i)=f(j)$ .

Thus, for all positive integers $n$ , there exists some $0 < m \le k$ such that $f(n)=f(n+m)$ . Let $\min(v_{p_j}(a_n), v_{p_j}(a_{n+m}))=\ell$ , then we have

$p_j^{\ell} \mid a \cdot 2017^n+b \cdot 2016^n$ and $p_j^{\ell} \mid a \cdot 2017^{n+m}+b \cdot 2016^{n+m}$ , so $p_j^{\ell} \mid b\cdot 2016^n \cdot (2016^m-2017^m)$ .

However, that forces $\sqrt[k]{2017^n} \le p_j^{\ell} \le M \cdot (2017^k-2016^k)$ which is a contradiction as $n$ goes to infinity.

The framework of the above solution can be adapted for a wide range of problems, including this floors problem by Atul Shatavart Nadig and Pranjal Srivastava, involving sequences $(x_n)$ for which a ‘nice’ choice of integers $m,n$ can be found such that $|mx_i-nx_j|$ is in some sense ‘bounded’ for our choice of $f(i)=f(j)$ .

The trick employed in our final problem is slightly more niche but is still important to note.

The key idea is that $A$ is a set of positive integers such that $\sum_{a\in A}\frac{1}{a}$ diverges, then the prime support of $A$ must be unbounded. Indeed, if it were finite, say $\{p_1,p_2,\dots , p_k\}$ then,

$\sum_{a\in A}\frac{1}{a}\le \prod_{i=1}^k\left(1+\frac{1}{p_i}+\frac{1}{p_i^2}+\dots \right) = \prod_{i=1}^k \left(\frac{p_i}{p_i-1}\right)$

which is a clear contradiction. We shall now look at an example.

Problem 4

Denote $p_n$ by the $n$ th prime number in ascending order. Prove that the sequence $\{\lfloor \lambda p_n \rfloor\}_{n=1}^{+\infty}$ has infinitely many prime divisors where $\lambda\in \mathbb{R}_{>1}$ .

Simply note that,

$\sum_{i=1}^{\infty} \frac{1}{\lfloor \lambda p_i \rfloor} \ge \sum_{i=1}^{\infty} \frac{1}{\lambda p_i}= \frac{1}{\lambda} \sum_{i=1}^{\infty} \frac{1}{p_i}$

which clearly diverges. Now that felt almost like cheating.
Cyclic Digits

August 16, 2026

Today we shall have a look at a neat little trick that is more commonly seen in computational contests, but occasionally makes an appearance in Olympiad problems as well.

Let $X=\overline{d_{n-1}d_{n-2}\dots d_0}_b= \sum_{i=0}^{n-1} d_ib^i$ be an integer in base- $b$ where $0 \le d_i \le b-1$ for all $0 \le i \le n-1$ , as usual. Observe that if $\rho(X)=\overline{d_{n-2}\dots d_0d_{n-1}}$ is the integer obtained by moving the first digit to the end,

$\rho(X)=bX-d_{n-1}(b^n-1)$

Hence, it is clear that $\rho(X) \equiv bX \pmod{b^n-1}$ . More generally, $\rho^k(X) \equiv b^kX \pmod{b^n-1}$ . Thus an $n-$ digit base- $b$ number modulo $b^n-1$ is naturally a circular string of digits. Multiplying by $b$ rotates the circle by one position, and a carry beyond the $n-$ th position wraps back to the first position.

Let us begin with the following classical problem.

Example 1 (IMO Shortlist 1993 N3)

Let $a,b,n$ be positive integers, $b > 1$ and $b^n-1\mid a.$ Show that the representation of the number $a$ in the base $b$ contains at least $n$ digits different from zero.

Suppose $a=\sum_{i=1}^tc_ib^{e_i}$ where $1\le c_i \le b-1$ where $t$ is the number of non-zero digits of $a$ . We wish to show that $t$ is at least $n$ , given that $a$ is a multiple of $b^n-1$ . Our goal then turns to showing that the sum of digits of $a$ is at least $n(b-1)$ , since each digit is at most $b-1$ .

Naturally, since $b^n\equiv 1 \pmod{b^n-1}$ , the first thing to try is reducing every exponent $e_i \pmod{n}$ . Replacing $e_i \equiv r_i \pmod{n}$ , we can define $S_0 =\sum_{i=1}^t c_ib^{r_i}$ which since $S_0 \equiv a \pmod{b^n-1}$ implies $S_0 \ge b^n-1$ .

But, this alone is useless. Note that a digit sitting in the $b^{n-1}-$ position contributes far more to the sum $S_0$ than a digit at the units position. We are trying to bound the number of non-zero digits — which should not depend on their positions, but our inequalities are highly position dependent.

To see what I mean, consider the example $b=10$ and $n=3$ . We want to understand multiples of $10^3-1=999$ , so reducing the powers of $10$ modulo $999$ gives

$a \equiv A+10B+100C \pmod{999}$

for positive integers $A,B,C$ . Thus, $A+10B+100C$ is a multiple of $999$ whenever $a$ is. However, $C$ is weighted 100 times as much as $A$ , and $B$ is weighted 10 times as much, so this does not tell us much about $A+B+C$ , the actual digit sum.

However, multiplication by $10$ shows that $10A+100B+C$ is a multiple of $999$ , and similarly that $100A+B+10C$ is a multiple of $999$ . Hence, each of these are at least $999$ so summing and dividing across by 111 immediately spits out the inequality $A+B+C \ge 27$ , which matches our target.

The key idea is that the contribution by a non-zero digit is not felt only from its current position but throughout all of the possible positions in the $n-$ digit number. This intuition appears time and time again in these kinds of problems.

Returning to our problem, for $0 \le j \le n-1$ , define the sums

$S_j = \sum_{i=1}^t c_ib^{e_i+j \pmod{n}}$ .

In other words, throw the digits onto a circle, and then rotate it exactly $j$ steps. Note that as we perform the rotations, any digit $c_i$ visits each of the $n$ positions exactly once. So its total contribution to $S_0+S_1+\dots S_{n-1}$ is exactly

$c_i(b^0+b^1+\dots + b^{n-1})=c_i\frac{b^n-1}{b-1}$ .

Summing across all the $t$ non-zero digits we have,

$\sum_{i=0}^{n-1}S_i = \frac{b^n-1}{b-1}\sum_{i=1}^t c_i$

which since $S_0,\dots , S_{n-1}$ are all multiples of $b^n-1$ implies

$\frac{b^n-1}{b-1}\sum_{i=1}^t c_i \ge n(b^n-1)$ so $\sum_{i=1}^t c_i \ge n(b-1)$ !

Now, this next problem might seem a bit unreasonable — especially for those who haven’t seen this trick before. So, it is best to first attempt 2025 CMIMC A5, which is basically the same problem but far less scary.

Example 2 (IMO Shortlist 2022 N5)

For each $1\leq i\leq 9$ and $T\in\mathbb N$ , define $d_i(T)$ to be the total number of times the digit $i$ appears when all the multiples of $1829$ between $1$ and $T$ inclusive are written out in base $10$ . Show that there are infinitely many $T\in\mathbb N$ such that there are precisely two distinct values among $d_1(T)$ , $d_2(T)$ , $\dots$ , $d_9(T)$ .

The idea is to pick $T=10^{k}-1$ where $\phi(1829) \mid k$ since $1829|10^k-1$ for this choice of $k$ , and write every integer multiple of 1829 upto $T$ as a $k-$ digit string, allowing leading zeros. Hence, for any multiple $\overline{a_ta_{t-1}\dots a_1}$ of 1829, it’s cyclic rotation $\overline{a_{t-1}\dots a_1a_t}$ is equivalent modulo $10^k-1$ and is hence also divisible by 1829.

Now, since 1829 is a bit of a mouthful, let us pick the smaller choice 37 instead. Why 37? Because it so happens that 37 is a factor of 999, so $T$ remains within our sights. The list of multiples of 37 up to 999 goes as follows,

037, 074, 111, 148, 185, 222, 259, 296, 333, 370, 407, 444, 481, 518, 555, 592, 629, 666, 703, 740, 777, 814, 851, 888, 925, 962, 999

We now group the multiples which are cyclic shifts of each other, while allowing for leading zeros,

037
370
703

074
740
407

148
481
841

185
851
518

259
592
925

296
962
629

and of course, 111, 222, 333, 444, 555, 666, 777, 888 and 999.

Notice that the distribution of digits in the hundreds, tens and units places are exactly identical! Hence, we only need focus on the units position.

Returning to the problem, the multiples of 1829 from 1 to our choice of $T$ have the same distribution of digits in each of the positions from $10^{t-1}$ through the units position. Hence, we only need to count the number of times each non-zero digit occurs in the units position. However, since 1829 and 10 are relatively prime, the units digit of multiples of 1829 are periodic modulo 10.

Observe that the number of multiples of 1829 from 1 to $T$ is $\frac{T}{1829} \equiv \frac{-1}{-1} \equiv 1 \pmod{10}$ , so each of the digits 0 through 8 occur $\lfloor \frac{T}{18290} \rfloor$ times while 9 occurs $\lceil \frac{T}{18290} \rceil$ times, implying that $d_1(T)=d_2(T)=\dots = d_8(T) \ne d_9(T)$ , as desired.

For the finale, we shall have a look at a problem of a more constructive flavour. The solution to this problem can seem almost magical without the underlying motivation of cyclic shifts.

Example 3 (USAMO 2013/5)

Given positive integers $m$ and $n$ , prove that there is a positive integer $c$ such that the numbers $cm$ and $cn$ have the same number of occurrences of each non-zero digit when written in base ten.

Well, by now you know the drill — we would love to be able to find some integer $c$ such that the two multiples $cn$ and $cm$ are cyclic shifts of each other. Note that it suffices to deal with the case where $n$ is relatively prime to 10 and $n<m$ (confirm why!).

Consider $c$ and $k$ such that $10cm-10^k+1=cn$ . If we can find $k$ such that $cm$ has leftmost digit 1 at the $10^k-$ position, we would be done. Rearranging, $c= \frac{10^k-1}{10m-n}$ . However observe,

$99\dots 9.9=\frac{10^k-1}{10} < \frac{10^k-1}{10m-n}m < \frac{10^k-1}{9}=11\dots 1$

which implies that the leading digit is indeed at the $10^k-$ position and is 1. We now need to pick $k$ such that this choice of $c$ is an integer, which is straightforward.
Not all is grey

August 2, 2026
Another IMO has come and gone, leaving us right where we started. Across 31 years of participation, Sri Lanka has cleared a 50% relative team score¹ exactly once, while the average team rel. across the last six years is just 32.8%.

One might ask why a nation with such a ‘proud intellectual tradition’ performs so poorly at the IMO—but then again, math is hard, world-class training costs money, and it is far easier to pretend the gap is too wide to be bridge. However, the truth is that Sri Lanka is performing far below (what I personally believe is) their natural potential.

Anyway, here are some quick thoughts in my head.

Going around in cycles

If one looks at the worm graph, the team performance trends upwards in cycles of three years — enough time for a handful of contestants to improve enough to supersede the vast majority of their peers forming what we call a ‘generation’. This batch of contestants will routinely make the team and naturally their performance will improve over time, but once they retire the entire country’s performance resets.

Sure, certain generations might do better than others but the absence of overall improvement over time is disturbing. The main issue is that there is little to no cross-generational flow of knowledge.

Progress in mathematics is accumulative, and the IMO is no different. Imagine if every working mathematician throughout history had to start from scratch — it could hardly be supposed that humanity would move further than the contents of a few volumes of the ‘Elements’. Euler or Gauss might have been able to approximate $\pi$ but the modern framework of mathematics would never be conceived.

In short, it is absolutely necessary that past contestants give back to future ones. And I don’t mean teaching a couple random lectures the week before the IMO, but consistent supportive efforts, even if that means dropping guidance through email or messaging. Just communication. Intuition is contagious, you just need to allow enough surface area for the diffusion.

I believe that what sets apart strong countries at the IMO is not merely that their training programs are stronger², but that they foster a much stronger relation between the trainer and the trainee, and just as importantly among the students themselves.

Instant Gratification

People say that math contests are not for everyone and one thing they mean by that (especially in the context of proof-based contests like the IMO) is that it is difficult to stop yourself expecting quick progress. Most of the students who get into math contests are here for a reason — they are good at math. Going from that mentality to accepting that it is totally normal to be unable to make a single piece of progress in a whopping four and a half hours (maybe more if you’re trying the problems at home) is hard.

For this reason, students might simply contend themselves with less rigorous contests with easier problems. Despite this being a problem for all prospective contestants around the world, it is especially prominent in Sri Lanka due to the way the system is structured. When the highest level of competition endorsed by the Ministry of Education is the ‘International Mathematics Competition (IMC)’, it is only natural that the students gravitate towards these options.

As a result, a vast majority of students never even enter proof-based contests and the ones that do spend a considerable fraction of their time preparing for the less intense and higher reward counterparts simultaneously. And in reality, the skills these contests reward are totally different. In the words of Tanya Khovanova it’s like ‘you got to the national swimming championship because you are a great runner, but you do not know how to swim.’³

Reach

The ‘Sri Lankan Mathematics Competition (SLMC)’ is supposed to be the entry point to the entire process of selecting the IMO Team. Today most schools have (or pretend to have) no idea what the SLMC is. For reference, in 2019 (the last year in which the test was administered onsite) over 4400 students (about 0.2% of all middle and highschoolers) took the SLMC. In 2026, the SLMC (which is fully online) doesn’t even contribute to team selection any more, and a few hundred students took its newer Junior/Intermediate counterparts.

The below excerpt from this article encapsulates this nicely (albeit in the context of the United States)

That’s what’s missing in what I see around me — the idea that “you will take the AMC” being ordinary school business at any more than a handful of places […]. There are many schools where the AMC is only offered because some long-veteran teacher has always done it and insists on it. Three years after that teacher retires, not only will the school no longer participate, but no one will remember that the school ever participated. Perhaps there’s enough life in a non-school model — but I have trouble seeing how that can be large enough or inclusive enough.

That’s the key word — ‘a school model’. It is absolutely essential to establish an official School Center framework. It provides credibility to the exam, because now it’s held physically under standard examination procedure and also extends its reach, because it’s a thousand times less hustle to just sign up for and sit an exam given at your highschool (or one a few minutes drive away).

There are all sorts of other angles to this — the highly competitive GCE Advanced Level environment, (largely) unsupportive highschool teachers and rising sea levels threatening to engulf the entire country; but the above factors are the most influential and possibly the most direct to address.

Now, not all is grey and there is still a sliver of hope, but we need to make a move fast.
1. This is the percentage of teams which have a lower total. I personally do not think that medal tally is a great metric for how well a country performs on the IMO ↩︎
2. Indeed some of the top countries are now choosing to have fewer and fewer sessions on actual Olympiad mathematics at their national training camps ↩︎
3. Actually, the original post is in the context of how short answer contests do not make for great selection tests leading up to the IMO team, but you get the idea ↩︎
D-Excircle of the Orthic triangle

March 28, 2026
Today we shall have a (very brief) look at the $D-$ excircle of the orthic triangle which appeared recently on the Vietnam Team Selection Test. This configuration can be transposed to the standard excircle configuration by shifting the reference triangle to the orthic triangle, but certain results are interpreted more naturally in an orthic setting.

As usual, a clickable GeoGebra link is attached to the following diagram.

A summary of the key results pertaining to this configuration,
1. An easy angle chase shows that is the incenter of and that , and are the , and excenters of the orthic triangle.
  - Hence, the feet $X$ , $Y$ and $Z$ of the perpendiculars from $A-$ to the sides $EF$ , $DF$ and $DE$ respectively are the corresponding extouch points of the same triangle.
  - Further, one can then observe that the lines $\overline{BC}$ and $\overline{YZ}$ are parallel.
2. The second intersection of line with and the second intersection of line with both lie on the excircle as well.
  - It can then be seen that quadrilaterals $BXPE$ and $CXQF$ are both cyclic. Also, by Reim’s theorem note that the quadrilateral $BCPQ$ is cyclic.
  - The circles $(BDY)$ and $(CDZ)$ can also be shown to intersect on the circumcircle of the orthic triangle $(DEF)$ .
3. The intersection of line with line and the intersection of with line can also be seen to lie on the circle via angle chase.
  - Points $U$ and $V$ also lie on the circles $(QEZ)$ and $(PFY)$ respectively. Hence, Power of a Point at $X$ implies that point $X$ lies on the radical axis of circles $(PFY)$ and $(QEZ)$ , which is the statement of 2025 Vietnam TST Problem 3.
  - Further, since quadrilaterals $BCEF$ and $BCUV$ are both cyclic, Reim’s theorem implies that lines $\overline{EF}$ and $\overline{UV}$ are parallel.
4. Quadrilaterals and are both cyclic, so it follows that also lies on the radical axis of circles and . This can also be shown quite simply using complex numbers, with as the unit circle.
  - Hence, the second intersection points of circles $(PFY)$ and $(QEZ)$ with $YZ$ , $N$ and $L$ are symmetric with respect to point $M$ .
  - Thus, point $M$ is the center of homothety mapping triangle $DYZ$ to triangle $HNL$ . Moreover, point $R$ is the center of homothety mapping the triangle $FL'S$ to $DYZ$ , and similarly.
  - Some angle chasing can then be used to show that points $U$ , $V$ , $N$ , $L$ and $H$ all lie on a circle.
  - It is also true the points $B$ , $C$ , $U$ , $V$ , $N$ and $L$ lie on the same conic, which gives us a plethora of collinearity/concurrency results via Pascal’s theorem.
Farey Sequences

February 7, 2026

Today we shall look at a class of sequences with a rich and deep history beginning from their earliest appearance in a problem that appeared in the Ladies’ Diary, which have numerous applications in number theory and combinatorics, and are lately making an appearance in math Olympiad problems.

The Farey sequence of order $n$ , denoted $\mathcal{F}_n$ is the sequence of completely reduced fractions, usually between 0 and 1, which have denominators less than or equal to $n$ , arranged in order of increasing size. For example,

$\mathcal{F}_8 = \left \{\frac{0}{1}, \frac{1}{8}, \frac{1}{7}, \frac{1}{6}, \frac{1}{5}, \frac{1}{4}, \frac{2}{7},\frac{1}{3}, \frac{3}{8}, \frac{2}{5},\frac{3}{5}, \frac{1}{2}, \frac{4}{7}, \frac{3}{5}, \frac{5}{8}, \frac{2}{3},\frac{5}{7}, \frac{3}{4}, \frac{4}{5}, \frac{5}{6}, \frac{6}{7}, \frac{7}{8}, \frac{1}{1}\right \}$

1. Basic Properties

First, observe that the terms which appear in the Farey sequence of order $n$ have denominators $1,2,\dots , n$ (which is of course obvious from the definition) and since they are completely reduced, the numerators are coprime to the denominators. Thus, there exists exactly $\phi(i)$ fractions with denominator $i$ for all $1 < i \le n$ and indeed, the Farey sequence of order $n$ has exactly $\sum_{i=1}^n \phi(i)+1$ terms.

Summing across the fractions with the same denominator by pairing, it is also not hard to show that the sum of fractions in the Farey sequence of order $n$ is equal to $\frac{1}{2}\left[1+\sum_{i=1}^n \phi(i)\right]$ , solving this unsourced problem from AoPS.

We shall now look at a few well known properties of the Farey sequences.

Theorem 1 (Farey Neighbours)

The fractions $\frac{a}{b}$ and $\frac{c}{d}$ are neighbours in a Farey sequence if and only if $\frac{a}{b}-\frac{c}{d}=\frac{1}{bd}$ or equivalently, $bc-ad=1$ .

We give two proofs of this result, each interesting in it’s own right.

First proof, bounding. Consider a term $\frac{a}{b} < 1$ in a Farey sequence. We shall determine the next term in the Farey sequence. Since $\gcd(a,b)=1$ , there exists integers $x$ and $y$ satisfying the equation,

$ax-by=1$

by Bezout’s Lemma. In particular, if $(x_0,y_0)$ is a pair of solutions, then all pairs of the form $(x_0+rb,y_0+ra)$ where $r$ is an integer are also solutions. We can now consider $r$ such that $n-b < y_0+rb \le n$ and look at the pair $c=y_0+rb$ and $d=x_0+ra$ . Since this is a pair of solutions to the above equation, $c < d < n$ so $\frac{c}{d}$ is a member of $\mathcal{F}_n$ .

Clearly, $\frac{c}{d} = \frac{a}{b}+\frac{1}{bd} > \frac{a}{b}$ so $\frac{c}{d}$ appears after $\frac{a}{b}$ in $\mathcal{F}_n$ . Now, let $\frac{a}{b}<\frac{c'}{d'}$ be the next term in the Farey sequence $\mathcal{F}_n$ . If this is distinct from $\frac{c}{d}$ , then $\frac{a}{b}< \frac{c'}{d'}< \frac{c}{d}$ and we have

$\frac{c}{d} - \frac{c'}{d'} = \frac{cd'-c'd}{dd'} \ge \frac{1}{dd'}$ and $\frac{c'}{d'} - \frac{a}{b}=\frac{bc'-ad'}{bd'} \ge \frac{1}{bd'}$ .

However, this is an immediate contradiction since

$\frac{1}{bd} = \frac{ac-bd}{bd} = \frac{c}{d}- \frac{a}{b} = \left(\frac{c}{d} - \frac{c'}{d'}\right) + \left(\frac{c'}{d'} - \frac{a}{b}\right) \ge \frac{1}{dd'}+\frac{1}{bd'} = \frac{b+d}{bdd'} > \frac{n}{bdd'} \ge \frac{1}{bd}$ .

where $b+d>n$ follows by our choice of $r$ .                                                                                                                                                 $\square$

Second proof, geometric. The idea is to represent the fraction $\frac{a}{b}$ by the ordered pair of integers $(b,a)$ and throw it on the lattice plane.

We say a point is visible if the line segment $OP$ does not contain any lattice points in it’s strict interior. It is not hard to see that the point $P(x, y)$ is visible if and only if $\gcd(x, y) = 1$ . This means that the set of fractions in the Farey sequences of order at most $n$ corresponds exactly to the set of visible points in the region $\Delta$ bounded by the lines $y = 0$ , $x = n$ and $y = x$ .

Now, consider a moving line $\ell$ passing through the origin $O$ and rotating clockwise. It is clear that passes through the visible points $P(x, y)$ in decreasing order of $\frac{y}{x}$ since $\tan \angle (\ell, \ell_x) = \frac{y}{x}$
where $\ell_x$ denotes the $x$ −axis.

Let $A(x_a, y_a)$ and $B(x_b, y_b)$ be two points on which lands consecutively. Since there exists no visible points within the angle $\angle (OA, OB)$ it is not hard to see that there exists no visible points (and hence no lattice points) within the parallelogram $OACB$ . By Pick’s Theorem it then follows that the area of the parallelogram $OACB$ is 1.

We can alternately calculate the area of the parallelogram $OACB$ as,

$[OACB] = |x_ay_b-x_by_a|$

which implies the result.                                                                                                                                                                                             $\square$

This is already sufficient to solve the following interesting problem given at a mock for the China National HS Math League and 2002 Kürschák Problem 2 which uses the cool result that the ratios of consecutive Fibonacci numbers are also consecutive Farey fractions.

An immediate corollary of this result is the fact that if the fractions $\frac{a}{b} < \frac{p}{q} < \frac{c}{d}$ are a trio of neighbours in a Farey sequence, then $\frac{p}{q} = \frac{a+c}{b+d}$ which can be verified by applying the above property on each pair of neighbours.

Another observation is that $\frac{a+c}{b+d}$ must be completely reduced since otherwise, this fraction lies strictly between $\frac{a}{b}$ and $\frac{c}{d}$ and has denominator at most $\frac{b+d}{2}<d$ .

Theorem 2 (Mediant Property)

If $\frac{a}{c}$ and $\frac{c}{d}$ are neighbours in a Farey sequence then the first term that appears between them as the order of the Farey sequence is incremented is their mediant, $\frac{a+c}{b+d}$ .

Proof. If exactly one new fraction appears between $\frac{a}{b}$ and $\frac{c}{d}$ this follows from the above corollary. Hence, at least two new fractions must appear. However it is not hard to see
that the newly added terms in the Farey sequence of order $n$ must all have denominator $n$.

If $\frac{a}{b} < \frac{m}{n}<\frac{m+\epsilon}{n}< \frac{c}{d}$ for some strictly positive integer $\epsilon < n-m$ note that $mb - an \ge 1$ and $md + \epsilon d \le cn$ so

$\frac{cn-\epsilon d}{d} \ge m \ge \frac{an+1}{b}$

and we have $(bc-ad)n > (b\epsilon +1)d$ which since $bc-ad=1$ by the Farey neighbour’s condition implies

$n > (b \epsilon +1)d \ge (b+1)d> b+d$

which is a clear contradiction.                                                                                                                                                                               $\square$

Surprisingly, this result has also appeared in recent olympiads, most notably as 2024 Mexico TST Problem 1.

This result is crucial since it allows us to iteratively construct all terms that appear in a Farey sequence (and by extension all rationals between 0 and 1).

Starting with $\frac{0}{1}$ and $\frac{1}{1}$ , placed at either end of a segment of length 1, in each step write the mediants of each pair of neighbouring fractions at the midpoint of their positions. Optionally, one can write the fractions generated in each step in a new level. This structure is sometimes refered to as the Stern-Brocot tree (when all edges are deleted except those between a fraction and it’s two children) or the Neighbour’s graph of Farey fractions. Given below is the graph upto 5 generations, with terms greater than 1 included.

We can immediately note that this graph is outerplanar — in each stage, the newly added vertices are connected to two neighbouring vertices which belong to the outer face. Since it is well known that outerplanar graphs on $n$ vertices have at most $2n-3$ edges, this immediately solves 2020 USAMO Problem 4.

Another important application of the Farey sequence is it’s connection to continued fractions and rational approximations.

2. Diophantine Approximations

By the denseness of the rational numbers, we know that for every irrational number $x$ and $\epsilon > 0$ , there exists integers $p$ and $q$ with

$\left | \frac{p}{q}-x\right |<\epsilon$ .

For example, consider $\sqrt{2} = 1.41421356237...$ . Clearly, $\frac{141421}{100000}$ is a really good rational approximation but this is pointless. The goal is to obtain as close an approximation as possible, using small denominators.

Theorem 3 (Weak Diophantine Approximation)

For every positive irrational number $\alpha$ , there exists infinitely many pairs of integers $(p,q)$ such that $\left|\frac{p}{q}-\alpha\right|< \frac{1}{2q}$ .

Proof. The idea is to consider for each positive integer $q_0$ , the positive integer $p_0$ such that $\frac{p_0-1}{q_0} < \alpha < \frac{p_0}{q_0}$ and pick the fraction which is closer to $\alpha$ . The interval $\left(\frac{p_0-1}{q_0},\frac{p_0}{q_0}\right)$ is of length $\frac{1}{q_0}$ meaning that our approximation is off by at worst $\frac{1}{2q_0}$ , as desired.                                                                        $\square$

First of all, the fact that such an approximation exists for every positive integral denominator $q$ is a red light, and indeed these approximations are not very good. For example, to get an approximation for $\sqrt{2}$ that is at most $1 \times 10^5$ off, we need to use a denominator of at least $5000$ which is barely any better than what we started with.

Using the knowledge of Farey fractions however, it is possible to significantly improve this approximation.

Theorem 4 (Strong Diophantine Approximation)

For every positive irrational number $\alpha$ , there exists infinitely many pairs of integers $(p,q)$ such that $\left|\frac{p}{q}-\alpha\right|< \frac{1}{2q^2}$ .

Proof. We only consider the case when $0 < \alpha < 1$ , it is easy to see that the others follow by shifting. Since $\alpha$ is in this range, it must lie strictly between two terms of the Farey sequence of order $n$ , say $\frac{a}{b} < \alpha < \frac{c}{d}$ .

By the AM-GM inequality we know that

$\frac{1}{2b^2}+\frac{1}{2d^2} \ge \frac{1}{bd} = \frac{c}{d}-\frac{a}{b}$ ,

the latter equality following from the Farey Neighbour’s theorem. However this means

$\left |\frac{c}{d}-\alpha \right| + \left |\frac{a}{b}-\alpha\right| = \frac{c}{d} - \frac{a}{b} \le \frac{1}{2b^2}+\frac{1}{2d^2}$

so one of the inequalities $\left |\frac{a}{b}-\alpha\right|\le \frac{1}{2b^2}$ and $\left |\frac{c}{d}-\alpha\right|\le \frac{1}{2d^2}$ must hold. Moreover, as the order of the Farey sequence increases, every rational number between 0 and 1 appears, and we obtain infinitely many (increasingly better) approximations of $\alpha$ .                                                                                                                               $\square$

Surprisingly, we can do yet better solely employing Farey fractions by being a little smarter.

Theorem 5 (Hurwitz’s Approximation)

For every positive irrational number $\alpha$ , there exists infinitely many pairs of integers $(p,q)$ such that $\left|\frac{p}{q}-\alpha\right|< \frac{1}{\sqrt{5}q^2}$ .

Proof. As before, consider the case when $0 < \alpha < 1$ and let $\alpha$ lie strictly between the Farey neighbours $\frac{a}{b}$ and $\frac{c}{d}$ . In particular, since $\frac{a}{b}<\frac{a+c}{b+d}<\frac{c}{d}$ it is clear that $\alpha$ must lie strictly within one of these two intervals. Without loss of generality, assume it lies strictly between $\frac{a+c}{b+d}$ and $\frac{c}{d}$ .

Working towards a contradiction, assume that each of the inequalities $\left |\frac{c}{d}-\alpha\right|\ge \frac{1}{\sqrt{5}d^2}$ , $\left |\frac{a}{b}-\alpha\right|\ge \frac{1}{\sqrt{5}b^2}$ and $\left |\frac{a+c}{b+d}-\alpha\right|\ge \frac{1}{\sqrt{5}(b+d)^2}$ hold.

However, adding the third inequality with each of the other two in turn yields,

$\frac{1}{bd} = \frac{c}{d}-\frac{a}{b} \ge \frac{1}{\sqrt{5}}\left(\frac{1}{b^2}+\frac{1}{d^2}\right)$

and

$\frac{1}{d(b+d)} = \frac{c}{d}-\frac{a+b}{c+d} \ge \frac{1}{\sqrt{5}}\left(\frac{1}{d^2}+\frac{1}{(b+d)^2}\right)$

utilizing both the Farey neighbours and Mediant properties. Thus, $b^2+d^2 \le \sqrt{5}bd$ and $d^2 + (b+d)^2 \le \sqrt{5}d(b+d)$ . Summing these two inequalities we have,

$\sqrt{5}d(2b+d) \ge 2b^2+3d^2+2bd$ which rearranges to $0 \ge \frac{1}{2}\left((\sqrt{5}-1)d-2b\right)^2$ which is a clear violation of the trivial inequality unless equality holds. However, equality cannot hold since $\sqrt{5}$ is irrational, and the result follows.                                                                                                                                                                                                   $\square$

It is in fact also known that $\sqrt{5}$ is the best constant $c$ such that for every irrational number $\alpha$ , there exists infinitely many integers $p,q$ such that $\left|\frac{p}{q}-\alpha\right|< \frac{1}{cq^2}$ . This is because for larger $c$ , the ‘golden ratio’ $\phi= \frac{\sqrt{5}+1}{2}$ ceases to have infinitely many approximations. This is part of the reason why the golden ratio is said to be in some sense ‘the most irrational number’.

The equality case is also quite interesting since one can show that all rational approximations of $\phi$ satisfying Hurwitz’s approximation are those which are ratios of consecutive Fibonacci numbers.

3. Ford Circles

Since any discussion on Farey sequences is incomplete without mentioning Ford circles, we shall point out a few connections between the two.

Ford circles are a set of circles whose centers are at $\left(\frac{p}{q},\frac{1}{2q^2}\right)$ and have radius $\frac{p}{q}$ for every completely reduced fraction $\frac{p}{q}$ between 0 and 1.

Theorem 6 (Ford Circles)

Two Ford circles are either disjoint or tangent to each other. In particular, the Ford circles for two completely reduced fractions are tangent if and only if these fractions are neighbours of some Farey sequence.

Proof. We employ Cartesian coordinates. With the center and radii all known, this is but a simple calculation. We know that two circles intersect if and only if the sum of their radii is less than the distance between their centers.

However,

$\left(\frac{a}{b}-\frac{c}{d}\right)^2 + \left(\frac{1}{2b^2}+\frac{1}{2d^2}\right)^2 - \left(\frac{1}{2b^2}+\frac{1}{2d^2}\right)^2=\left(\frac{a}{b}-\frac{c}{d}\right)^2 - \frac{1}{b^2d^2}$

which is negative if and only if $\left|\frac{a}{b}-\frac{c}{d}\right|<\frac{1}{bd}$ or simply $|ad-bc|<1$ which is a clear contradiction, and in particular tangency holds if and only if $|ad-bc|=1$ which is precisely the Farey neighbours condition.
Four Kissing Circles

January 25, 2026
Today we shall explore a more classical configuration which has been studied in various settings — most notably in terms of inversion. We consider $\omega_1$ , $\omega_2$ , $\omega_3$ and $\omega_4$ (with centers $O_1$ , $O_2$ , $O_3$ and $O_4$ ) to be four circles such that $\omega_i$ and $\omega_{i+1}$ are externally tangent for all $1 \le i \le 4$ where indices are considered $\pmod{4}$ .

We shall refer to the following diagram for notation. Since most labels are not standard, the precise definition of each point is given where it is introduced.

A summary of the key results pertaining to this configuration,
1. Points ,, and denote the tangency points of each pair of circles. An easy angle chase or an inversion about shows that quadrilateral is degenerate or cyclic, which is Problem 24 in Chapter 8 of Evan Chen’s EGMO and has also appeared as 2004 Indonesia MO Problem 4.
  - Moreover, this implies that the length of the tangents from $LM \cap KN$ to $\omega_2$ and $\omega_4$ as well as the length of the tangents from $LK \cap MN$ to $\omega_1$ and $\omega_2$ are equal, which is the statement of 1999 Argentina TST Problem 2.
  - Since the sum of opposite sides of $O_1O_2O_3O_4$ is equal to the sum of the radii of the circles, by Pitot’s theorem it follows that $O_1O_2O_3O_4$ is a tangential quadrilateral.
  - Clearly, the perpendicular bisector of segment $LK$ is the internal $\angle O_4O_1O_2$ bisector and similarly, so it follows that the circumcenter $O$ of $LMNK$ coincides with the incenter of $O_1O_2O_3O_4$ .
  - Congruency arguments show that $LMNK$ is a rectangle if and only if $\omega_1,\omega_3$ and $\omega_2,\omega_4$ are pairs of equiradial circles. In particular, when this happens $O_1O_2O_3O_4$ is a rhombus, and the incircle of this rhombus coincides with $(LMNK)$ . In this case, the antipodes of $L$ , $M$ , $N$ and $K$ in $\omega_1,\omega_2,\omega_3$ and $\omega_4$ (whenever they are defined) all lie on an ellipse with center $O$ .
  - Strengthening this observation, $LMNK$ is a square if and only if all four circles are equiradial, which is asked in 2014 Kukin MO Grade 10 Problem 3.
2. For any point denote by the incenter of the triangle formed by the other three points.
  - By the Incenter/Excenter lemma it follows that quadrilateral $LMI_KI_N$ (and similarly) is concyclic with circumcenter coinciding with the minor $LM$ arc midpoint in $(LMNK)$ .
  - Further, an easy angle chase shows that all angles of quadrilateral $I_MI_NI_KI_L$ are right and hence a rectangle.
3. For any point denote by the orthocenter of the triangle formed by the other three points.
  - It is not hard to see that quadrilateral $LMH_KH_N$ (and similarly) is concyclic, and that quadrilateral $H_MH_NH_KH_L$ is also concyclic.
  - The quadrilaterals $H_MK_KMK$ (and similarly) are all parallelograms, which implies that the segments $H_MM$ , $H_LL$ , $H_NN$ and $H_KK$ concur, bisecting each other. This claim is in fact also true for any set of four concyclic points.
Miquel point of a quadrilateral formed by the H-tangent to (BHC)

January 12, 2026
Today we shall have a look at another orthocentric configuration, that of the Miquel point of the quadrilateral formed by the intersections of the tangent to circle $(BHC)$ at $H$ with the sides of $\triangle ABC$ . Many thanks to Yangqin Yang for contributing several proofs and for saving me from crashing out.

As usual, points follow their standard labels (except for the renaming of the $A-$ Humpty point to $H_M$ ) and a GeoGebra link is embedded to the diagram below for closer inspection.

A summary of the key results pertaining to this configuration,
1. First, an easy angle chase shows that quadrilateral is cyclic. Hence, by Radical center theorem on circles , and it follows that lines , and concur at .
  - Since it is well known that the $A-$ diameter of $(ABC)$ and $H-$ diameter of $(BHC)$ are parallel, it follows that $AA' \perp PQ$ .
2. Reflection across the line implies that is tangent to at and since it is well known that we have that is the pole of with respect to .
  - In particular, this implies that quadrilateral $AQ_aKH_a$ is also harmonic and hence projecting onto line $\overline{BC}$ through $A$ we have that the $A-$ tangent to $(ABC)$ intersects $BC$ at precisely the reflection of $D$ across $Z$ .
3. It is not hard to see that the Miquel point of with respect to must lie on the altitude, so quadrilaterals and are also cyclic.
  - Since $BCPQ$ is cyclic, it is well known that $R$ lies on the rectangular circumhyperbola of $\triangle ABC$ passing through $A'$ . Pascal’s theorem on coconic hexagon $A'RBHAC$ implies that lines $\overline{AH \cap RA' , P}, BH$ and $CA'$ concur, which since the latter two are both perpendicular to side $AC$ implies that $S = AH \cap RA'$ and hence points $R$ , $S$ and $A'$ must be collinear.
  - It is not hard to see that point $K$ must also lie on this line due to the right angles. Further, if $J = (PQD) \cap BC \ne D$ then $AKDJ$ is also cyclic by PoP at $Z$ so it follows that $J$ also lies on this line due to the right angles.
4. Quadrilaterals and are also cyclic which by an easy angle chase shows that the midpoint of segment lies on .
  - Further, we can also show that line $ZH_a$ must be tangent to $(PQH_a)$ at $H_a$ so circles $(ABC)$ and $(PQH_a)$ are tangent, which is the statement of 2023 Thailand TSTST Problem 1.
5. Now, consider the inversion centered at with radius . This inversion swaps the pairs , . and due to the cyclic quadrilaterals noted above.
  - Thus, this inversion swaps line $\overline{PQ}$ with circle $(ABC)$ so $AU=AV = \sqrt{AS \cdot AD}$ which solves the following easy problem on AoPS.
  - Also, this inversion swaps circles $(BHC)$ and $(PQH_a)$ so the intersections of these circles remain fixed under inversion, implying that $AE=AF = \sqrt{AS \cdot AD}$ . Combining this with the previous result it follows that quadrilateral $UVFE$ is cyclic with center $A$ . Also, Radical center now implies that line $EF$ passes through $Z$ .
  - Since $HH_MMD$ is well known to be cyclic, it follows that $HH_aWH_M$ is too by Reim’s theorem. Thus, this inversion swaps points $H_M$ and $W$ . In particular, this implies that $W$ lies on $(PQH_a)$ since it is well known that $H_M$ lies on $(BHC)$ .
  - As we noted before that $AA' \perp PQ$ , it is clear that this inversion also swaps $A'$ and the point $AA' \cap PQ$ . Thus, $\overline{A'WH_a}$ which is the line through $A'$ parallel to $BC$ maps to the circle with diameter $AH$ implying that $Y = A'H_a \cap PQ$ must map to the $A-$ Queue point.
6. Note that and are tangent to . Thus, lies on the polar of with respect to . Furthermore, since we showed that lies on we have implying that also lies on the polar of and thus, is the polar of with respect to .
  - But then $L = AK \cap H_aA'$ lies on the polars of both $T$ and $H$ with respect to $(APQ)$ which by La Hire’s implies that $\overline{TH}$ is the polar of $L$ with respect to this circle.
  - It is not hard to check that $\frac{H_aN}{AH_a} = \frac{DZ}{DX_a}$ so it follows that lines $NL$ and $AY$ are parallel. In particular, this means that $NL \perp HQ_a$ which must imply that $\overline{QH_a}$ is the polar of $L$ with resepct to $(APQ)$ . This implies that $TH$ bisects segment $BC$ , which solves 2023 Kazakhstan Junior MO Grade 9 Problem 6.
7. Let denote the rectangular circumhyperbola of passing through . We noted before that lies on . The parallelogram point also lies on this hyperbola.
  - It is easy to show via lengths that the line through $AQ_a \cap CH$ and $AB \cap Q_aH$ is parallel to $BC$ . Hence, points $YA' \cap BC$ , $AY \cap CH$ and $AB \cap HA'$ are collinear which by the converse of Pascal’s theorem implies that $Y$ must also lie on $\mathcal{H}$ .
  - It is also not hard to see that points $A$ , $BT \cap QQ_a$ and $CT \cap PQ_a$ are collinear implying that the points $T$ , $B$ , $C$ , $P$ , $Q$ and $Q_a$ are coconic.
8. Since by reflection, it is clear that lines and intersect on . Thus, points , and are collinear. By reflection across the line it also follows that points , and are collinear.
  - The inversion we mentioned before shows that $KZH_aH$ is cyclic, on which $J$ must also lie since $ZH_aJH$ is a kite due to symmetry.
  - By PoP at $J$ it then follows that quadrilateral $KHA'A_1$ is cyclic. Further, the above observation implies that $Y$ must also lie on this circle by Reim’s theorem.
  - Also by Reim’s it further follows that $Q_aJMT_a$ is cyclic, which implies that lines $Q_aT_a$ , $BC$ and $YA_1$ concur.