Shortlist 2013, C6¶
Domaine : Combinatoire · Difficulté : ★★★★☆ · Proposé par : Russia
Concepts : Graphes : degrés, chemins, arbres · Principe extrémal · Principe des tiroirs
Solution officielle : Shortlist officielle 2013 (avec solutions), p. 31 (page 31 du PDF)
Énoncé¶
In some country several pairs of cities are connected by direct two-way flights. It is possible to go from any city to any other by a sequence of flights. The distance between two cities is defined to be the least possible number of flights required to go from one of them to the other. It is known that for any city there are at most \(100\) cities at distance exactly three from it. Prove that there is no city such that more than \(2550\) other cities have distance exactly four from it.
Indices : les idées clés
- Graphes et distances : \(S_i(a)\) est l'ensemble des villes à distance exactement \(i\) de \(a\) ; on suppose \(\lvert S_4(x) \rvert \geq 2551\).
- Principe extrémal : on prend une partie « substantielle » \(A^*\) de \(S_1(x)\) de cardinal minimal \(m\) ; chaque \(y \in A^*\) a une ville \(d_y\) qu'on ne peut atteindre en quatre vols qu'en passant par \(y\).
- Tiroirs : comme \(m(101 - m) \leq 2550\), une ville \(a \in A^*\) a au moins \(102 - m\) villes de \(D\) à distance \(3\), donc au plus \(m - 2\) autres ; or les chemins vers les \(d_y\) en fournissent \(m - 1\).
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2013 (une solution et trois remarques).
Solution¶
Notons \(d(a, b)\) la distance entre les villes \(a\) et \(b\), et
l'ensemble des villes à distance exactement \(i\) de la ville \(a\).
Supposons que, pour une ville \(x\), l'ensemble \(D = S_4(x)\) ait au moins \(2551\) éléments. Soit \(A = S_1(x)\). Une partie \(A'\) de \(A\) est dite substantielle si toute ville de \(D\) peut être atteinte depuis \(x\) en quatre vols en passant par un élément de \(A'\) ; autrement dit, toute ville de \(D\) est à distance \(3\) d'un élément de \(A'\), c'est-à-dire \(D \subseteq \bigcup_{a \in A'} S_3(a)\). Par exemple, \(A\) lui-même est substantiel. Fixons une partie substantielle \(A^*\) de \(A\) de cardinal minimal \(m = \lvert A^* \rvert\).
Comme
il existe une ville \(a \in A^*\) telle que \(\lvert S_3(a) \cap D \rvert \geq 102 - m\). Comme \(\lvert S_3(a) \rvert \leq 100\), l'ensemble \(S_3(a)\) contient au plus \(100 - (102 - m) = m - 2\) villes \(c\) avec \(d(c, x) \leq 3\). Notons \(T = \{c \in S_3(a) : d(x, c) \leq 3\}\) l'ensemble de ces villes ; ainsi \(\lvert T \rvert \leq m - 2\). Pour obtenir une contradiction, on va construire \(m - 1\) éléments distincts de \(T\), correspondant aux \(m - 1\) éléments de l'ensemble \(A_a = A^* \setminus \{a\}\).
D'abord, par minimalité de \(A^*\), pour chaque \(y \in A_a\), il existe une ville \(d_y \in D\) qu'on ne peut atteindre en quatre vols depuis \(x\) qu'en passant par \(y\). Il existe donc un trajet \(x - y - b_y - c_y - d_y\) de \(x\) à \(d_y\), pour certaines villes \(b_y\) et \(c_y\) ; on a \(d(x, b_y) = 2\) et \(d(x, c_y) = 3\), car ce trajet est de longueur minimale.
Montrons que les \(2(m - 1)\) villes de la forme \(b_y\), \(c_y\) avec \(y \in A_a\) sont distinctes. Aucun \(b_y\) ne peut coïncider avec un \(c_z\), car leurs distances à \(x\) sont différentes. D'autre part, si \(b_y = b_z\) pour \(y \neq z\), il existerait un trajet de longueur \(4\) de \(x\) à \(d_z\) passant par \(y\), à savoir \(x - y - b_z - c_z - d_z\) ; c'est impossible par le choix de \(d_z\). De même, \(c_y \neq c_z\) pour \(y \neq z\).
Il suffit donc de prouver que, pour tout \(y \in A_a\), l'une des villes \(b_y\), \(c_y\) est à distance \(3\) de \(a\) (et appartient donc à \(T\)). Pour cela, on remarque que \(d(a, y) \leq 2\) grâce au trajet \(a - x - y\), tandis que \(d(a, d_y) \geq d(x, d_y) - d(x, a) = 3\). De plus, \(d(a, d_y) \neq 3\) par le choix de \(d_y\) ; donc \(d(a, d_y) > 3\). Enfin, dans la suite \(d(a, y)\), \(d(a, b_y)\), \(d(a, c_y)\), \(d(a, d_y)\), deux termes voisins diffèrent d'au plus \(1\), le premier terme est inférieur à \(3\) et le dernier supérieur à \(3\) ; l'un d'eux vaut donc \(3\), comme voulu. \(\blacksquare\)
Remarques¶
Remarque 1. La borne \(2550\) est optimale, comme le montrent divers exemples. En voici un, l'« Empire romain » : une capitale, appelée « Rome », est reliée à \(51\) villes secondaires par des chemins de longueur \(3\) deux à deux disjoints (hors Rome). De plus, chacune de ces villes secondaires est reliée par vol direct à \(50\) villes rurales.
Remarque 2. Sous les hypothèses du problème, il n'y a aucune borne sur la taille de \(S_1(x)\) ou de \(S_2(x)\).
Remarque 3. On peut remplacer les nombres \(100\) et \(2550\) de l'énoncé par \(n\) et \(\left\lfloor \frac{(n + 1)^2}{4} \right\rfloor\), pour tout entier \(n \geq 1\). Plus généralement encore, on peut remplacer le couple de distances \((3, 4)\) par tout couple \((r, s)\) d'entiers strictement positifs tel que \(r < s \leq \frac{3}{2}r\).
Pour adapter la preuve, on prend \(A = S_{s-r}(x)\) et l'on définit la notion de partie substantielle comme ci-dessus. On prend une partie substantielle minimale \(A^*\) de \(A\), et pour chaque \(y \in A^*\), on fixe un élément \(d_y \in S_s(x)\) qu'on ne peut atteindre depuis \(x\) par un chemin de longueur \(s\) qu'en passant par \(y\). Comme ci-dessus, il suffit de montrer que, pour \(a, y \in A^*\) distincts et un chemin \(y = y_0 - y_1 - \cdots - y_r = d_y\), l'une des villes \(y_0, \ldots, y_{r-1}\) est à distance \(r\) de \(a\). On le fait comme ci-dessus ; la relation \(s \leq \frac{3}{2}r\) sert à montrer que \(d(a, y_0) \leq r\).
De plus, l'estimation \(\left\lfloor \frac{(n + 1)^2}{4} \right\rfloor\) est aussi optimale pour tout entier \(n \geq 1\) et tous entiers \(r, s\) avec \(r < s \leq \frac{3}{2}r\), comme le montre un exemple analogue à celui de la remarque précédente.