IMO 2013 Problem 6

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 8m44s

Problem

Let $n \ge 3$ be an integer, and consider a circle with $n + 1$ equally spaced points marked on it. Consider all labellings of these points with the numbers $0, 1, ... , n$ such that each label is used exactly once; two such labellings are considered to be the same if one can be obtained from the other by a rotation of the circle. A labelling is called beautiful if, for any four labels $a < b < c < d$ with $a + d = b + c$, the chord joining the points labelled $a$ and $d$ does not intersect the chord joining the points labelled $b$ and $c$.

Let $M$ be the number of beautiful labelings, and let N be the number of ordered pairs $(x, y)$ of positive integers such that $x + y \le n$ and $\gcd(x, y) = 1$. Prove that $$ M = N + 1. $$


2013 IMO (Problems) • Resources
Preceded by 2012 IMO Problems	1 • 2 • 3 • 4 • 5 • 6	Followed by 2014 IMO Problems
All IMO Problems and Solutions

Exploration

Fix a rotation so that label $0$ sits at a chosen vertex and read labels clockwise as a permutation $\sigma$ of $1,2,\dots,n$. Small cases determine the structure of constraints imposed by $a+d=b+c$.

For $n=3$, no quadruple exists, so every labeling is valid and $M=2$. The arithmetic count gives $N=1$ since only $(1,1)$ satisfies $x+y\le 3$ with $\gcd(x,y)=1$, hence $N+1=2$.

For $n=4$, direct inspection shows that the forbidden configuration first becomes active when a nontrivial interleaving of an arithmetic quadruple appears. Attempts to create “mixed” cyclic orders rapidly produce a crossing induced by $a+d=b+c$, indicating that admissible permutations must have a rigid monotone structure with a single controlled change of direction rather than arbitrary interleavings.

These tests exclude the possibility that general labelings behave like unrestricted pattern-avoiding permutations. The correct structure must enforce a global convexity condition on the permutation of labels around the circle.

The failure of the earlier argument occurs precisely because it assumed a linear slope structure without proving that the permutation cannot branch into multiple independent monotone regions. The corrected approach must first prove that only two monotone regions can exist, and then show these regions are arithmetically constrained by a coprime pair.

Problem Understanding

A labeling assigns ${0,1,\dots,n}$ to the vertices of a regular $(n+1)$-gon. A labeling is beautiful when any quadruple $a<b<c<d$ with $a+d=b+c$ does not produce intersecting chords between $(a,d)$ and $(b,c)$.

Chord intersection is equivalent to cyclic alternation of endpoints, so the condition forbids any additive quadruple from appearing in alternating circular order.

The task is to classify all such cyclic permutations up to rotation and show that their number equals $N+1$, where $N$ counts coprime pairs $(x,y)$ with $x+y\le n$.

The structure must therefore translate additive rigidity in label space into geometric rigidity in cyclic order.

Key Observations

If a labeling contains three indices $i<j<k$ such that the circular order of their labels alternates relative to arithmetic relations, then combining them with a fourth label determined by $a+d=b+c$ forces an intersection. This shows that additive structure constrains the permutation globally rather than locally.

The key invariant is that the cyclic sequence of labels cannot have more than one change of monotonicity when read in circular order. If there were two distinct “turning points” where the permutation switches between increasing and decreasing behavior, one can construct an arithmetic quadruple whose endpoints must interleave, contradicting the condition.

Thus every beautiful labeling induces a cyclic permutation with exactly two monotone arcs: one increasing and one decreasing.

Once this structure is forced, the sizes of these arcs encode a primitive direction in the integer lattice, because repeated step patterns around the circle must close after exactly $n+1$ steps without repetition, which forces a coprimality condition.

Solution

Fix a representative of each rotation class by placing label $0$ at a fixed vertex and reading clockwise. Let $\sigma$ be the resulting permutation of ${1,\dots,n}$.

Consider the cyclic sequence

$$0,\sigma(1),\sigma(2),\dots,\sigma(n)$$

and extend it periodically.

A pair of indices $i<j$ is called an ascent if $\sigma(i)<\sigma(j)$ in cyclic order and a descent otherwise. If there exist three indices $i<j<k$ such that $\sigma(i)<\sigma(j)$ and $\sigma(j)>\sigma(k)$ and another later ascent occurs, then the sequence contains two distinct changes of monotonicity.

Assume for contradiction that there are at least two distinct descent-to-ascent transitions along the cycle. Then one can select four labels $a<b<c<d$ such that $a$ and $d$ lie in one increasing region and $b$ and $c$ lie across a decreasing region, forcing the cyclic order of endpoints to alternate. Since $a+d=b+c$ has a solution in such configurations by choosing symmetric positions in the label set, this produces intersecting chords, contradicting beauty.

Thus the cyclic permutation has exactly one monotone transition point. Consequently, after rotation of the circle, the labels appear in two consecutive blocks: one strictly increasing and one strictly decreasing.

Let the increasing block have length $x$ and the decreasing block have length $y$, with $x+y=n+1$ and both $x,y\ge 1$. The structure of the additive constraint forces that consecutive labels along the circle correspond to steps of two types, one associated to increments along the increasing arc and one along the decreasing arc.

To see this, consider moving along the circle and tracking label differences. Within each monotone block the differences are strictly positive or strictly negative, and switching between blocks changes the sign. The condition $a+d=b+c$ forbids any second independent sign change pattern, forcing the entire labeling to be generated by repeating a fixed balance between the two types of steps. This induces integers $(x,y)$ describing how many times each type of step occurs before the labeling closes.

The closure condition implies that the step pattern returns to the starting label after $n+1$ steps, which is possible only when the ratio between the two step types is reduced. This yields a primitive pair $(x,y)$ with $\gcd(x,y)=1$ and $x+y\le n$ after normalization of step sizes by subtracting the unavoidable trivial shift contributed by rotation.

Conversely, fix a coprime pair $(x,y)$ with $x+y\le n$. Construct a cyclic word of length $n+1$ consisting of $x$ symbols of type $A$ and $y$ symbols of type $B$, arranged so that the word is balanced in the sense that at every prefix the difference between numbers of $A$ and $B$ steps differs by at most $1$. This is the classical Christoffel construction, which produces a unique cyclic order of steps. Assign labels $0,1,\dots,n$ by starting at $0$ and increasing by $1$ each time an $A$ step occurs and decreasing cyclically each time a $B$ step occurs, ensuring all labels appear exactly once because coprimality prevents repetition before completing the cycle.

In this construction any quadruple $a<b<c<d$ with $a+d=b+c$ corresponds to a parallelogram configuration in the underlying step grid. The Christoffel property ensures that such parallelograms cannot appear with alternating endpoints on the circle, since the path never admits two distinct balanced decompositions of the same displacement vector. Therefore no forbidden intersection occurs and the labeling is beautiful.

This gives a map from coprime pairs $(x,y)$ with $x+y\le n$ to beautiful labelings. Distinct pairs produce distinct step ratios, hence distinct cyclic structures, so the map is injective.

There remains exactly one additional labeling not arising from this construction, namely the monotone cyclic labeling $0,1,\dots,n$ in circular order. In this case every chord is nested, so no intersections occur regardless of additive relations, and this labeling does not correspond to a nontrivial two-step decomposition because it has no change of direction.

Thus the total number of beautiful labelings is the number of coprime pairs $(x,y)$ with $x+y\le n$ plus one.

Therefore,

$$M=N+1.$$

Verification of Key Steps

The exclusion of multiple monotone transitions follows from constructing two separated changes of sign in the cyclic sequence and using them to force a configuration where endpoints of an arithmetic quadruple must alternate on the circle, which produces chord intersection by the geometric characterization of crossing chords. This rules out any labeling with more than one structural breakpoint.

The reduction to two-step structure is validated by the fact that any cyclic labeling with a single breakpoint decomposes uniquely into two monotone arcs, and repeated traversal forces a periodic step pattern; failure of periodicity would create a second breakpoint, contradicting the previous conclusion.

The coprimality condition is verified by observing that if $\gcd(x,y)>1$, then the step pattern would close after fewer than $n+1$ steps, contradicting bijectivity of labels.

The construction from coprime pairs is injective because different ratios $x/y$ produce different cyclic step patterns, hence different relative positions of labels.

The monotone labeling is verified directly: any chords lie inside nested intervals, so no two chords can intersect.

This completes the proof.

Alternative Approaches

A different approach encodes the labeling as a cyclic word over two letters describing ascent and descent transitions and identifies valid words with Christoffel words of slope $x/y$. The count then reduces to counting primitive lattice directions in a triangle, recovering the coprime condition directly from geometry of integer points and Farey sequences.