Exercice national 1 — Étiquetage gracieux d'une figure (tous candidats)

C3. Deux étiquettes de parités différentes donnent une différence impaire ; de même parité, une différence paire.

C4. Compter, dans un pentagone (5 sommets, 5 arêtes), combien de pondérations doivent être impaires (les entiers impairs entre 1 et 5) et comparer au nombre de segments reliant des sommets de parités différentes, sachant que ce nombre est contraint par la répartition des 5 étiquettes entre pairs et impairs.

D1. Nombre de segments de \(K_n\) : \(\binom n2=\dfrac{n(n-1)}2\).

D2-3. Les pondérations impaires sont en nombre fixé (les entiers impairs entre 1 et \(n\)) ; d'autre part, ce nombre égale le nombre de segments reliant un point pair à un point impair, soit \(p\times(2022-p)\) si \(p\) est le nombre de points pairs. Confronter les deux expressions pour obtenir une contradiction.

A.1. Les étiquetages proposés sont-ils gracieux ?

L'énoncé ne fournit pas de figure spécifique ici. En général, pour vérifier si un étiquetage est gracieux, on calcule les pondérations de tous les segments (valeur absolue de la différence des étiquettes des extrémités) et on vérifie si l'ensemble de ces pondérations est exactement \(\{1, 2, \dots, n\}\), où \(n\) est le nombre de segments. Sans figure, on ne peut pas répondre numériquement. On suppose que l'élève doit appliquer cette définition aux figures données dans l'énoncé original.

A.2. Compléter un étiquetage pour le rendre gracieux.

De même, sans la figure, on ne peut pas donner de valeurs. La méthode générale consiste à attribuer des entiers distincts de 0 à \(n\) aux points de sorte que les différences absolues sur les segments donnent tous les entiers de 1 à \(n\). On peut procéder par essais ou en utilisant des symétries.

B. \(L_n\) = ligne de \(n+1\) points alignés, \(n\) segments.

B.1. Trouver un étiquetage gracieux pour \(L_5, L_6, L_7\).

Pour une ligne de \(n+1\) points alignés (donc \(n\) segments), un étiquetage gracieux classique consiste à étiqueter les points de gauche à droite avec la suite : \(0, n, 1, n-1, 2, n-2, \dots\) (alternance entre les extrémités).

• Pour \(L_5\) : \(n=5\), points : \(P_0, P_1, P_2, P_3, P_4, P_5\) (6 points).

Étiquetage : \(0, 5, 1, 4, 2, 3\).

Segments :

• entre 0 et 5 : \(|0-5| = 5\)

• entre 5 et 1 : \(|5-1| = 4\)

• entre 1 et 4 : \(|1-4| = 3\)

• entre 4 et 2 : \(|4-2| = 2\)

• entre 2 et 3 : \(|2-3| = 1\)

Pondérations : \(\{1,2,3,4,5\}\). C'est gracieux.

• Pour \(L_6\) : \(n=6\), points : \(0, 6, 1, 5, 2, 4, 3\).

Segments :

• \(0-6\) : 6

• \(6-1\) : 5

• \(1-5\) : 4

• \(5-2\) : 3

• \(2-4\) : 2

• \(4-3\) : 1

Pondérations : \(\{1,2,3,4,5,6\}\). Gracieux.

• Pour \(L_7\) : \(n=7\), points : \(0, 7, 1, 6, 2, 5, 3, 4\).

Segments :

• \(0-7\) : 7

• \(7-1\) : 6

• \(1-6\) : 5

• \(6-2\) : 4

• \(2-5\) : 3

• \(5-3\) : 2

• \(3-4\) : 1

Pondérations : \(\{1,2,3,4,5,6,7\}\). Gracieux.

B.2. Décrire un étiquetage gracieux de \(L_{2022}\) (point le plus à gauche étiqueté 0, admis).

On généralise la méthode précédente. Pour \(n=2022\), on a \(2023\) points. On étiquette les points de gauche à droite par la suite :

\[0,\ 2022,\ 1,\ 2021,\ 2,\ 2020,\ \dots,\ 1010,\ 1012,\ 1011\]

Plus formellement, pour \(k\) de \(0\) à \(2022\) :

• Si \(k\) est pair : étiquette \( \frac{k}{2} \)

• Si \(k\) est impair : étiquette \( 2022 - \frac{k-1}{2} \)

Les segments successifs donnent les différences :

• Entre le premier et le deuxième : \(2022 - 0 = 2022\)

• Entre le deuxième et le troisième : \(2022 - 1 = 2021\)

• Entre le troisième et le quatrième : \(2021 - 1 = 2020\)

• ...

• Entre l'avant-dernier et le dernier : \(1012 - 1011 = 1\)

On obtient bien toutes les pondérations de 1 à 2022. C'est un étiquetage gracieux.

C.1. Tout triangle et tout quadrilatère admettent un étiquetage gracieux.

• Triangle (3 segments, 3 points) : On étiquette les sommets avec \(0, 1, 3\).

Segments :

• \(0-1\) : 1

• \(1-3\) : 2

• \(0-3\) : 3

Pondérations : \(\{1,2,3\}\). Gracieux.

• Quadrilatère (4 segments, 4 points) : On étiquette les sommets dans l'ordre cyclique avec \(0, 2, 1, 4\) (la version \(0,4,1,3\) parfois citée n'est en fait pas gracieuse : elle referme le cycle sur \(|3-0|=3\), qui duplique la pondération déjà obtenue entre 4 et 1, et ne produit jamais 1).

Segments :

• \(0-2\) : 2

• \(2-1\) : 1

• \(1-4\) : 3

• \(4-0\) : 4

Pondérations : \(\{1,2,3,4\}\). Gracieux.

C.2. À partir d'un étiquetage gracieux d'un polygone à 11 côtés, en déduire un pour 12 côtés.

Un étiquetage gracieux d'un polygone à 11 côtés est \(0, 4, 6, 5, 8, 3, 9, 2, 10, 1, 11\) (ordre cyclique) : les pondérations successives sont \(4,2,1,3,5,6,7,8,9,10,11\), soit exactement \(\{1,\dots,11\}\) — donc gracieux. (L'étiquetage \(0,11,1,10,2,9,\dots\) utilisé pour la ligne \(L_{11}\) en partie B ne fonctionne pas pour un cycle : la fermeture du dernier côté produit une pondération dupliquée.)

Un étiquetage gracieux d'un polygone à 12 côtés est \(0, 5, 4, 8, 6, 9, 3, 10, 2, 11, 1, 12\) (ordre cyclique) : les pondérations successives sont \(5,1,4,2,3,6,7,8,9,10,11,12\), soit exactement \(\{1,\dots,12\}\) — donc gracieux également.

C.3. Parité de la pondération d'un segment selon la parité des étiquettes de ses extrémités.

Soient deux étiquettes \(x\) et \(y\). La pondération est \(|x-y|\).

• Si \(x\) et \(y\) ont même parité (tous deux pairs ou tous deux impairs), alors \(x-y\) est pair, donc \(|x-y|\) est pair.

• Si \(x\) et \(y\) ont des parités différentes, alors \(x-y\) est impair, donc \(|x-y|\) est impair.

Ainsi, la pondération d'un segment est impaire si et seulement si les étiquettes de ses extrémités sont de parités différentes.

C.4. En déduire qu'aucun pentagone n'a d'étiquetage gracieux.

Un pentagone a 5 segments et 5 points. Les étiquettes sont des entiers distincts de 0 à 5 (car \(n=5\)). Parmi ces 6 entiers (0,1,2,3,4,5), il y a 3 pairs (0,2,4) et 3 impairs (1,3,5). Mais on n'utilise que 5 étiquettes pour 5 points. Donc, selon le choix, le nombre de points étiquetés pairs peut être 2 ou 3 (et impairs 3 ou 2). Notons \(p\) le nombre de points pairs. Alors le nombre de segments reliant deux points de parités différentes est \(p \times (5-p)\) (car chaque point pair est relié à chaque point impair). Ce nombre doit être égal au nombre de pondérations impaires, car un segment a une pondération impaire si et seulement si ses extrémités sont de parités différentes. Or, dans un étiquetage gracieux, les pondérations sont 1,2,3,4,5. Les pondérations impaires sont 1,3,5 : il y en a 3. Donc on doit avoir \(p \times (5-p) = 3\). Or pour \(p=0,1,2,3,4,5\), \(p(5-p)\) vaut respectivement \(0,4,6,6,4,0\) : la valeur 3 n'est jamais atteinte. Donc c'est impossible. Aucun pentagone n'admet d'étiquetage gracieux.

D. \(K_{2022}\) : 2022 points, tous reliés deux à deux.

D.1. Montrer qu'il y a 2 043 231 segments.

Le nombre de segments dans un graphe complet à \(N\) points est \(\frac{N(N-1)}{2}\). Ici \(N=2022\).

\[\frac{2022 \times 2021}{2} = 1011 \times 2021\]

Calculons : \(1011 \times 2021 = 1011 \times (2000 + 21) = 1011 \times 2000 + 1011 \times 21 = 2\,022\,000 + 21\,231 = 2\,043\,231\).

Donc il y a bien 2 043 231 segments.

D.2. Si un étiquetage gracieux existe :

a) Nombre de segments de pondération impaire ?

Dans un étiquetage gracieux, les pondérations sont exactement les entiers de 1 à \(n\), où \(n = 2\,043\,231\). Parmi ces entiers, les impairs sont ceux de la forme \(2k-1\) pour \(k=1\) à \(\frac{n+1}{2}\). Le nombre d'entiers impairs de 1 à \(n\) est \(\frac{n+1}{2}\) si \(n\) est impair. Ici \(n=2\,043\,231\) est impair (car se termine par 1). Donc le nombre de segments de pondération impaire est :

\[\frac{2\,043\,231 + 1}{2} = \frac{2\,043\,232}{2} = 1\,021\,616\]

b) En notant \(p\) le nombre de points étiquetés pair, exprimer ce nombre en fonction de \(p\).

Soit \(p\) le nombre de points dont l'étiquette est paire. Alors le nombre de points impairs est \(2022 - p\). Un segment a une pondération impaire si et seulement si ses extrémités sont de parités différentes. Le nombre de tels segments est donc \(p \times (2022 - p)\) (car chaque point pair est relié à chaque point impair). Ainsi, le nombre de segments de pondération impaire est \(p(2022-p)\).

D.3. En déduire que \(K_{2022}\) n'a pas d'étiquetage gracieux.

On a deux expressions pour le nombre de segments de pondération impaire :

• D'après D.2.a : \(1\,021\,616\)

• D'après D.2.b : \(p(2022-p)\)

On doit donc avoir \(p(2022-p) = 1\,021\,616\). Résolvons cette équation :

\[p(2022-p) = 1\,021\,616 \quad \Rightarrow \quad -p^2 + 2022p - 1\,021\,616 = 0 \quad \Rightarrow \quad p^2 - 2022p + 1\,021\,616 = 0\]

Calculons le discriminant :

\[\Delta = 2022^2 - 4 \times 1\,021\,616\]

\(2022^2 = (2000+22)^2 = 4\,000\,000 + 2 \times 2000 \times 22 + 484 = 4\,000\,000 + 88\,000 + 484 = 4\,088\,484\)

\(4 \times 1\,021\,616 = 4\,086\,464\)

Donc \(\Delta = 4\,088\,484 - 4\,086\,464 = 2\,020\)

\(\sqrt{\Delta} = \sqrt{2020} = \sqrt{4 \times 505} = 2\sqrt{505}\). Ce n'est pas un entier car 505 n'est pas un carré parfait (\(22^2=484\), \(23^2=529\)). Donc \(p\) ne serait pas entier. Or \(p\) est un entier (nombre de points). Donc impossible. Ainsi, \(K_{2022}\) n'admet pas d'étiquetage gracieux.