IMO 2013 · Problem 6

Let \(n \geq 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,\ldots,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 labellings, and let \(N\) be the number of ordered pairs \((x,y)\) of positive integers such that \(x+y\leq n\) and \(\gcd(x,y)=1\). Prove that \[ M=N+1. \]

Official text of the problem. Official problem paper (PDF)

Solution

Two chords with four distinct endpoints intersect if and only if their endpoints alternate around the circle. Thus beauty depends only on the circular order of the labels. We may work with circular orders, transferring them to equally spaced points whenever necessary.

For \(q\geq2\), let \[ \varphi(q)=\#\{r:1\leq r<q,\ \gcd(r,q)=1\}. \] Since \(\gcd(x,y)=\gcd(x,x+y)\), we have \[ N=\sum_{q=2}^{n}\varphi(q). \tag{1} \]

We first prove an upper bound for \(M\).

Say that a circular order of \(0,1,\ldots,m\) has property \(P\) if the map \[ i\longmapsto i+1,\qquad 0\leq i<m, \] preserves counterclockwise cyclic order: a counterclockwise listing of its domain is carried to a counterclockwise listing of its image.

Every beautiful labelling has property \(P\). To prove this, write \(P_i\) for the point labelled \(i\), and consider the counterclockwise arcs \[ I_i=P_iP_{i+1},\qquad 0\leq i<n. \] No one of these arcs can properly contain another. Indeed, arcs with consecutive indices cannot contain one another, because one ends at their common endpoint and the other begins there. If \(i+1<j\) and either \(I_i\) or \(I_j\) contains the other, the endpoints of the chords \[ P_iP_{j+1}\quad\text{and}\quad P_{i+1}P_j \] alternate. These chords would intersect, contradicting beauty because \[ i+(j+1)=(i+1)+j. \]

For completeness, noncontainment implies that the starting points and ending points of these arcs have the same cyclic order. Measure angles in turns and list the starting points as \[ s_1<s_2<\cdots<s_n<s_1+1. \] Let \(t_k\in(s_k,s_k+1)\) be the lifted coordinate of the corresponding ending point. If \(t_k>t_{k+1}\), then \[ s_k<s_{k+1}<t_{k+1}<t_k, \] so one arc contains the other. Similarly, \(t_n>t_1+1\) would give containment across the chosen cut. Ending points are distinct, so \[ t_1<t_2<\cdots<t_n<t_1+1. \] This proves property \(P\).

Let \(A_m\) be the number of circular orders of \(0,\ldots,m\), up to rotation, having property \(P\). We shall show that \[ A_m=A_{m-1}+\varphi(m)\qquad(m\geq3). \tag{2} \]

Deleting \(m\) from an order counted by \(A_m\) leaves an order counted by \(A_{m-1}\). Conversely, fix an order of \(0,\ldots,m-1\) having property \(P\). Its map \[ i\longmapsto i+1,\qquad 0\leq i\leq m-2, \] preserves cyclic order.

Among the points labelled \(0,\ldots,m-2\), let \(u\) and \(v\) be the immediate predecessor and successor of the point labelled \(m-1\). To extend property \(P\), the new point labelled \(m\) must lie in the counterclockwise gap from \(u+1\) to \(v+1\) among the points labelled \(1,\ldots,m-1\). This condition is also sufficient.

That gap contains either no other old point or just the point labelled \(0\). Consequently, there is exactly one possible insertion of \(m\), except when the gap contains \(0\), in which case there are exactly two.

The exceptional case occurs precisely when the permutation \[ 0\mapsto1\mapsto2\mapsto\cdots\mapsto m-1\mapsto0 \] preserves the cyclic order of all \(m\) old points. Any permutation preserving the cyclic order of all points is a rotation of their positions. If this rotation advances \(r\) positions, it is a single cycle exactly when \(\gcd(r,m)=1\).

There are exactly \(\varphi(m)\) such orders: after fixing label \(0\) at position \(0\), each permitted \(r\) uniquely places label \(i\) at position \(ir\pmod m\). Each of these orders has property \(P\), since the displayed permutation preserves cyclic order. This proves (2).

Both circular orders of \(0,1,2\) have property \(P\), so \(A_2=2\). Hence \[ A_n=2+\sum_{q=3}^{n}\varphi(q) =1+\sum_{q=2}^{n}\varphi(q) =N+1. \] Since every beautiful order has property \(P\), \[ M\leq N+1. \tag{3} \]

We now construct at least \(N+1\) distinct beautiful orders.

Let \[ \mathcal F_n= \{0,1\}\cup \left\{\frac pq:1\leq p<q\leq n,\ \gcd(p,q)=1\right\}. \] By (1), this set has \(N+2\) elements, so its consecutive elements determine \(N+1\) open intervals. Choose a real number \(\alpha\) in each interval.

For such an \(\alpha\), place the labels \(0,\ldots,n\) at the complex points \[ z_k=e^{2\pi i k\alpha}. \] These points are distinct: equality \(z_r=z_s\), with \(0\leq r<s\leq n\), would make \(\alpha\) a rational number whose reduced denominator is at most \(s-r\leq n\), contrary to its choice.

This circular order is beautiful. Indeed, \[ z_s-z_r = 2i\,e^{\pi i(r+s)\alpha}\sin\!\bigl(\pi(s-r)\alpha\bigr). \] Thus, if \(a+d=b+c\), the chords \(z_az_d\) and \(z_bz_c\) are parallel. Their supporting lines are distinct, since a line cannot contain four distinct points of a circle. Therefore the chords do not intersect. Transferring the same circular order to equally spaced points preserves this property.

It remains to show that choices from different intervals give different circular orders.

Cut the circle at label \(0\). The linear order of the remaining labels is the order of the fractional parts \[ \{\alpha\},\{2\alpha\},\ldots,\{n\alpha\}. \] For \(1\leq j\leq n\), put \[ \varepsilon_j(\alpha)= \begin{cases} 1,&\{j\alpha\}<\{(j-1)\alpha\},\\ 0,&\{j\alpha\}>\{(j-1)\alpha\}. \end{cases} \] These values are determined by the circular order. Because \(0<\alpha<1\), each step adds \(\alpha\), crossing an integer precisely when the fractional part decreases. Hence \[ \lfloor q\alpha\rfloor=\sum_{j=1}^{q}\varepsilon_j(\alpha) \qquad(1\leq q\leq n). \tag{4} \]

Suppose \(\alpha<\beta\) were chosen from different intervals and gave the same circular order. Some fraction \(p/q\in\mathcal F_n\), with \(q\leq n\), lies strictly between them. Therefore \[ \lfloor q\alpha\rfloor\leq p-1 \quad\text{and}\quad \lfloor q\beta\rfloor\geq p. \] But their identical circular orders would make all the values in (4) equal, a contradiction.

We have therefore constructed \(N+1\) distinct beautiful labellings, giving \[ M\geq N+1. \] Together with (3), this proves \[ \boxed{M=N+1}. \]

The solution was checked against the official IMO shortlist solutions.

IMO 2013 · Aufgabe 6

Es sei \(n\ge 3\) eine ganze Zahl. Man betrachte einen Kreis, auf dem \(n+1\) Punkte in jeweils gleichem Abstand markiert sind. Man betrachte alle Beschriftungen dieser Punkte mit den Zahlen \(0,1,\ldots,n\), wobei jede Zahl genau einmal vorkommt. Zwei solche Beschriftungen werden als gleich angesehen, wenn man die eine durch Drehung des Kreises aus der anderen erhalten kann. Eine Beschriftung heißt schön, wenn für je vier Zahlen \(a<b<c<d\) mit \(a+d=b+c\) die Sehne zwischen \(a\) und \(d\) nicht die Sehne zwischen \(b\) und \(c\) schneidet. Es bezeichne \(M\) die Anzahl der schönen Beschriftungen und \(N\) die Anzahl der geordneten Paare \((x,y)\) von positiven ganzen Zahlen mit \(x+y\le n\) und \(\operatorname{ggT}(x,y)=1\). Man beweise \[ M=N+1. \]

Offizieller deutscher Aufgabentext. Offizielles Aufgabenblatt (PDF)

Lösung

Zwei Sehnen mit vier verschiedenen Endpunkten schneiden sich genau dann, wenn ihre Endpunkte auf dem Kreis abwechselnd auftreten. Somit hängt die Eigenschaft, schön zu sein, nur von der zyklischen Reihenfolge der Beschriftungen ab. Wir können mit zyklischen Anordnungen arbeiten und diese bei Bedarf auf Punkte mit gleichen Abständen übertragen.

Für \(q\geq2\) sei \[ \varphi(q)=\#\{r:1\leq r<q,\ \operatorname{ggT}(r,q)=1\}. \] Wegen \(\operatorname{ggT}(x,y)=\operatorname{ggT}(x,x+y)\) gilt \[ N=\sum_{q=2}^{n}\varphi(q). \tag{1} \]

Wir beweisen zunächst eine obere Schranke für \(M\).

Wir sagen, eine zyklische Anordnung von \(0,1,\ldots,m\) habe die Eigenschaft \(P\), wenn die Abbildung \[ i\longmapsto i+1,\qquad 0\leq i<m, \] die zyklische Reihenfolge gegen den Uhrzeigersinn erhält: Eine Aufzählung ihres Definitionsbereichs gegen den Uhrzeigersinn wird auf eine Aufzählung ihrer Bildmenge gegen den Uhrzeigersinn abgebildet.

Jede schöne Beschriftung hat die Eigenschaft \(P\). Zum Beweis bezeichnen wir den mit \(i\) beschrifteten Punkt mit \(P_i\) und betrachten die gegen den Uhrzeigersinn verlaufenden Kreisbögen \[ I_i=P_iP_{i+1},\qquad 0\leq i<n. \] Keiner dieser Bögen kann einen anderen echt enthalten. Tatsächlich können Bögen mit aufeinanderfolgenden Indizes einander nicht enthalten, da einer an ihrem gemeinsamen Endpunkt endet und der andere dort beginnt. Ist \(i+1<j\) und enthält entweder \(I_i\) den Bogen \(I_j\) oder umgekehrt, so treten die Endpunkte der Sehnen \[ P_iP_{j+1}\quad\text{und}\quad P_{i+1}P_j \] abwechselnd auf. Diese Sehnen würden sich schneiden, im Widerspruch zur Schönheit der Beschriftung, denn \[ i+(j+1)=(i+1)+j. \]

Der Vollständigkeit halber zeigen wir, dass aus dem gegenseitigen Nichtenthalten folgt, dass die Anfangspunkte und Endpunkte dieser Bögen dieselbe zyklische Reihenfolge haben. Wir messen Winkel in vollen Umdrehungen und ordnen die Anfangspunkte als \[ s_1<s_2<\cdots<s_n<s_1+1. \] Sei \(t_k\in(s_k,s_k+1)\) die auf dieses Intervall angehobene Koordinate des zugehörigen Endpunkts. Wäre \(t_k>t_{k+1}\), so wäre \[ s_k<s_{k+1}<t_{k+1}<t_k, \] so dass ein Bogen den anderen enthielte. Ebenso würde \(t_n>t_1+1\) zu einem Enthaltensein über den gewählten Schnitt hinweg führen. Da die Endpunkte verschieden sind, gilt also \[ t_1<t_2<\cdots<t_n<t_1+1. \] Damit ist die Eigenschaft \(P\) bewiesen.

Sei \(A_m\) die Anzahl der zyklischen Anordnungen von \(0,\ldots,m\) mit der Eigenschaft \(P\), wobei Anordnungen bis auf Drehung gezählt werden. Wir werden zeigen, dass \[ A_m=A_{m-1}+\varphi(m)\qquad(m\geq3). \tag{2} \]

Entfernt man \(m\) aus einer von \(A_m\) gezählten Anordnung, so bleibt eine von \(A_{m-1}\) gezählte Anordnung übrig. Umgekehrt wählen wir eine Anordnung von \(0,\ldots,m-1\) mit der Eigenschaft \(P\) fest. Ihre Abbildung \[ i\longmapsto i+1,\qquad 0\leq i\leq m-2, \] erhält die zyklische Reihenfolge.

Unter den mit \(0,\ldots,m-2\) beschrifteten Punkten seien \(u\) und \(v\) der unmittelbare Vorgänger beziehungsweise Nachfolger des mit \(m-1\) beschrifteten Punktes. Damit die Eigenschaft \(P\) erhalten bleibt, muss der neue, mit \(m\) beschriftete Punkt in der gegen den Uhrzeigersinn verlaufenden Lücke von \(u+1\) nach \(v+1\) zwischen den mit \(1,\ldots,m-1\) beschrifteten Punkten liegen. Diese Bedingung ist auch hinreichend.

Diese Lücke enthält entweder keinen weiteren alten Punkt oder nur den mit \(0\) beschrifteten Punkt. Folglich gibt es genau eine Möglichkeit, \(m\) einzufügen, außer wenn die Lücke \(0\) enthält; in diesem Fall gibt es genau zwei.

Der Ausnahmefall tritt genau dann ein, wenn die Permutation \[ 0\mapsto1\mapsto2\mapsto\cdots\mapsto m-1\mapsto0 \] die zyklische Reihenfolge aller \(m\) alten Punkte erhält. Jede Permutation, welche die zyklische Reihenfolge aller Punkte erhält, ist eine Drehung ihrer Positionen. Verschiebt diese Drehung um \(r\) Positionen, so besteht sie genau dann aus einem einzigen Zyklus, wenn \(\operatorname{ggT}(r,m)=1\).

Es gibt genau \(\varphi(m)\) solche Anordnungen: Nachdem die Beschriftung \(0\) an Position \(0\) festgelegt ist, platziert jedes zulässige \(r\) die Beschriftung \(i\) eindeutig an Position \(ir\pmod m\). Jede dieser Anordnungen hat die Eigenschaft \(P\), da die angegebene Permutation die zyklische Reihenfolge erhält. Damit ist (2) bewiesen.

Beide zyklischen Anordnungen von \(0,1,2\) haben die Eigenschaft \(P\), also gilt \(A_2=2\). Somit ist \[ A_n=2+\sum_{q=3}^{n}\varphi(q) =1+\sum_{q=2}^{n}\varphi(q) =N+1. \] Da jede schöne Anordnung die Eigenschaft \(P\) hat, gilt \[ M\leq N+1. \tag{3} \]

Wir konstruieren nun mindestens \(N+1\) verschiedene schöne Anordnungen.

Sei \[ \mathcal F_n= \{0,1\}\cup \left\{\frac pq:1\leq p<q\leq n,\ \operatorname{ggT}(p,q)=1\right\}. \] Nach (1) hat diese Menge \(N+2\) Elemente, so dass ihre aufeinanderfolgenden Elemente \(N+1\) offene Intervalle bestimmen. Wir wählen in jedem Intervall eine reelle Zahl \(\alpha\).

Für ein solches \(\alpha\) platzieren wir die Beschriftungen \(0,\ldots,n\) an den komplexen Punkten \[ z_k=e^{2\pi i k\alpha}. \] Diese Punkte sind verschieden: Aus einer Gleichheit \(z_r=z_s\) mit \(0\leq r<s\leq n\) würde folgen, dass \(\alpha\) eine rationale Zahl ist, deren Nenner in vollständig gekürzter Darstellung höchstens \(s-r\leq n\) ist, im Widerspruch zu ihrer Wahl.

Diese zyklische Anordnung ist schön. Tatsächlich gilt \[ z_s-z_r = 2i\,e^{\pi i(r+s)\alpha}\sin\!\bigl(\pi(s-r)\alpha\bigr). \] Gilt also \(a+d=b+c\), so sind die Sehnen \(z_az_d\) und \(z_bz_c\) parallel. Ihre Trägergeraden sind verschieden, da eine Gerade keine vier verschiedenen Punkte eines Kreises enthalten kann. Daher schneiden sich die Sehnen nicht. Bei der Übertragung derselben zyklischen Reihenfolge auf Punkte mit gleichen Abständen bleibt diese Eigenschaft erhalten.

Es bleibt zu zeigen, dass Wahlen aus verschiedenen Intervallen verschiedene zyklische Anordnungen ergeben.

Wir schneiden den Kreis an der Beschriftung \(0\) auf. Die lineare Reihenfolge der übrigen Beschriftungen ist die Reihenfolge der gebrochenen Anteile \[ \{\alpha\},\{2\alpha\},\ldots,\{n\alpha\}. \] Für \(1\leq j\leq n\) setzen wir \[ \varepsilon_j(\alpha)= \begin{cases} 1,&\{j\alpha\}<\{(j-1)\alpha\},\\ 0,&\{j\alpha\}>\{(j-1)\alpha\}. \end{cases} \] Diese Werte sind durch die zyklische Anordnung bestimmt. Wegen \(0<\alpha<1\) wird bei jedem Schritt \(\alpha\) addiert, wobei genau dann eine ganze Zahl überschritten wird, wenn der gebrochene Anteil kleiner wird. Daher gilt \[ \lfloor q\alpha\rfloor=\sum_{j=1}^{q}\varepsilon_j(\alpha) \qquad(1\leq q\leq n). \tag{4} \]

Angenommen, \(\alpha<\beta\) wären aus verschiedenen Intervallen gewählt und ergäben dieselbe zyklische Anordnung. Ein Bruch \(p/q\in\mathcal F_n\) mit \(q\leq n\) liegt strikt zwischen ihnen. Daher gilt \[ \lfloor q\alpha\rfloor\leq p-1 \quad\text{und}\quad \lfloor q\beta\rfloor\geq p. \] Ihre identischen zyklischen Anordnungen würden jedoch bedeuten, dass alle Werte in (4) übereinstimmen, ein Widerspruch.

Wir haben somit \(N+1\) verschiedene schöne Beschriftungen konstruiert, woraus \[ M\geq N+1 \] folgt. Zusammen mit (3) beweist dies \[ \boxed{M=N+1}. \]

Die Lösung wurde mit den offiziellen Lösungen der IMO-Shortlist abgeglichen.

IMO 2013 · Soru 6

\(n\ge 3\) bir tam sayı olmak üzere, bir çember üzerinde çemberi eşit yaylara bölen \(n+1\) nokta işaretlenmiştir. \(0,1,\ldots,n\) sayılarının her biri tam olarak bir kez kullanılarak işaretli noktalara yazılmasına numaralandırma diyelim. Biri diğerinden çemberin döndürülmesi ile elde edilen iki numaralandırma aynı sayılmaktadır. Bir numaralandırmada, \(a+d=b+c\) koşulunu sağlayan her \(a<b<c<d\) için uçlarında \(a\) ve \(d\) yazan kiriş ile uçlarında \(b\) ve \(c\) yazan kiriş kesişmiyorsa, bu numaralandırmaya güzel diyelim.

Güzel numaralandırmaların sayısı \(M\), \(x+y\le n\) ve \(\operatorname{ebob}(x,y)=1\) koşullarını sağlayan \((x,y)\) pozitif tam sayı sıralı ikililerinin sayısı \(N\) olsun. \[ M=N+1 \] olduğunu gösteriniz.

Sorunun resmi Türkçe metni. Resmi soru kâğıdı (PDF)

Çözüm

Dört farklı uç noktaya sahip iki kiriş, ancak ve ancak uç noktaları çember üzerinde dönüşümlü olarak sıralanıyorsa kesişir. Dolayısıyla güzel olma özelliği yalnızca etiketlerin çembersel sırasına bağlıdır. Çembersel sıralamalarla çalışabilir ve gerektiğinde bunları eşit aralıklı noktalara aktarabiliriz.

\(q\geq2\) için \[ \varphi(q)=\#\{r:1\leq r<q,\ \operatorname{ebob}(r,q)=1\} \] olsun. \(\operatorname{ebob}(x,y)=\operatorname{ebob}(x,x+y)\) olduğundan, \[ N=\sum_{q=2}^{n}\varphi(q). \tag{1} \]

Önce \(M\) için bir üst sınır kanıtlayacağız.

\(0,1,\ldots,m\)'nin bir çembersel sıralamasında \[ i\longmapsto i+1,\qquad 0\leq i<m \] dönüşümü saat yönünün tersindeki çevrimsel sırayı koruyorsa, bu sıralamanın \(P\) özelliğine sahip olduğunu söyleyelim: tanım kümesinin saat yönünün tersindeki bir sıralanışı, görüntü kümesinin saat yönünün tersindeki bir sıralanışına götürülür.

Her güzel numaralandırma \(P\) özelliğine sahiptir. Bunu kanıtlamak için, \(i\) etiketli noktayı \(P_i\) ile gösterelim ve saat yönünün tersindeki \[ I_i=P_iP_{i+1},\qquad 0\leq i<n \] yaylarını ele alalım. Bu yaylardan hiçbiri bir diğerini öz altkümesi olarak içeremez. Gerçekten de, ardışık indisli yaylar birbirini içeremez; çünkü biri ortak uç noktalarında biterken diğeri orada başlar. \(i+1<j\) ise ve \(I_i\) veya \(I_j\)'den biri diğerini içeriyorsa, \[ P_iP_{j+1}\quad\text{ve}\quad P_{i+1}P_j \] kirişlerinin uç noktaları dönüşümlü olarak sıralanır. Bu kirişler kesişirdi; bu ise \[ i+(j+1)=(i+1)+j \] olduğundan güzel olma özelliğiyle çelişir.

Eksiksiz olması için, birbirini içermeme koşulunun bu yayların başlangıç noktaları ile bitiş noktalarının aynı çevrimsel sırada olmasını gerektirdiğini de gösterelim. Açıları tam tur biriminde ölçelim ve başlangıç noktalarını \[ s_1<s_2<\cdots<s_n<s_1+1 \] şeklinde sıralayalım. Karşılık gelen bitiş noktasının gerçek doğruya kaldırılmış koordinatı \(t_k\in(s_k,s_k+1)\) olsun. \(t_k>t_{k+1}\) ise \[ s_k<s_{k+1}<t_{k+1}<t_k \] olur; dolayısıyla bir yay diğerini içerir. Benzer şekilde, \(t_n>t_1+1\) olması, seçilen kesim noktasının iki tarafına uzanan bir içerme ilişkisi verirdi. Bitiş noktaları birbirinden farklı olduğundan, \[ t_1<t_2<\cdots<t_n<t_1+1. \] Bu, \(P\) özelliğini kanıtlar.

\(0,\ldots,m\)'nin, dönmeyle elde edilenler aynı sayılmak üzere, \(P\) özelliğine sahip çembersel sıralamalarının sayısı \(A_m\) olsun. \[ A_m=A_{m-1}+\varphi(m)\qquad(m\geq3) \tag{2} \] olduğunu göstereceğiz.

\(A_m\) ile sayılan bir sıralamadan \(m\)'yi silmek, \(A_{m-1}\) ile sayılan bir sıralama bırakır. Tersine, \(0,\ldots,m-1\)'in \(P\) özelliğine sahip bir sıralamasını sabitleyelim. Bu sıralamanın \[ i\longmapsto i+1,\qquad 0\leq i\leq m-2 \] dönüşümü çevrimsel sırayı korur.

\(0,\ldots,m-2\) etiketli noktalar arasında, \(m-1\) etiketli noktanın hemen önceki ve hemen sonraki komşuları \(u\) ve \(v\) olsun. \(P\) özelliğinin devam etmesi için, yeni \(m\) etiketli nokta, \(1,\ldots,m-1\) etiketli noktalar arasında \(u+1\)'den \(v+1\)'e saat yönünün tersinde gidilen aralıkta bulunmalıdır. Bu koşul aynı zamanda yeterlidir.

Bu aralık ya başka hiçbir eski nokta içermez ya da yalnızca \(0\) etiketli noktayı içerir. Dolayısıyla \(m\)'nin eklenmesi için tam olarak bir olasılık vardır; aralığın \(0\)'ı içerdiği durumda ise tam olarak iki olasılık vardır.

İstisnai durum tam olarak \[ 0\mapsto1\mapsto2\mapsto\cdots\mapsto m-1\mapsto0 \] permütasyonunun \(m\) eski noktanın tümünün çevrimsel sırasını koruduğu zaman ortaya çıkar. Tüm noktaların çevrimsel sırasını koruyan her permütasyon, noktaların konumlarının bir dönmesidir. Bu dönme \(r\) konum ilerletiyorsa, ancak ve ancak \(\operatorname{ebob}(r,m)=1\) olduğunda tek bir çevrimdir.

Bu tür sıralamaların sayısı tam olarak \(\varphi(m)\)'dir: \(0\) etiketini \(0\) konumunda sabitledikten sonra, izin verilen her \(r\) değeri, \(i\) etiketini tek bir şekilde \(ir\pmod m\) konumuna yerleştirir. Gösterilen permütasyon çevrimsel sırayı koruduğundan, bu sıralamaların her biri \(P\) özelliğine sahiptir. Böylece (2) kanıtlanır.

\(0,1,2\)'nin her iki çembersel sıralaması da \(P\) özelliğine sahiptir; dolayısıyla \(A_2=2\). Böylece \[ A_n=2+\sum_{q=3}^{n}\varphi(q) =1+\sum_{q=2}^{n}\varphi(q) =N+1. \] Her güzel sıralama \(P\) özelliğine sahip olduğundan, \[ M\leq N+1. \tag{3} \]

Şimdi en az \(N+1\) farklı güzel sıralama inşa edeceğiz.

\[ \mathcal F_n= \{0,1\}\cup \left\{\frac pq:1\leq p<q\leq n,\ \operatorname{ebob}(p,q)=1\right\} \] olsun. (1)'e göre bu kümenin \(N+2\) elemanı vardır; dolayısıyla ardışık elemanları \(N+1\) açık aralık belirler. Her aralıktan bir \(\alpha\) gerçek sayısı seçelim.

Böyle bir \(\alpha\) için, \(0,\ldots,n\) etiketlerini \[ z_k=e^{2\pi i k\alpha} \] karmaşık noktalarına yerleştirelim. Bu noktalar birbirinden farklıdır: \(0\leq r<s\leq n\) olmak üzere \(z_r=z_s\) eşitliği, \(\alpha\)'nın sadeleştirilmiş paydası en fazla \(s-r\leq n\) olan bir rasyonel sayı olmasını gerektirirdi; bu ise seçimine aykırıdır.

Bu çembersel sıralama güzeldir. Gerçekten de, \[ z_s-z_r = 2i\,e^{\pi i(r+s)\alpha}\sin\!\bigl(\pi(s-r)\alpha\bigr). \] Dolayısıyla \(a+d=b+c\) ise \(z_az_d\) ve \(z_bz_c\) kirişleri paraleldir. Bir doğru bir çemberin dört farklı noktasını içeremeyeceğinden, bu kirişleri taşıyan doğrular farklıdır. Bu nedenle kirişler kesişmez. Aynı çembersel sırayı eşit aralıklı noktalara aktarmak bu özelliği korur.

Geriye, farklı aralıklardan yapılan seçimlerin farklı çembersel sıralamalar verdiğini göstermek kalır.

Çemberi \(0\) etiketli noktada keselim. Kalan etiketlerin doğrusal sırası, \[ \{\alpha\},\{2\alpha\},\ldots,\{n\alpha\} \] kesir kısımlarının sırasıdır. \(1\leq j\leq n\) için \[ \varepsilon_j(\alpha)= \begin{cases} 1,&\{j\alpha\}<\{(j-1)\alpha\},\\ 0,&\{j\alpha\}>\{(j-1)\alpha\} \end{cases} \] olarak tanımlayalım. Bu değerler çembersel sıra tarafından belirlenir. \(0<\alpha<1\) olduğundan, her adımda \(\alpha\) eklenir ve tam olarak kesir kısmı azaldığında bir tam sayı aşılır. Dolayısıyla \[ \lfloor q\alpha\rfloor=\sum_{j=1}^{q}\varepsilon_j(\alpha) \qquad(1\leq q\leq n). \tag{4} \]

Farklı aralıklardan seçilen \(\alpha<\beta\)'nın aynı çembersel sıralamayı verdiğini varsayalım. \(q\leq n\) olmak üzere, bir \(p/q\in\mathcal F_n\) kesri bu iki sayının kesin olarak arasındadır. Dolayısıyla \[ \lfloor q\alpha\rfloor\leq p-1 \quad\text{ve}\quad \lfloor q\beta\rfloor\geq p. \] Ancak çembersel sıralamalarının aynı olması (4)'teki tüm değerleri eşit kılardı; bu bir çelişkidir.

Böylece \(N+1\) farklı güzel numaralandırma inşa ettik; dolayısıyla \[ M\geq N+1. \] (3) ile birlikte bu, \[ \boxed{M=N+1} \] eşitliğini kanıtlar.

Çözüm, resmi IMO shortlist çözümleriyle karşılaştırılarak kontrol edildi.

IMO 2013 · Problema 6

Sea \(n\ge 3\) un número entero. Se considera una circunferencia en la que se han marcado \(n+1\) puntos igualmente espaciados. Cada punto se etiqueta con uno de los números \(0,1,\ldots,n\) de manera que cada número se usa exactamente una vez. Dos distribuciones de etiquetas se consideran la misma si una se puede obtener de la otra por una rotación de la circunferencia. Una distribución de etiquetas se llama bonita si, para cualesquiera cuatro etiquetas \(a<b<c<d\), con \(a+d=b+c\), la cuerda que une los puntos etiquetados \(a\) y \(d\) no corta la cuerda que une los puntos etiquetados \(b\) y \(c\).

Sea \(M\) el número de distribuciones bonitas y \(N\) el número de pares ordenados \((x,y)\) de enteros positivos tales que \(x+y\le n\) y \(\operatorname{mcd}(x,y)=1\). Demostrar que \[ M=N+1. \]

Texto oficial en español del problema. Enunciado oficial (PDF)

Solución

Dos cuerdas con cuatro extremos distintos se cortan si y solo si sus extremos se alternan alrededor de la circunferencia. Así, que una distribución sea bonita depende únicamente del orden circular de las etiquetas. Podemos trabajar con órdenes circulares, trasladándolos a puntos igualmente espaciados cuando sea necesario.

Para \(q\geq2\), sea \[ \varphi(q)=\#\{r:1\leq r<q,\ \operatorname{mcd}(r,q)=1\}. \] Como \(\operatorname{mcd}(x,y)=\operatorname{mcd}(x,x+y)\), tenemos \[ N=\sum_{q=2}^{n}\varphi(q). \tag{1} \]

Primero demostramos una cota superior para \(M\).

Diremos que un orden circular de \(0,1,\ldots,m\) tiene la propiedad \(P\) si la aplicación \[ i\longmapsto i+1,\qquad 0\leq i<m, \] conserva el orden cíclico en sentido antihorario: una enumeración de su dominio en sentido antihorario se transforma en una enumeración de su imagen en sentido antihorario.

Toda distribución bonita tiene la propiedad \(P\). Para demostrarlo, escribimos \(P_i\) para el punto etiquetado \(i\) y consideramos los arcos en sentido antihorario \[ I_i=P_iP_{i+1},\qquad 0\leq i<n. \] Ninguno de estos arcos puede contener propiamente a otro. En efecto, los arcos con índices consecutivos no pueden contenerse uno a otro, porque uno termina en su extremo común y el otro comienza allí. Si \(i+1<j\) y uno de los arcos \(I_i\) o \(I_j\) contiene al otro, los extremos de las cuerdas \[ P_iP_{j+1}\quad\text{y}\quad P_{i+1}P_j \] se alternan. Estas cuerdas se cortarían, lo que contradice que la distribución sea bonita, porque \[ i+(j+1)=(i+1)+j. \]

Para completar el argumento, la ausencia de contenciones implica que los puntos iniciales y los puntos finales de estos arcos tienen el mismo orden cíclico. Medimos los ángulos en vueltas y enumeramos los puntos iniciales como \[ s_1<s_2<\cdots<s_n<s_1+1. \] Sea \(t_k\in(s_k,s_k+1)\) la coordenada elevada a la recta real del punto final correspondiente. Si \(t_k>t_{k+1}\), entonces \[ s_k<s_{k+1}<t_{k+1}<t_k, \] por lo que un arco contiene al otro. Análogamente, \(t_n>t_1+1\) daría una contención a través del corte elegido. Los puntos finales son distintos, por lo que \[ t_1<t_2<\cdots<t_n<t_1+1. \] Esto demuestra la propiedad \(P\).

Sea \(A_m\) el número de órdenes circulares de \(0,\ldots,m\), considerados salvo rotaciones, que tienen la propiedad \(P\). Demostraremos que \[ A_m=A_{m-1}+\varphi(m)\qquad(m\geq3). \tag{2} \]

Al eliminar \(m\) de un orden contado por \(A_m\), queda un orden contado por \(A_{m-1}\). Recíprocamente, fijemos un orden de \(0,\ldots,m-1\) que tenga la propiedad \(P\). Su aplicación \[ i\longmapsto i+1,\qquad 0\leq i\leq m-2, \] conserva el orden cíclico.

Entre los puntos etiquetados \(0,\ldots,m-2\), sean \(u\) y \(v\) el predecesor y el sucesor inmediatos del punto etiquetado \(m-1\). Para extender la propiedad \(P\), el nuevo punto etiquetado \(m\) debe estar en el hueco en sentido antihorario de \(u+1\) a \(v+1\) entre los puntos etiquetados \(1,\ldots,m-1\). Esta condición también es suficiente.

Ese hueco no contiene ningún otro punto antiguo, o bien contiene únicamente el punto etiquetado \(0\). Por consiguiente, hay exactamente una inserción posible de \(m\), excepto cuando el hueco contiene \(0\), en cuyo caso hay exactamente dos.

El caso excepcional se da precisamente cuando la permutación \[ 0\mapsto1\mapsto2\mapsto\cdots\mapsto m-1\mapsto0 \] conserva el orden cíclico de los \(m\) puntos antiguos. Toda permutación que conserva el orden cíclico de todos los puntos es una rotación de sus posiciones. Si esta rotación avanza \(r\) posiciones, consta de un solo ciclo exactamente cuando \(\operatorname{mcd}(r,m)=1\).

Hay exactamente \(\varphi(m)\) órdenes de este tipo: después de fijar la etiqueta \(0\) en la posición \(0\), cada \(r\) permitido coloca de manera única la etiqueta \(i\) en la posición \(ir\pmod m\). Cada uno de estos órdenes tiene la propiedad \(P\), puesto que la permutación indicada conserva el orden cíclico. Esto demuestra (2).

Los dos órdenes circulares de \(0,1,2\) tienen la propiedad \(P\), por lo que \(A_2=2\). Por tanto, \[ A_n=2+\sum_{q=3}^{n}\varphi(q) =1+\sum_{q=2}^{n}\varphi(q) =N+1. \] Como todo orden bonito tiene la propiedad \(P\), \[ M\leq N+1. \tag{3} \]

Ahora construimos al menos \(N+1\) órdenes bonitos distintos.

Sea \[ \mathcal F_n= \{0,1\}\cup \left\{\frac pq:1\leq p<q\leq n,\ \operatorname{mcd}(p,q)=1\right\}. \] Por (1), este conjunto tiene \(N+2\) elementos, por lo que sus elementos consecutivos determinan \(N+1\) intervalos abiertos. Elegimos un número real \(\alpha\) en cada intervalo.

Para cada uno de estos \(\alpha\), colocamos las etiquetas \(0,\ldots,n\) en los puntos complejos \[ z_k=e^{2\pi i k\alpha}. \] Estos puntos son distintos: la igualdad \(z_r=z_s\), con \(0\leq r<s\leq n\), haría que \(\alpha\) fuese un número racional cuyo denominador en forma irreducible es a lo sumo \(s-r\leq n\), en contra de su elección.

Este orden circular es bonito. En efecto, \[ z_s-z_r = 2i\,e^{\pi i(r+s)\alpha}\sin\!\bigl(\pi(s-r)\alpha\bigr). \] Así, si \(a+d=b+c\), las cuerdas \(z_az_d\) y \(z_bz_c\) son paralelas. Las rectas que las contienen son distintas, puesto que una recta no puede contener cuatro puntos distintos de una circunferencia. Por tanto, las cuerdas no se cortan. Al trasladar el mismo orden circular a puntos igualmente espaciados, esta propiedad se conserva.

Queda por demostrar que las elecciones hechas en intervalos distintos dan órdenes circulares distintos.

Cortamos la circunferencia en la etiqueta \(0\). El orden lineal de las etiquetas restantes es el orden de las partes fraccionarias \[ \{\alpha\},\{2\alpha\},\ldots,\{n\alpha\}. \] Para \(1\leq j\leq n\), ponemos \[ \varepsilon_j(\alpha)= \begin{cases} 1,&\{j\alpha\}<\{(j-1)\alpha\},\\ 0,&\{j\alpha\}>\{(j-1)\alpha\}. \end{cases} \] Estos valores están determinados por el orden circular. Como \(0<\alpha<1\), en cada paso se suma \(\alpha\), y se cruza un entero precisamente cuando la parte fraccionaria disminuye. Por tanto, \[ \lfloor q\alpha\rfloor=\sum_{j=1}^{q}\varepsilon_j(\alpha) \qquad(1\leq q\leq n). \tag{4} \]

Supongamos que \(\alpha<\beta\) se han elegido en intervalos distintos y dan el mismo orden circular. Alguna fracción \(p/q\in\mathcal F_n\), con \(q\leq n\), está estrictamente entre ellos. Por tanto, \[ \lfloor q\alpha\rfloor\leq p-1 \quad\text{y}\quad \lfloor q\beta\rfloor\geq p. \] Pero sus órdenes circulares idénticos harían que todos los valores de (4) fueran iguales, lo que es una contradicción.

Por tanto, hemos construido \(N+1\) distribuciones bonitas distintas, lo que da \[ M\geq N+1. \] Junto con (3), esto demuestra \[ \boxed{M=N+1}. \]

La solución se comprobó con las soluciones oficiales de la shortlist de la IMO.

IMO 2013 · 问题 6

设整数 \(n\ge 3\)，在圆周上有 \(n+1\) 个等分点。用数 \(0,1,\ldots,n\) 标记这些点，每个数字恰好用一次。考虑所有可能的标记方式；如果一种标记方式可以由另一种标记方式通过圆的旋转得到，那么认为这两种标记方式是同一个。一种标记方式称为是漂亮的，如果对于任意满足 \(a+d=b+c\) 的四个标记数 \(a<b<c<d\)，连接标 \(a\) 和 \(d\) 的点的弦与连接标 \(b\) 和 \(c\) 的点的弦都不相交。

设 \(M\) 是漂亮的标记方式的总数，又设 \(N\) 是满足 \(x+y\le n\)，且 \(\gcd(x,y)=1\) 的有序正整数对 \((x,y)\) 的个数。证明： \[ M=N+1. \]

题目为官方中文译本。官方试卷 (PDF)

解答

两条具有四个不同端点的弦相交，当且仅当它们的端点在圆周上交替出现。因此，标记方式是否漂亮只取决于标记的循环顺序。我们可以研究循环顺序，并在需要时将其转移到等分点上。

对于 \(q\geq2\)，令 \[ \varphi(q)=\#\{r:1\leq r<q,\ \gcd(r,q)=1\}. \] 由于 \(\gcd(x,y)=\gcd(x,x+y)\)，有 \[ N=\sum_{q=2}^{n}\varphi(q). \tag{1} \]

我们先证明 \(M\) 的一个上界。

若映射 \[ i\longmapsto i+1,\qquad 0\leq i<m, \] 保持逆时针循环顺序，即定义域中各点的一个逆时针排列被映为像集中各点的一个逆时针排列，则称 \(0,1,\ldots,m\) 的循环顺序具有性质 \(P\)。

每个漂亮的标记方式都具有性质 \(P\)。 为证明这一点，用 \(P_i\) 表示标记为 \(i\) 的点，并考虑逆时针圆弧 \[ I_i=P_iP_{i+1},\qquad 0\leq i<n. \] 这些圆弧中的任何一条都不可能真包含另一条。事实上，下标相邻的圆弧不可能相互包含，因为其中一条终止于它们的公共端点，而另一条从该端点出发。若 \(i+1<j\)，且 \(I_i\) 或 \(I_j\) 中的一条包含另一条，则弦 \[ P_iP_{j+1}\quad\text{和}\quad P_{i+1}P_j \] 的端点交替出现。这两条弦就会相交，与标记方式的漂亮性矛盾，因为 \[ i+(j+1)=(i+1)+j. \]

为使论证完整，下面说明互不包含如何推出这些圆弧的起点与终点具有相同的循环顺序。以一周为单位度量角度，将起点排列为 \[ s_1<s_2<\cdots<s_n<s_1+1. \] 设 \(t_k\in(s_k,s_k+1)\) 为相应终点提升到实轴上的坐标。若 \(t_k>t_{k+1}\)，则 \[ s_k<s_{k+1}<t_{k+1}<t_k, \] 因而一条圆弧包含另一条。同样，若 \(t_n>t_1+1\)，则会在跨越所选切口处出现包含关系。各终点互不相同，因此 \[ t_1<t_2<\cdots<t_n<t_1+1. \] 这就证明了性质 \(P\)。

设 \(A_m\) 为 \(0,\ldots,m\) 的具有性质 \(P\) 的循环顺序的个数，其中相差一个旋转的顺序视为相同。我们将证明 \[ A_m=A_{m-1}+\varphi(m)\qquad(m\geq3). \tag{2} \]

从 \(A_m\) 所计数的一个顺序中删去 \(m\)，剩下的顺序属于 \(A_{m-1}\) 所计数的顺序。反过来，固定 \(0,\ldots,m-1\) 的一个具有性质 \(P\) 的顺序。其映射 \[ i\longmapsto i+1,\qquad 0\leq i\leq m-2, \] 保持循环顺序。

在标记为 \(0,\ldots,m-2\) 的点中，设 \(u\) 和 \(v\) 分别为标记为 \(m-1\) 的点的紧邻前驱和紧邻后继。为了将性质 \(P\) 扩展到新顺序，标记为 \(m\) 的新点必须落在标记为 \(1,\ldots,m-1\) 的点中从 \(u+1\) 到 \(v+1\) 的逆时针间隙内。这一条件也是充分的。

这个间隙内或者没有其他旧点，或者只有标记为 \(0\) 的点。因此，插入 \(m\) 的方式恰有一种；唯一的例外是这个间隙包含 \(0\)，此时恰有两种插入方式。

例外情形发生，当且仅当置换 \[ 0\mapsto1\mapsto2\mapsto\cdots\mapsto m-1\mapsto0 \] 保持全部 \(m\) 个旧点的循环顺序。任何保持所有点的循环顺序的置换，都是这些点的位置的一个旋转。若这个旋转向前移动 \(r\) 个位置，则它是一个单循环，当且仅当 \(\gcd(r,m)=1\)。

这样的顺序恰有 \(\varphi(m)\) 个：将标记 \(0\) 固定在位置 \(0\) 后，每个允许的 \(r\) 都唯一地将标记 \(i\) 放在位置 \(ir\pmod m\)。这些顺序中的每一个都具有性质 \(P\)，因为上述置换保持循环顺序。这就证明了 (2)。

\(0,1,2\) 的两个循环顺序都具有性质 \(P\)，所以 \(A_2=2\)。因此 \[ A_n=2+\sum_{q=3}^{n}\varphi(q) =1+\sum_{q=2}^{n}\varphi(q) =N+1. \] 由于每个漂亮的顺序都具有性质 \(P\)， \[ M\leq N+1. \tag{3} \]

现在我们构造至少 \(N+1\) 个不同的漂亮顺序。

令 \[ \mathcal F_n= \{0,1\}\cup \left\{\frac pq:1\leq p<q\leq n,\ \gcd(p,q)=1\right\}. \] 由 (1)，这个集合有 \(N+2\) 个元素，故其相邻元素确定了 \(N+1\) 个开区间。在每个区间中选取一个实数 \(\alpha\)。

对于这样的 \(\alpha\)，将标记 \(0,\ldots,n\) 放在复平面上的点 \[ z_k=e^{2\pi i k\alpha}. \] 这些点互不相同：若 \(z_r=z_s\)，其中 \(0\leq r<s\leq n\)，则 \(\alpha\) 是一个既约分母至多为 \(s-r\leq n\) 的有理数，这与其选取方式矛盾。

这个循环顺序是漂亮的。事实上， \[ z_s-z_r = 2i\,e^{\pi i(r+s)\alpha}\sin\!\bigl(\pi(s-r)\alpha\bigr). \] 因此，若 \(a+d=b+c\)，则弦 \(z_az_d\) 和 \(z_bz_c\) 平行。它们所在的直线互不相同，因为一条直线不可能包含一个圆上的四个不同点。因此这两条弦不相交。将同一循环顺序转移到等分点上，仍保持这一性质。

剩下只需证明，从不同区间中选取的数给出不同的循环顺序。

在标记 \(0\) 处将圆周切开。其余标记的线性顺序就是小数部分 \[ \{\alpha\},\{2\alpha\},\ldots,\{n\alpha\} \] 的大小顺序。对于 \(1\leq j\leq n\)，令 \[ \varepsilon_j(\alpha)= \begin{cases} 1,&\{j\alpha\}<\{(j-1)\alpha\},\\ 0,&\{j\alpha\}>\{(j-1)\alpha\}. \end{cases} \] 这些值由循环顺序确定。由于 \(0<\alpha<1\)，每一步都加上 \(\alpha\)，且恰在小数部分减小时越过一个整数。因此 \[ \lfloor q\alpha\rfloor=\sum_{j=1}^{q}\varepsilon_j(\alpha) \qquad(1\leq q\leq n). \tag{4} \]

假设从不同区间中选取的 \(\alpha<\beta\) 给出了相同的循环顺序。存在某个分数 \(p/q\in\mathcal F_n\)，其中 \(q\leq n\)，严格位于它们之间。因此 \[ \lfloor q\alpha\rfloor\leq p-1 \quad\text{且}\quad \lfloor q\beta\rfloor\geq p. \] 但相同的循环顺序会使 (4) 中所有对应的值都相等，矛盾。

因此，我们构造出了 \(N+1\) 个不同的漂亮标记方式，从而 \[ M\geq N+1. \] 结合 (3)，即得 \[ \boxed{M=N+1}. \]

解答已与 IMO 官方预选题（shortlist）解答核对。

IMO 2013 · Задача 6

Пусть \(n\ge 3\) — целое число. Рассмотрим окружность и \(n+1\) точек на ней, разбивающих ее на равные дуги. Рассмотрим все способы пометить эти точки числами \(0,1,\ldots,n\), так, что каждое число использовано ровно один раз. Два способа, отличающихся поворотом, считаются одинаковыми. Способ пометки называется красивым, если для любых четырех меток \(a<b<c<d\) таких, что \(a+d=b+c\), хорда, соединяющая точки с метками \(a\) и \(d\), не пересекает хорду, соединяющую точки с метками \(b\) и \(c\).

Пусть \(M\) — количество красивых способов пометки. Пусть \(N\) — количество упорядоченных пар \((x,y)\) натуральных чисел, удовлетворяющих условиям \(x+y\le n\) и \(\operatorname{НОД}(x,y)=1\). Докажите, что \[ M=N+1. \]

Официальный русский текст задачи. Официальный текст задач (PDF)

Решение

Две хорды с четырьмя различными концами пересекаются тогда и только тогда, когда их концы чередуются при обходе окружности. Поэтому свойство пометки быть красивой зависит только от циклического порядка меток. Можно работать с циклическими порядками, при необходимости перенося их на равноотстоящие точки.

Для \(q\geq2\) положим \[ \varphi(q)=\#\{r:1\leq r<q,\ \operatorname{НОД}(r,q)=1\}. \] Поскольку \(\operatorname{НОД}(x,y)=\operatorname{НОД}(x,x+y)\), имеем \[ N=\sum_{q=2}^{n}\varphi(q). \tag{1} \]

Сначала докажем верхнюю оценку для \(M\).

Будем говорить, что циклический порядок меток \(0,1,\ldots,m\) обладает свойством \(P\), если отображение \[ i\longmapsto i+1,\qquad 0\leq i<m, \] сохраняет циклический порядок против часовой стрелки: перечисление элементов его области определения против часовой стрелки переходит в перечисление элементов его образа против часовой стрелки.

Любая красивая пометка обладает свойством \(P\). Чтобы это доказать, обозначим через \(P_i\) точку с меткой \(i\) и рассмотрим дуги, направленные против часовой стрелки, \[ I_i=P_iP_{i+1},\qquad 0\leq i<n. \] Ни одна из этих дуг не может строго содержать другую. Действительно, дуги с последовательными индексами не могут содержать друг друга, поскольку одна заканчивается в их общем конце, а другая начинается в нём. Если \(i+1<j\) и одна из дуг \(I_i\), \(I_j\) содержит другую, то концы хорд \[ P_iP_{j+1}\quad\text{и}\quad P_{i+1}P_j \] чередуются. Эти хорды пересекались бы, что противоречит тому, что пометка красивая, поскольку \[ i+(j+1)=(i+1)+j. \]

Для полноты объясним, почему из отсутствия вложенных дуг следует, что начальные и конечные точки этих дуг имеют один и тот же циклический порядок. Будем измерять углы в оборотах и перечислим начальные точки так, чтобы \[ s_1<s_2<\cdots<s_n<s_1+1. \] Пусть \(t_k\in(s_k,s_k+1)\) — координата соответствующей конечной точки при развёртывании окружности на прямую. Если \(t_k>t_{k+1}\), то \[ s_k<s_{k+1}<t_{k+1}<t_k, \] так что одна дуга содержит другую. Аналогично, неравенство \(t_n>t_1+1\) означало бы вложение дуг, проходящих через выбранную точку разреза. Конечные точки различны, поэтому \[ t_1<t_2<\cdots<t_n<t_1+1. \] Это доказывает свойство \(P\).

Пусть \(A_m\) — число циклических порядков меток \(0,\ldots,m\) с точностью до поворота, обладающих свойством \(P\). Покажем, что \[ A_m=A_{m-1}+\varphi(m)\qquad(m\geq3). \tag{2} \]

Удаляя \(m\) из порядка, учитываемого в \(A_m\), получаем порядок, учитываемый в \(A_{m-1}\). Обратно, зафиксируем порядок меток \(0,\ldots,m-1\), обладающий свойством \(P\). Его отображение \[ i\longmapsto i+1,\qquad 0\leq i\leq m-2, \] сохраняет циклический порядок.

Среди точек с метками \(0,\ldots,m-2\) обозначим через \(u\) и \(v\) метки ближайших предшественника и последователя точки с меткой \(m-1\). Чтобы свойство \(P\) сохранилось, новая точка с меткой \(m\) должна лежать в промежутке от \(u+1\) до \(v+1\) при обходе против часовой стрелки среди точек с метками \(1,\ldots,m-1\). Это условие также достаточно.

Этот промежуток либо не содержит других старых точек, либо содержит только точку с меткой \(0\). Следовательно, существует ровно один способ вставить \(m\), кроме случая, когда промежуток содержит \(0\): тогда способов ровно два.

Исключительный случай возникает в точности тогда, когда перестановка \[ 0\mapsto1\mapsto2\mapsto\cdots\mapsto m-1\mapsto0 \] сохраняет циклический порядок всех \(m\) старых точек. Любая перестановка, сохраняющая циклический порядок всех точек, является циклическим сдвигом их позиций. Если этот сдвиг перемещает точки на \(r\) позиций вперёд, то он состоит из одного цикла тогда и только тогда, когда \(\operatorname{НОД}(r,m)=1\).

Таких порядков ровно \(\varphi(m)\): если закрепить метку \(0\) в позиции \(0\), каждое допустимое \(r\) однозначно определяет положение метки \(i\) в позиции \(ir\pmod m\). Каждый из этих порядков обладает свойством \(P\), поскольку указанная перестановка сохраняет циклический порядок. Это доказывает (2).

Оба циклических порядка меток \(0,1,2\) обладают свойством \(P\), поэтому \(A_2=2\). Следовательно, \[ A_n=2+\sum_{q=3}^{n}\varphi(q) =1+\sum_{q=2}^{n}\varphi(q) =N+1. \] Поскольку каждый красивый порядок обладает свойством \(P\), \[ M\leq N+1. \tag{3} \]

Теперь построим не менее \(N+1\) различных красивых порядков.

Пусть \[ \mathcal F_n= \{0,1\}\cup \left\{\frac pq:1\leq p<q\leq n,\ \operatorname{НОД}(p,q)=1\right\}. \] По (1) это множество содержит \(N+2\) элемента, поэтому его соседние элементы определяют \(N+1\) открытых интервалов. Выберем в каждом интервале вещественное число \(\alpha\).

Для такого \(\alpha\) поместим метки \(0,\ldots,n\) в комплексные точки \[ z_k=e^{2\pi i k\alpha}. \] Эти точки различны: равенство \(z_r=z_s\) при \(0\leq r<s\leq n\) означало бы, что \(\alpha\) — рациональное число, знаменатель которого в несократимой записи не превосходит \(s-r\leq n\), вопреки его выбору.

Этот циклический порядок красивый. Действительно, \[ z_s-z_r = 2i\,e^{\pi i(r+s)\alpha}\sin\!\bigl(\pi(s-r)\alpha\bigr). \] Таким образом, если \(a+d=b+c\), то хорды \(z_az_d\) и \(z_bz_c\) параллельны. Содержащие их прямые различны, поскольку прямая не может содержать четыре различные точки окружности. Поэтому хорды не пересекаются. Перенос того же циклического порядка на равноотстоящие точки сохраняет это свойство.

Остаётся показать, что выбор чисел из разных интервалов даёт разные циклические порядки.

Разрежем окружность в точке с меткой \(0\). Линейный порядок остальных меток совпадает с порядком дробных частей \[ \{\alpha\},\{2\alpha\},\ldots,\{n\alpha\}. \] Для \(1\leq j\leq n\) положим \[ \varepsilon_j(\alpha)= \begin{cases} 1,&\{j\alpha\}<\{(j-1)\alpha\},\\ 0,&\{j\alpha\}>\{(j-1)\alpha\}. \end{cases} \] Эти значения определяются циклическим порядком. Поскольку \(0<\alpha<1\), на каждом шаге прибавляется \(\alpha\), причём переход через целое число происходит в точности тогда, когда дробная часть уменьшается. Следовательно, \[ \lfloor q\alpha\rfloor=\sum_{j=1}^{q}\varepsilon_j(\alpha) \qquad(1\leq q\leq n). \tag{4} \]

Предположим, что числа \(\alpha<\beta\), выбранные из разных интервалов, дали один и тот же циклический порядок. Между ними строго лежит некоторая дробь \(p/q\in\mathcal F_n\), где \(q\leq n\). Поэтому \[ \lfloor q\alpha\rfloor\leq p-1 \quad\text{и}\quad \lfloor q\beta\rfloor\geq p. \] Но из совпадения их циклических порядков следовало бы, что все значения в (4) совпадают, — противоречие.

Итак, мы построили \(N+1\) различных красивых пометок, откуда \[ M\geq N+1. \] Вместе с (3) это доказывает \[ \boxed{M=N+1}. \]

Решение проверено по официальным решениям шортлиста IMO.

IMO 2013 · المسألة 6

ليكن \(n\ge 3\) عددا صحيحا. لدينا \(n+1\) نقطة موزّعة بطريقة منتظمة على دائرة. لنعتبر كلّ التّرقيمات الممكنة لهذه النقط بواسطة الأعداد \(0\) ، \(1\) ، \(\ldots\) ، \(n\) بحيث يُستخدم كلّ عدد مرّة واحدة. نعتبر التّرقيمين متطابقين إذا أمكننا الحصول على أحدهما من الآخر بواسطة دوران حول مركز الدائرة. يقال عن ترقيم إنّه جميل إذا كان لكلّ أربع نقط مرقّمة بالأعداد \(a<b<c<d\) التي تحقّق \(a+d=b+c\) ، الوتر الواصل بين النّقطتين المرقّمتين بالعددين \(a\) و \(d\) ، لا يقطع الوتر الواصل بين النّقطتين المرقّمتين بالعددين \(b\) و \(c\) .

ليكن \(M\) عدد التّرقيمات الجميلة غير المتطابقة، و \(N\) عدد الأزواج المرتّبة \((x,y)\) من الأعداد الصّحيحة الموجبة بحيث \(x+y\le n\) و \(\gcd(x,y)=1\) . أثبت أنّ \[ M=N+1. \]

نص المسألة هو الترجمة العربية الرسمية. ورقة المسائل الرسمية (PDF)

الحل

يتقاطع وتران لهما أربعة أطراف مختلفة إذا وفقط إذا تعاقبت أطرافهما حول الدائرة. ومن ثم فإن جمال الترقيم لا يعتمد إلا على الترتيب الدائري للأعداد. ويمكننا العمل بالترتيبات الدائرية، ونقلها إلى نقاط متساوية التباعد كلما لزم ذلك.

من أجل \(q\geq2\)، ليكن \[ \varphi(q)=\#\{r:1\leq r<q,\ \gcd(r,q)=1\}. \] وبما أن \(\gcd(x,y)=\gcd(x,x+y)\)، فإن \[ N=\sum_{q=2}^{n}\varphi(q). \tag{1} \]

نثبت أولًا حدًا علويًا لـ\(M\).

نقول إن ترتيبًا دائريًا للأعداد \(0,1,\ldots,m\) يحقق الخاصية \(P\) إذا كان التطبيق \[ i\longmapsto i+1,\qquad 0\leq i<m, \] يحافظ على الترتيب الدوري عكس اتجاه عقارب الساعة: أي يحول سردًا لعناصر مجاله عكس اتجاه عقارب الساعة إلى سرد لعناصر صورته عكس اتجاه عقارب الساعة.

كل ترقيم جميل يحقق الخاصية \(P\). لإثبات ذلك، نرمز بـ\(P_i\) إلى النقطة المرقمة بالعدد \(i\)، وننظر في الأقواس المأخوذة عكس اتجاه عقارب الساعة \[ I_i=P_iP_{i+1},\qquad 0\leq i<n. \] لا يمكن لأي من هذه الأقواس أن يحتوي قوسًا آخر احتواءً فعليًا. بالفعل، لا يمكن لقوسين ذوي دليلين متتاليين أن يحتوي أحدهما الآخر، لأن أحدهما ينتهي عند طرفهما المشترك ويبدأ الآخر منه. وإذا كان \(i+1<j\) وكان أحد القوسين \(I_i\) أو \(I_j\) يحتوي الآخر، فإن أطراف الوترين \[ P_iP_{j+1}\quad\text{و}\quad P_{i+1}P_j \] تتعاقب. وعندئذ يتقاطع هذان الوتران، وهو ما يناقض جمال الترقيم لأن \[ i+(j+1)=(i+1)+j. \]

واستكمالًا للبرهان، فإن عدم الاحتواء يستلزم أن يكون لنقاط بداية هذه الأقواس ونقاط نهايتها الترتيب الدوري نفسه. نقيس الزوايا بوحدة الدورة الكاملة، ونسرد نقاط البداية على النحو الآتي: \[ s_1<s_2<\cdots<s_n<s_1+1. \] ليكن \(t_k\in(s_k,s_k+1)\) إحداثي نقطة النهاية الموافقة بعد رفعه إلى هذا المجال. إذا كان \(t_k>t_{k+1}\)، فإن \[ s_k<s_{k+1}<t_{k+1}<t_k, \] ومن ثم يحتوي أحد القوسين الآخر. وبالمثل، فإن \(t_n>t_1+1\) يؤدي إلى احتواء عبر موضع القطع المختار. ونقاط النهاية مختلفة، ولذلك \[ t_1<t_2<\cdots<t_n<t_1+1. \] وهذا يثبت الخاصية \(P\).

ليكن \(A_m\) عدد الترتيبات الدائرية للأعداد \(0,\ldots,m\)، مع اعتبار الترتيبات المتطابقة بالدوران ترتيبًا واحدًا، التي تحقق الخاصية \(P\). سنبين أن \[ A_m=A_{m-1}+\varphi(m)\qquad(m\geq3). \tag{2} \]

حذف \(m\) من ترتيب محسوب ضمن \(A_m\) يترك ترتيبًا محسوبًا ضمن \(A_{m-1}\). وبالعكس، نثبت ترتيبًا للأعداد \(0,\ldots,m-1\) يحقق الخاصية \(P\). التطبيق الموافق له \[ i\longmapsto i+1,\qquad 0\leq i\leq m-2, \] يحافظ على الترتيب الدوري.

من بين النقاط المرقمة بالأعداد \(0,\ldots,m-2\)، ليكن \(u\) و\(v\) رقمي النقطتين السابقة واللاحقة مباشرة للنقطة المرقمة بالعدد \(m-1\). ولكي تمتد الخاصية \(P\)، يجب أن تقع النقطة الجديدة المرقمة بالعدد \(m\) في الفجوة الممتدة عكس اتجاه عقارب الساعة من \(u+1\) إلى \(v+1\) بين النقاط المرقمة بالأعداد \(1,\ldots,m-1\). وهذا الشرط كافٍ أيضًا.

إما أن هذه الفجوة لا تحتوي على أي نقطة قديمة أخرى، أو أنها تحتوي فقط على النقطة المرقمة بالعدد \(0\). ولذلك توجد طريقة واحدة بالضبط لإدراج \(m\)، إلا عندما تحتوي الفجوة على \(0\)، فتوجد عندئذ طريقتان بالضبط.

تحدث الحالة الاستثنائية بالضبط عندما يحافظ التبديل \[ 0\mapsto1\mapsto2\mapsto\cdots\mapsto m-1\mapsto0 \] على الترتيب الدوري لجميع النقاط القديمة البالغ عددها \(m\). وكل تبديل يحافظ على الترتيب الدوري لجميع النقاط هو دوران لمواضعها. وإذا كان هذا الدوران يتقدم بمقدار \(r\) موضعًا، فإنه يكون دورة واحدة إذا وفقط إذا كان \(\gcd(r,m)=1\).

يوجد بالضبط \(\varphi(m)\) من هذه الترتيبات: فبعد تثبيت العدد \(0\) في الموضع \(0\)، تضع كل قيمة مسموحة لـ\(r\) العدد \(i\) في الموضع \(ir\pmod m\) على نحو وحيد. ويحقق كل من هذه الترتيبات الخاصية \(P\)، لأن التبديل المعروض يحافظ على الترتيب الدوري. وهذا يثبت (2).

كلا الترتيبين الدائريين للأعداد \(0,1,2\) يحقق الخاصية \(P\)، ومن ثم \(A_2=2\). ولذلك \[ A_n=2+\sum_{q=3}^{n}\varphi(q) =1+\sum_{q=2}^{n}\varphi(q) =N+1. \] وبما أن كل ترتيب جميل يحقق الخاصية \(P\)، فإن \[ M\leq N+1. \tag{3} \]

ننشئ الآن ما لا يقل عن \(N+1\) ترتيبًا جميلًا مختلفًا.

لتكن \[ \mathcal F_n= \{0,1\}\cup \left\{\frac pq:1\leq p<q\leq n,\ \gcd(p,q)=1\right\}. \] بحسب (1)، تحتوي هذه المجموعة على \(N+2\) عنصرًا، ومن ثم تحدد عناصرها المتتالية \(N+1\) مجالًا مفتوحًا. نختار عددًا حقيقيًا \(\alpha\) في كل مجال.

من أجل \(\alpha\) كهذا، نضع الأعداد \(0,\ldots,n\) عند النقاط المركبة \[ z_k=e^{2\pi i k\alpha}. \] هذه النقاط مختلفة: فالمساواة \(z_r=z_s\)، حيث \(0\leq r<s\leq n\)، تجعل \(\alpha\) عددًا نسبيًا مقامه بعد الاختزال لا يتجاوز \(s-r\leq n\)، خلافًا لاختياره.

هذا الترتيب الدائري جميل. بالفعل، \[ z_s-z_r = 2i\,e^{\pi i(r+s)\alpha}\sin\!\bigl(\pi(s-r)\alpha\bigr). \] إذن، إذا كان \(a+d=b+c\)، فإن الوترين \(z_az_d\) و\(z_bz_c\) متوازيان. والمستقيمان الحاملان لهما مختلفان، إذ لا يمكن لمستقيم أن يحتوي على أربع نقاط مختلفة من دائرة. ولذلك لا يتقاطع الوتران. ونقل الترتيب الدائري نفسه إلى نقاط متساوية التباعد يحافظ على هذه الخاصية.

يبقى أن نبين أن الاختيارات من مجالات مختلفة تعطي ترتيبات دائرية مختلفة.

نقطع الدائرة عند العدد \(0\). الترتيب الخطي للأعداد الباقية هو ترتيب الأجزاء الكسرية \[ \{\alpha\},\{2\alpha\},\ldots,\{n\alpha\}. \] من أجل \(1\leq j\leq n\)، نضع \[ \varepsilon_j(\alpha)= \begin{cases} 1,&\{j\alpha\}<\{(j-1)\alpha\},\\ 0,&\{j\alpha\}>\{(j-1)\alpha\}. \end{cases} \] يحدد الترتيب الدائري هذه القيم. وبما أن \(0<\alpha<1\)، فإن كل خطوة تضيف \(\alpha\)، وتعبر عددًا صحيحًا بالضبط عندما ينقص الجزء الكسري. ومن ثم \[ \lfloor q\alpha\rfloor=\sum_{j=1}^{q}\varepsilon_j(\alpha) \qquad(1\leq q\leq n). \tag{4} \]

لنفترض أن \(\alpha<\beta\) اختيرا من مجالين مختلفين وأعطيا الترتيب الدائري نفسه. يوجد كسر \(p/q\in\mathcal F_n\)، حيث \(q\leq n\)، يقع بينهما تمامًا. وبالتالي \[ \lfloor q\alpha\rfloor\leq p-1 \quad\text{و}\quad \lfloor q\beta\rfloor\geq p. \] لكن تطابق ترتيبيهما الدائريين يجعل جميع القيم في (4) متساوية، وهذا تناقض.

وبذلك أنشأنا \(N+1\) ترقيمًا جميلًا مختلفًا، مما يعطي \[ M\geq N+1. \] وبالاقتران مع (3)، يثبت هذا أن \[ \boxed{M=N+1}. \]

تمت مراجعة الحل بمقارنته بالحلول الرسمية لقائمة IMO المختصرة.