Given a circular arrangement of r0, ns “ t0, 1, . . . , nu, we define a k-chord to be
a (possibly degenerate) chord whose (possibly equal) endpoints add up to k. We say that three
chords of a circle are aligned if one of them separates the other two. Say that m ě 3 chords
are aligned if any three of them are aligned. For instance, in Figure 1, A, B, and C are aligned,
while B, C, and D are not.
ABCDB ACDE0 nu vtn − t
Figure 1 Figure 2
Claim. In a beautiful arrangement, the k–chords are aligned for any integer k.
Proof. We proceed by induction. For n ď 3 the statement is trivial. Now let n ě 4, and proceed
by contradiction. Consider a beautiful arrangement S where the three k–chords A, B, C are not
aligned. If n is not among the endpoints of A, B, and C, then by deleting n from S we obtain
a beautiful arrangement Sztnu of r0, n ´ 1s, where A, B, and C are aligned by the induction
hypothesis. Similarly, if 0 is not among these endpoints, then deleting 0 and decreasing all the
numbers by 1 gives a beautiful arrangement Szt0u where A, B, and C are aligned. Therefore
both 0 and n are among the endpoints of these segments. If x and y are their respective partners,
we have n ě 0 ` x “ k “ n ` y ě n. Thus 0 and n are the endpoints of one of the chords; say it
Let D be the chord formed by the numbers u and v which are adjacent to 0 and n and on the
same side of C as A and B, as shown in Figure 2. Set t “ u`v. If we had t “ n, the n–chords A,
B, and D would not be aligned in the beautiful arrangement Szt0, nu, contradicting the induction
hypothesis. If t ă n, then the t-chord from 0 to t cannot intersect D, so the chord C separates t
and D. The chord E from t to n´t does not intersect C, so t and n´t are on the same side of C.
But then the chords A, B, and E are not aligned in Szt0, nu, a contradiction. Finally, the case
t ą n is equivalent to the case t ă n via the beauty-preserving relabelling x ÞÑ n´x for 0 ď x ď n,
which sends t-chords to p2n ´ tq–chords. This proves the Claim.
Having established the Claim, we prove the desired result by induction. The case n “ 2 is
trivial. Now assume that n ě 3. Let S be a beautiful arrangement of r0, ns and delete n to obtain
34 IMO 2013 Colombia
the beautiful arrangement T of r0, n ´ 1s. The n–chords of T are aligned, and they contain every
point except 0. Say T is of Type 1 if 0 lies between two of these n–chords, and it is of Type 2
otherwise; i.e., if 0 is aligned with these n–chords. We will show that each Type 1 arrangement
of r0, n´ 1s arises from a unique arrangement of r0, ns, and each Type 2 arrangement of r0, n´ 1s arises from exactly two beautiful arrangements of r0, ns.
If T is of Type 1, let 0 lie between chords A and B. Since the chord from 0 to n must be
aligned with A and B in S, n must be on the other arc between A and B. Therefore S can be
recovered uniquely from T. In the other direction, if T is of Type 1 and we insert n as above,
then we claim the resulting arrangement S is beautiful. For 0 ă k ă n, the k–chords of S are also
k–chords of T, so they are aligned. Finally, for n ă k ă 2n, notice that the n–chords of S are
parallel by construction, so there is an antisymmetry axis ℓ such that x is symmetric to n´x with
respect to ℓ for all x. If we had two k–chords which intersect, then their reflections across ℓ would
be two p2n ´ kq-chords which intersect, where 0 ă 2n ´ k ă n, a contradiction.
If T is of Type 2, there are two possible positions for n in S, on either side of 0. As above, we
check that both positions lead to beautiful arrangements of r0, ns.
Hence if we let Mn be the number of beautiful arrangements of r0, ns, and let Ln be the number
of beautiful arrangements of r0, n ´ 1s of Type 2, we have
Mn “ pMn´1 ´ Ln´1q ` 2Ln´1 “ Mn´1 ` Ln´1.
It then remains to show that Ln´1 is the number of pairs px, yq of positive integers with x`y “ n
and gcdpx, yq “ 1. Since n ě 3, this number equals ϕpnq “ #tx : 1 ď x ď n, gcdpx, nq “ 1u.
To prove this, consider a Type 2 beautiful arrangement of r0, n ´ 1s. Label the positions
0, . . . , n ´ 1 pmod nq clockwise around the circle, so that number 0 is in position 0. Let fpiq be
the number in position i; note that f is a permutation of r0, n ´ 1s. Let a be the position such
that fpaq “ n ´ 1.
Since the n–chords are aligned with 0, and every point is in an n–chord, these chords are all
fpiq ` fp´iq “ n for all i.
Similarly, since the pn´1q–chords are aligned and every point is in an pn´1q–chord, these chords
are also parallel and
fpiq ` fpa ´ iq “ n ´ 1 for all i.
Therefore fpa ´ iq “ fp´iq ´ 1 for all i; and since fp0q “ 0, we get
fp´akq “ k for all k. (1)
Recall that this is an equality modulo n. Since f is a permutation, we must have pa, nq “ 1. Hence
Ln´1 ď ϕpnq.
To prove equality, it remains to observe that the labeling (1) is beautiful. To see this, consider
four numbers w, x, y, z on the circle with w ` y “ x ` z. Their positions around the circle satisfy
p´awq ` p´ayq “ p´axq ` p´azq, which means that the chord from w to y and the chord from
x to z are parallel. Thus (1) is beautiful, and by construction it has Type 2. The desired result