Aller au contenu

Shortlist 2023, C7

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

Concepts : Graphes : degrés, chemins, arbres · Principe extrémal

Solution officielle : Shortlist officielle 2023 (avec solutions), p. 52 (page 54 du PDF)

Pas encore relu

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

Énoncé

The Imomi archipelago consists of \(n \geq 2\) islands. Between each pair of distinct islands is a unique ferry line that runs in both directions, and each ferry line is operated by one of \(k\) companies. It is known that if any one of the \(k\) companies closes all its ferry lines, then it becomes impossible for a traveller, no matter where the traveller starts at, to visit all the islands exactly once (in particular, not returning to the island the traveller started at).

Determine the maximal possible value of \(k\) in terms of \(n\).

Indices : les idées clés
  • Graphes : on colorie les arêtes du graphe complet \(K_n\) avec \(k\) couleurs de sorte que tout chemin hamiltonien contienne les \(k\) couleurs (coloriage « bon »).
  • Construction dyadique : colorier l'arête \(ij\) (\(i < j\)) avec la « couleur » \(\min(\lfloor \log_2 i \rfloor + 1, k)\) du sommet \(i\) ; une couleur portée par plus de la moitié des sommets ne peut être évitée.
  • Recolorier sans perdre la propriété : si \(d_i(A) + d_i(B) \leq n - 1\), l'arête \(AB\) de couleur \(i\) peut être recoloriée ; en partant d'un sommet de degré monochromatique maximal (principe extrémal), on se ramène à une structure où l'arête \(A_u A_v\) (\(u < v\)) a la couleur du sommet \(A_u\).
  • Majorité dans un préfixe : chaque couleur doit être majoritaire dans un préfixe \(A_1, \ldots, A_{p_i}\), et en prenant les \(p_i\) minimaux on obtient \(p_i \geq 2^i - 1\), d'où \(n \geq 2^k\).
Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2023 (une solution).

Réponse. La plus grande valeur de \(k\) est \(k = \lfloor \log_2 n \rfloor\).

Solution

Reformulation. On a un graphe complet \(K_n\) (les sommets sont les îles) dont on colorie les arêtes (les lignes de ferry) avec \(k\) couleurs (les compagnies), de sorte que tout chemin hamiltonien contienne les \(k\) couleurs. Pour un ensemble fixé de \(k\) couleurs, on dit qu'un coloriage des arêtes de \(K_n\) est bon si tout chemin hamiltonien contient une arête de chacune des \(k\) couleurs.

Construction pour \(k = \lfloor \log_2 n \rfloor\).

Affirmation 1. Soit \(k = \lfloor \log_2 n \rfloor\) et numérotons les sommets \(1, 2, \ldots, n\). On attribue au sommet \(i\) la couleur \(\min(\lfloor \log_2 i \rfloor + 1, k)\) (les premiers sommets ont donc les couleurs \(1, 2, 2, 3, 3, 3, 3, 4, \ldots\) et les \(n - 2^{k-1} + 1\) derniers ont la couleur \(k\)), et pour \(1 \leq i < j \leq n\) on colorie l'arête \(ij\) avec la couleur du sommet \(i\). Ce coloriage est bon.

Preuve. Le nombre de sommets de couleur \(k\) est \(n - 2^{k-1} + 1\) ; comme \(n \geq 2^k\),

\[n - 2^{k-1} + 1 \geq \frac{n}{2} + 1.\]

Donc dans tout chemin hamiltonien, deux sommets de couleur \(k\) sont voisins, et l'arête qui les relie a la couleur \(k\).

Soit maintenant \(1 \leq i < k\) et supposons qu'un chemin hamiltonien ne contienne aucune arête de couleur \(i\). Une arête issue d'un sommet de couleur \(i\) vers un sommet de couleur \(\geq i\) a la couleur \(i\) ; donc, dans ce chemin, les sommets de couleur \(i\) ne sont voisins que de sommets de couleur \(< i\). Comme il y a \(2^{i-1}\) sommets de couleur \(i\) et \(2^{i-1} - 1\) sommets de couleur \(< i\), le chemin est nécessairement de la forme

\[(i) \leftrightarrow ({<}\,i) \leftrightarrow (i) \leftrightarrow ({<}\,i) \leftrightarrow \cdots \leftrightarrow ({<}\,i) \leftrightarrow (i),\]

où \((i)\) désigne un sommet de couleur \(i\) et \(({<}\,i)\) un sommet de couleur \(< i\). C'est impossible, car ce chemin ne contiendrait aucun sommet de couleur \(> i\). \(\square\)

Majoration. Fixons \(k\) couleurs et supposons qu'il existe un bon coloriage de \(K_n\) ; montrons que \(k \leq \lfloor \log_2 n \rfloor\). Pour \(n = 2\) c'est trivial ; supposons \(n \geq 3\). Pour un sommet \(v\) et \(1 \leq i \leq k\), notons \(d_i(v)\) le nombre d'arêtes de couleur \(i\) issues de \(v\).

Lemme 1. Dans un bon coloriage, soit \(AB\) une arête de couleur \(i\). Si \(d_i(A) + d_i(B) \leq n - 1\), le coloriage reste bon quand on recolorie \(AB\) avec n'importe quelle autre couleur.

Preuve. Supposons que le recoloriage de \(AB\) rende le coloriage mauvais. Le problème vient forcément de la couleur \(i\) : il existe un chemin hamiltonien contenant \(AB\) dans lequel, avant recoloriage, \(AB\) est la seule arête de couleur \(i\). Avec \(A = A_0\), \(B = B_0\), écrivons ce chemin

\[A_s \leftrightarrow A_{s-1} \leftrightarrow \cdots \leftrightarrow A_1 \leftrightarrow A_0 \leftrightarrow B_0 \leftrightarrow B_1 \leftrightarrow \cdots \leftrightarrow B_{t-1} \leftrightarrow B_t,\]

où \(s, t \geq 0\) et \(s + t + 2 = n\). Dans le coloriage initial :

  • l'arête \(B_0 A_s\) est de couleur \(i\), sinon le chemin \(A_0 \leftrightarrow A_1 \leftrightarrow \cdots \leftrightarrow A_s \leftrightarrow B_0 \leftrightarrow B_1 \leftrightarrow \cdots \leftrightarrow B_t\) n'aurait aucune arête de couleur \(i\) ;
  • de même, l'arête \(A_0 B_t\) est de couleur \(i\) ;

  • pour chaque \(0 \leq p < s\), l'une au moins des arêtes \(B_0 A_p\) et \(A_0 A_{p+1}\) est de couleur \(i\), sinon le chemin

    \[A_s \leftrightarrow \cdots \leftrightarrow A_{p+2} \leftrightarrow A_{p+1} \leftrightarrow A_0 \leftrightarrow A_1 \leftrightarrow \cdots \leftrightarrow A_{p-1} \leftrightarrow A_p \leftrightarrow B_0 \leftrightarrow B_1 \leftrightarrow \cdots \leftrightarrow B_t\]

    n'aurait aucune arête de couleur \(i\) ;

  • de même, pour chaque \(0 \leq q < t\), l'une au moins des arêtes \(A_0 B_q\) et \(B_0 B_{q+1}\) est de couleur \(i\).

Dans cette liste, chaque arête \(A_0 X\) apparaît exactement une fois, ainsi que chaque arête \(B_0 X\) (\(A_0 B_0\) et \(B_0 A_0\) étant comptées séparément). En additionnant les contributions à \(d_i(A) + d_i(B)\), on obtient

\[d_i(A) + d_i(B) \geq (s + 1) + (t + 1) = n,\]

ce qui contredit l'hypothèse \(d_i(A) + d_i(B) \leq n - 1\). \(\square\)

On va recolorier répétitivement grâce au lemme 1 jusqu'à obtenir une structure simple. Pour un sommet \(v\), notons \(m(v)\) la plus grande valeur de \(d_i(v)\) sur toutes les couleurs \(i\).

Lemme 2. Dans un bon coloriage, soit \(A\), \(B\) deux sommets distincts et \(j\) la couleur de \(AB\). Si \(m(A) \geq m(B)\) et \(m(A) = d_i(A)\) pour une couleur \(i \neq j\), alors le coloriage reste bon quand on recolorie \(AB\) avec la couleur \(i\).

Preuve. On a \(d_j(A) + d_j(B) \leq (n - 1 - m(A)) + m(B) \leq n - 1\), et l'on applique le lemme 1. \(\square\)

Lemme 3. Dans un bon coloriage, soit \(S\) un ensemble non vide de sommets, \(A \in S\) tel que \(m(A) \geq m(B)\) pour tout \(B \in S\) (principe extrémal), et \(i\) une couleur telle que \(d_i(A) = m(A)\). Alors après avoir recolorié avec la couleur \(i\) toutes les arêtes \(AB\), \(B \in S \setminus \{A\}\), le coloriage reste bon.

Preuve. On répète l'opération suivante tant que toutes les arêtes \(AB\) (\(B \in S\)) ne sont pas de couleur \(i\) : choisir une arête \(AB\) avec \(B \in S\) qui n'est pas de couleur \(i\) et la recolorier avec la couleur \(i\). D'après le lemme 2, le coloriage reste bon après chaque opération. De plus, \(m(A)\) augmente de \(1\) à chaque opération, et chaque autre \(m(B)\) augmente d'au plus \(1\) ; donc \(m(A)\) reste maximal parmi les \(m(B)\), \(B \in S\). On a aussi toujours \(d_i(A) = m(A)\), les deux membres augmentant de \(1\). On peut donc répéter l'opération, et le coloriage reste bon. \(\square\)

On applique le lemme 3 à l'ensemble des \(n\) sommets : il existe alors un sommet \(A_1\) dont toutes les arêtes ont une même couleur \(c_1\). On l'applique ensuite à l'ensemble des sommets autres que \(A_1\), et ainsi de suite. On aboutit à la configuration suivante :

  • les \(n\) sommets sont numérotés \(A_1, A_2, \ldots, A_n\) ;
  • au sommet \(A_i\) correspond une couleur \(c_i\) (par convention, on dit que \(A_i\) a la couleur \(c_i\)) ;
  • pour \(1 \leq u < v \leq n\), l'arête \(A_u A_v\) a la couleur \(c_u\) ;
  • ce coloriage est bon.

Affirmation 2. Pour toute couleur \(i\), il existe \(1 \leq p \leq n\) tel que plus de \(p/2\) des sommets \(A_1, \ldots, A_p\) soient de couleur \(i\).

Preuve. Supposons au contraire que pour tout \(1 \leq p \leq n\), au plus \(\lfloor p/2 \rfloor\) des sommets \(A_1, \ldots, A_p\) soient de couleur \(i\) ; construisons un chemin hamiltonien sans arête de couleur \(i\). Soit \(A_{x_1}, \ldots, A_{x_t}\) (\(x_1 < \cdots < x_t\)) les sommets de couleur \(i\) et \(A_{y_1}, \ldots, A_{y_s}\) (\(y_1 < \cdots < y_s\)) les autres. On a \(s + t = n\) et \(t \leq \lfloor n/2 \rfloor\), donc \(t \leq s\). De plus \(y_j < x_j\) pour tout \(1 \leq j \leq t\), sinon \(A_1, \ldots, A_{x_j}\) contiendraient \(j\) sommets de couleur \(i\) et moins de \(j\) sommets d'une autre couleur. Le chemin hamiltonien

\[A_{x_1} \leftrightarrow A_{y_1} \leftrightarrow A_{x_2} \leftrightarrow A_{y_2} \leftrightarrow A_{x_3} \leftrightarrow \cdots \leftrightarrow A_{x_t} \leftrightarrow A_{y_t} \leftrightarrow A_{y_{t+1}} \leftrightarrow \cdots \leftrightarrow A_{y_s}\]

ne contient alors aucune arête de couleur \(i\) (chaque arête a la couleur de son extrémité d'indice le plus petit, qui est un \(A_{y_j}\)). Contradiction. \(\square\)

Ainsi, pour chaque couleur \(i\), il existe un entier \(1 \leq p_i \leq n\) tel que plus de \(p_i/2\) des sommets \(A_1, \ldots, A_{p_i}\) soient de couleur \(i\). Choisissons le plus petit tel \(p_i\) pour chaque \(i\), et supposons sans perte de généralité

\[p_1 < p_2 < \cdots < p_k\]

(les inégalités sont strictes : deux couleurs ne peuvent pas être toutes deux majoritaires dans le même préfixe). Parmi \(A_1, \ldots, A_{p_i}\), il y a au moins \(\lceil (p_j + 1)/2 \rceil\) sommets de couleur \(j\) pour tout \(1 \leq j \leq i\). Donc

\[p_i \geq \left\lceil \frac{p_1 + 1}{2} \right\rceil + \left\lceil \frac{p_2 + 1}{2} \right\rceil + \cdots + \left\lceil \frac{p_i + 1}{2} \right\rceil.\]

On en déduit par récurrence que \(p_i \geq 2^i - 1\) pour tout \(1 \leq i \leq k\), ce qui donne déjà \(n \geq 2^k - 1\).

Il reste à exclure \(n = 2^k - 1\). Dans ce cas, toutes les inégalités sont des égalités : \(p_i = 2^i - 1\) et il y a exactement \(2^{i-1}\) sommets de couleur \(i\). De plus, aucun sommet de couleur \(i\) ne figure parmi \(A_1, \ldots, A_{p_{i-1}}\), donc les sommets de couleur \(i\) sont exactement

\[A_{2^{i-1}}, A_{2^{i-1}+1}, \ldots, A_{2^i - 1}.\]

On forme alors le chemin hamiltonien

\[A_{2^{k-1}} \leftrightarrow A_1 \leftrightarrow A_{2^{k-1}+1} \leftrightarrow A_2 \leftrightarrow A_{2^{k-1}+2} \leftrightarrow A_3 \leftrightarrow \cdots \leftrightarrow A_n,\]

qui ne contient aucune arête de couleur \(k\). C'est une contradiction, donc \(n \geq 2^k\), c'est-à-dire \(k \leq \lfloor \log_2 n \rfloor\). \(\blacksquare\)