Shortlist 2013, C7

Domaine : Combinatoire · Difficulté : ★★★★★ · Proposé par : Russia

Concepts : Bijections et dénombrement · Récurrence et constructions récursives · Fonctions arithmétiques : nombre de diviseurs, indicatrice d'Euler, somme des diviseurs

Solution officielle : Shortlist officielle 2013 (avec solutions), p. 33 (page 33 du PDF)

Problème 6 de l'OIM 2013

Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2013, où il était le problème 6 (jour 2).

Figures reprises du livret officiel de la Shortlist.

Pas encore relu

Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.

Énoncé

Let \(n \geq 2\) be an integer. Consider all circular arrangements of the numbers \(0, 1, \ldots, n\); the \(n + 1\) rotations of an arrangement are considered to be equal. A circular arrangement is called beautiful if, for any four distinct numbers \(0 \leq a, b, c, d \leq n\) with \(a + c = b + d\), the chord joining numbers \(a\) and \(c\) does not intersect the chord joining numbers \(b\) and \(d\).

Let \(M\) be the number of beautiful arrangements of \(0, 1, \ldots, n\). Let \(N\) be the number of pairs \((x, y)\) of positive integers such that \(x + y \leq n\) and \(\gcd(x, y) = 1\). Prove that

\[M = N + 1.\]

Indices : les idées clés

• Cordes alignées (solution 1) : dans une disposition belle, les \(k\)-cordes (extrémités de somme \(k\)) sont « alignées » ; on le montre par récurrence en retirant \(0\) ou \(n\).
• Récurrence : en retirant \(n\), \(M_n = M_{n-1} + L_{n-1}\), où \(L_{n-1}\) compte les dispositions de \([0, n - 1]\) « de type 2 » ; une telle disposition est \(f(-ak) = k\) avec \(\operatorname{pgcd}(a, n) = 1\), d'où \(L_{n-1} = \varphi(n)\) (indicatrice d'Euler).
• Bijection avec des fractions (solution 2) : les dispositions belles sont exactement les dispositions « cycliques » \(A(\alpha)\) (le point \(k\) placé en \(\{k\alpha\}\)), qui changent seulement quand \(\alpha\) franchit l'une des \(N\) fractions irréductibles de dénominateur au plus \(n\).

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2013 (deux solutions).

Solution 1

Étant donnée une disposition circulaire de \([0, n] = \{0, 1, \ldots, n\}\), on appelle \(k\)-corde une corde (éventuellement dégénérée) dont les extrémités (éventuellement égales) ont pour somme \(k\). Trois cordes d'un cercle sont dites alignées si l'une d'elles sépare les deux autres. On dit que \(m \geq 3\) cordes sont alignées si trois quelconques d'entre elles le sont. Par exemple, sur la figure 1, \(A\), \(B\) et \(C\) sont alignées, alors que \(B\), \(C\) et \(D\) ne le sont pas.

Affirmation. Dans une disposition belle, les \(k\)-cordes sont alignées, pour tout entier \(k\).

Preuve. Par récurrence. Pour \(n \leq 3\), c'est évident. Soit \(n \geq 4\), et raisonnons par l'absurde. Considérons une disposition belle \(S\) dans laquelle trois \(k\)-cordes \(A\), \(B\), \(C\) ne sont pas alignées. Si \(n\) n'est pas une extrémité de \(A\), \(B\), \(C\), en supprimant \(n\) de \(S\) on obtient une disposition belle \(S \setminus \{n\}\) de \([0, n - 1]\), dans laquelle \(A\), \(B\) et \(C\) sont alignées par hypothèse de récurrence. De même, si \(0\) n'est pas une extrémité, en supprimant \(0\) et en diminuant tous les nombres de \(1\), on obtient une disposition belle \(S \setminus \{0\}\) dans laquelle \(A\), \(B\) et \(C\) sont alignées. Donc \(0\) et \(n\) sont tous deux des extrémités de ces cordes. Si \(x\) et \(y\) sont leurs partenaires respectifs, on a \(n \geq 0 + x = k = n + y \geq n\). Donc \(0\) et \(n\) sont les extrémités d'une même corde ; disons \(C\).

Soit \(D\) la corde formée par les nombres \(u\) et \(v\) voisins de \(0\) et de \(n\), situés du même côté de \(C\) que \(A\) et \(B\), comme sur la figure 2. Posons \(t = u + v\). Si l'on avait \(t = n\), les \(n\)-cordes \(A\), \(B\) et \(D\) ne seraient pas alignées dans la disposition belle \(S \setminus \{0, n\}\), ce qui contredit l'hypothèse de récurrence. Si \(t < n\), la \(t\)-corde de \(0\) à \(t\) ne peut pas couper \(D\), donc la corde \(C\) sépare \(t\) de \(D\). La corde \(E\) de \(t\) à \(n - t\) ne coupe pas \(C\), donc \(t\) et \(n - t\) sont du même côté de \(C\). Mais alors les cordes \(A\), \(B\) et \(E\) ne sont pas alignées dans \(S \setminus \{0, n\}\), une contradiction. Enfin, le cas \(t > n\) équivaut au cas \(t < n\) par le changement de numérotation \(x \mapsto n - x\) pour \(0 \leq x \leq n\), qui préserve la beauté et envoie les \(t\)-cordes sur les \((2n - t)\)-cordes. Cela prouve l'affirmation. \(\square\)

Une fois l'affirmation établie, on prouve le résultat par récurrence. Le cas \(n = 2\) est évident. Supposons \(n \geq 3\). Soit \(S\) une disposition belle de \([0, n]\) ; supprimons \(n\) pour obtenir la disposition belle \(T\) de \([0, n - 1]\). Les \(n\)-cordes de \(T\) sont alignées, et elles contiennent tous les points sauf \(0\). On dit que \(T\) est de type 1 si \(0\) est entre deux de ces \(n\)-cordes, et de type 2 sinon, c'est-à-dire si \(0\) est aligné avec ces \(n\)-cordes. On va montrer que chaque disposition de type 1 de \([0, n - 1]\) provient d'une unique disposition de \([0, n]\), et chaque disposition de type 2 de exactement deux dispositions belles de \([0, n]\).

Si \(T\) est de type 1, supposons \(0\) entre les cordes \(A\) et \(B\). Comme la corde de \(0\) à \(n\) doit être alignée avec \(A\) et \(B\) dans \(S\), le point \(n\) doit être sur l'autre arc entre \(A\) et \(B\). Donc \(S\) se retrouve de façon unique à partir de \(T\). Réciproquement, si \(T\) est de type 1 et qu'on insère \(n\) comme ci-dessus, la disposition \(S\) obtenue est belle. Pour \(0 < k < n\), les \(k\)-cordes de \(S\) sont aussi des \(k\)-cordes de \(T\), donc elles sont alignées. Enfin, pour \(n < k < 2n\), on remarque que les \(n\)-cordes de \(S\) sont parallèles par construction ; il existe donc un axe d'antisymétrie \(\ell\) tel que \(x\) et \(n - x\) soient symétriques par rapport à \(\ell\) pour tout \(x\). Si deux \(k\)-cordes se coupaient, leurs symétriques par rapport à \(\ell\) seraient deux \((2n - k)\)-cordes qui se coupent, avec \(0 < 2n - k < n\), une contradiction.

Si \(T\) est de type 2, il y a deux positions possibles pour \(n\) dans \(S\), de part et d'autre de \(0\). Comme ci-dessus, on vérifie que les deux positions donnent des dispositions belles de \([0, n]\).

Si l'on note \(M_n\) le nombre de dispositions belles de \([0, n]\) et \(L_n\) le nombre de dispositions belles de \([0, n - 1]\) de type 2, on a donc

\[M_n = (M_{n-1} - L_{n-1}) + 2L_{n-1} = M_{n-1} + L_{n-1}.\]

Il reste à montrer que \(L_{n-1}\) est le nombre de couples \((x, y)\) d'entiers strictement positifs tels que \(x + y = n\) et \(\operatorname{pgcd}(x, y) = 1\). Comme \(n \geq 3\), ce nombre vaut \(\varphi(n) = \#\{x : 1 \leq x \leq n, \; \operatorname{pgcd}(x, n) = 1\}\).

Pour le prouver, considérons une disposition belle de type 2 de \([0, n - 1]\). Numérotons les positions \(0, \ldots, n - 1 \pmod n\) dans le sens des aiguilles d'une montre, de sorte que le nombre \(0\) soit en position \(0\). Soit \(f(i)\) le nombre en position \(i\) ; \(f\) est une permutation de \([0, n - 1]\). Soit \(a\) la position telle que \(f(a) = n - 1\).

Comme les \(n\)-cordes sont alignées avec \(0\) et que chaque point est sur une \(n\)-corde, ces cordes sont toutes parallèles, et

\[f(i) + f(-i) = n \quad \text{pour tout } i.\]

De même, comme les \((n - 1)\)-cordes sont alignées et que chaque point est sur une \((n - 1)\)-corde, ces cordes sont aussi parallèles, et

\[f(i) + f(a - i) = n - 1 \quad \text{pour tout } i.\]

Donc \(f(a - i) = f(-i) - 1\) pour tout \(i\) ; comme \(f(0) = 0\), on obtient

\[f(-ak) = k \quad \text{pour tout } k. \tag{1}\]

Il s'agit d'une égalité modulo \(n\). Comme \(f\) est une permutation, on doit avoir \(\operatorname{pgcd}(a, n) = 1\). Donc \(L_{n-1} \leq \varphi(n)\).

Pour avoir l'égalité, il reste à remarquer que la numérotation (1) est belle. Considérons quatre nombres \(w\), \(x\), \(y\), \(z\) du cercle avec \(w + y = x + z\). Leurs positions vérifient \((-aw) + (-ay) = (-ax) + (-az)\), ce qui signifie que la corde de \(w\) à \(y\) et la corde de \(x\) à \(z\) sont parallèles. Donc (1) est belle, et par construction elle est de type 2. Le résultat suit. \(\blacksquare\)

Solution 2

Il y a exactement \(N\) fractions irréductibles \(f_1 < \cdots < f_N\) dans \((0, 1)\) de dénominateur au plus \(n\), puisque le couple \((x, y)\) avec \(x + y \leq n\) et \(\operatorname{pgcd}(x, y) = 1\) correspond à la fraction \(\frac{x}{x + y}\). Écrivons \(f_i = \frac{a_i}{b_i}\) pour \(1 \leq i \leq N\).

Construisons d'abord \(N + 1\) dispositions belles. Prenons \(\alpha \in (0, 1)\) qui n'est pas l'une des \(N\) fractions ci-dessus. Considérons un cercle de périmètre \(1\). Marquons successivement les points \(0, 1, 2, \ldots, n\), où \(0\) est quelconque et la distance de \(i\) à \(i + 1\) dans le sens des aiguilles d'une montre est \(\alpha\). Le point \(k\) est alors à distance \(\{k\alpha\}\) de \(0\), où \(\{r\}\) désigne la partie fractionnaire de \(r\). Une telle disposition est dite cyclique, et on la note \(A(\alpha)\). Si l'ordre des points est le même dans \(A(\alpha_1)\) et \(A(\alpha_2)\), on les considère comme la même disposition. La figure 3 montre la disposition cyclique \(A(3/5 + \epsilon)\) de \([0, 13]\), où \(\epsilon > 0\) est très petit.

Si \(0 \leq a, b, c, d \leq n\) vérifient \(a + c = b + d\), alors \(a\alpha + c\alpha = b\alpha + d\alpha\), donc la corde de \(a\) à \(c\) est parallèle à la corde de \(b\) à \(d\) dans \(A(\alpha)\). Dans une disposition cyclique, toutes les \(k\)-cordes sont donc parallèles. En particulier, toute disposition cyclique est belle.

Montrons ensuite qu'il y a exactement \(N + 1\) dispositions cycliques distinctes. Voyons comment \(A(\alpha)\) change quand \(\alpha\) croît de \(0\) à \(1\). L'ordre des points \(p\) et \(q\) change exactement quand on franchit une valeur \(\alpha = f\) telle que \(\{pf\} = \{qf\}\) ; cela ne peut arriver que si \(f\) est l'une des \(N\) fractions \(f_1, \ldots, f_N\). Il y a donc au plus \(N + 1\) dispositions cycliques différentes.

Pour montrer qu'elles sont toutes distinctes, rappelons que \(f_i = \frac{a_i}{b_i}\) et soit \(\epsilon > 0\) très petit. Dans la disposition \(A(f_i + \epsilon)\), le point \(k\) est en \(\frac{k a_i \bmod b_i}{b_i} + k\epsilon\). Les points sont donc groupés en \(b_i\) paquets à côté des points \(0, \frac{1}{b_i}, \ldots, \frac{b_i - 1}{b_i}\) du cercle. Le paquet qui suit \(\frac{k}{b_i}\) contient les nombres congrus à \(k a_i^{-1}\) modulo \(b_i\), rangés dans l'ordre croissant dans le sens des aiguilles d'une montre. Il s'ensuit que le premier nombre après \(0\) dans \(A(f_i + \epsilon)\) est \(b_i\), et que le premier nombre après \(0\) qui est inférieur à \(b_i\) est \(a_i^{-1} \pmod{b_i}\), ce qui détermine \(a_i\). On retrouve ainsi \(f_i\) à partir de la disposition cyclique. Remarquons aussi que \(A(f_i + \epsilon)\) n'est pas la disposition triviale où l'on range \(0, 1, \ldots, n\) dans l'ordre. Il s'ensuit que les \(N + 1\) dispositions cycliques \(A(\epsilon), A(f_1 + \epsilon), \ldots, A(f_N + \epsilon)\) sont distinctes.

Notons une observation qui servira plus loin :

\[\text{si } f_i < \alpha < f_{i+1}, \text{ alors } 0 \text{ est juste après } b_{i+1} \text{ et juste avant } b_i \text{ dans } A(\alpha). \tag{2}\]

En effet, on a vu que \(b_i\) est le premier nombre après \(0\) dans \(A(f_i + \epsilon) = A(\alpha)\). De même, \(b_{i+1}\) est le dernier nombre avant \(0\) dans \(A(f_{i+1} - \epsilon) = A(\alpha)\).

Montrons enfin, par récurrence sur \(n\), que toute disposition belle de \([0, n]\) est cyclique. Pour \(n \leq 2\), c'est clair. Supposons que toutes les dispositions belles de \([0, n - 1]\) soient cycliques, et considérons une disposition belle \(A\) de \([0, n]\). La sous-disposition \(A_{n-1} = A \setminus \{n\}\) de \([0, n - 1]\), obtenue en supprimant \(n\), est cyclique ; disons \(A_{n-1} = A_{n-1}(\alpha)\).

Soit \(\alpha\) entre les fractions consécutives \(\frac{p_1}{q_1} < \frac{p_2}{q_2}\) parmi les fractions irréductibles de dénominateur au plus \(n - 1\). Il y a au plus une fraction \(\frac{i}{n}\) dans \(\left(\frac{p_1}{q_1}, \frac{p_2}{q_2}\right)\), puisque \(\frac{i}{n} < \frac{i}{n - 1} \leq \frac{i + 1}{n}\) pour \(0 < i \leq n - 1\).

Cas 1 : il n'y a pas de fraction de dénominateur \(n\) entre \(\frac{p_1}{q_1}\) et \(\frac{p_2}{q_2}\). La seule disposition cyclique qui prolonge \(A_{n-1}(\alpha)\) est alors \(A_n(\alpha)\). On sait que \(A\) et \(A_n(\alpha)\) ne peuvent différer que par la position de \(n\). Supposons que \(n\) soit juste après \(x\) et juste avant \(y\) dans \(A_n(\alpha)\). Comme les voisins de \(0\) sont \(q_1\) et \(q_2\) par (2), on a \(x, y \geq 1\).

Dans \(A_n(\alpha)\), la corde de \(n - 1\) à \(x\) est parallèle et adjacente à la corde de \(n\) à \(x - 1\), donc \(n - 1\) est entre \(x - 1\) et \(x\) dans le sens des aiguilles d'une montre, comme sur la figure 4. De même, \(n - 1\) est entre \(y\) et \(y - 1\). Donc \(x\), \(y\), \(x - 1\), \(n - 1\) et \(y - 1\) apparaissent dans cet ordre dans \(A_n(\alpha)\), et donc dans \(A\) (avec éventuellement \(y = x - 1\) ou \(x = y - 1\)).

Or \(A\) ne peut différer de \(A_n(\alpha)\) que par la position de \(n\). Dans \(A\), comme la corde de \(n - 1\) à \(x\) et la corde de \(n\) à \(x - 1\) ne se coupent pas, \(n\) est entre \(x\) et \(n - 1\). De même, \(n\) est entre \(n - 1\) et \(y\). Donc \(n\) est entre \(x\) et \(y\), et \(A = A_n(\alpha)\). Ainsi \(A\) est cyclique, comme voulu.

Cas 2 : il existe exactement un \(i\) tel que \(\frac{p_1}{q_1} < \frac{i}{n} < \frac{p_2}{q_2}\). Il existe alors deux dispositions cycliques \(A_n(\alpha_1)\) et \(A_n(\alpha_2)\) des nombres \(0, \ldots, n\) prolongeant \(A_{n-1}(\alpha)\), avec \(\frac{p_1}{q_1} < \alpha_1 < \frac{i}{n}\) et \(\frac{i}{n} < \alpha_2 < \frac{p_2}{q_2}\). Dans \(A_{n-1}(\alpha)\), le seul nombre entre \(q_2\) et \(q_1\) est \(0\), par (2). Pour la même raison, \(n\) est entre \(q_2\) et \(0\) dans \(A_n(\alpha_1)\), et entre \(0\) et \(q_1\) dans \(A_n(\alpha_2)\).

En posant \(x = q_2\) et \(y = q_1\), l'argument du cas 1 montre que \(n\) doit être entre \(x\) et \(y\) dans \(A\). Donc \(A\) est égale à \(A_n(\alpha_1)\) ou à \(A_n(\alpha_2)\), et elle est cyclique.

Cela achève la preuve que toute disposition belle est cyclique. Il y a donc exactement \(N + 1\) dispositions belles de \([0, n]\), comme voulu. \(\blacksquare\)