Aller au contenu

Shortlist 2019, C8

Domaine : Combinatoire · Difficulté : ★★★★☆ · Proposé par : Thailand

Concepts : Graphes : degrés, chemins, arbres

Solution officielle : Shortlist officielle 2019 (avec solutions), section C8 (livret PDF)

Énoncé

Alice has a map of Wonderland, a country consisting of \(n \geq 2\) towns. For every pair of towns, there is a narrow road going from one town to the other. One day, all the roads are declared to be "one way" only. Alice has no information on the direction of the roads, but the King of Hearts has offered to help her. She is allowed to ask him a number of questions. For each question in turn, Alice chooses a pair of towns and the King of Hearts tells her the direction of the road connecting those two towns.

Alice wants to know whether there is at least one town in Wonderland with at most one outgoing road. Prove that she can always find out by asking at most \(4n\) questions.

Indices : les idées clés
  • Graphes : un tournoi ; les routes dont Alice connaît le sens forment d'abord un arbre, puis une forêt sur l'ensemble \(S\) des villes encore « suspectes ».
  • Élimination type « tournoi à élimination » (phase 2) : en \(n - 1\) questions, toutes les villes sauf une ont une route sortante connue.
  • Ensemble de candidats qui rétrécit : chaque question entre deux villes de \(S\) ayant déjà une route sortante connue élimine l'une des deux ; il reste au plus \(2\) candidats, que l'on vérifie entièrement.
Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2019 (une solution et quatre remarques).

Solution

Montrons qu'Alice a besoin d'au plus \(4n - 7\) questions (pour \(n \geq 2\), on a \(4n - 7 \leq 4n\)). Sa stratégie comporte plusieurs phases. Dans la suite, \(S\) désigne l'ensemble des villes dont Alice ne sait pas encore qu'elles ont plus d'une route sortante (au départ, \(|S| = n\)).

Phase 1. Alice choisit deux villes quelconques \(A\) et \(B\). Sans perte de généralité, le Roi répond que la route va de \(A\) à \(B\). À la fin de cette phase, Alice a posé \(1\) question.

Phase 2. Pendant cette phase, il y a une ville (variable) \(T\) dont on sait qu'elle a au moins une route entrante, mais dont on ne connaît encore aucune route sortante. Au départ, \(T = B\). Alice répète \(n - 2\) fois : elle choisit une ville \(X\) dont elle n'a encore jamais parlé et demande le sens de la route entre \(T\) et \(X\). Si la route va de \(X\) à \(T\), \(T\) ne change pas ; si elle va de \(T\) à \(X\), \(X\) devient la nouvelle ville \(T\), puisqu'on sait maintenant que l'ancienne \(T\) a une route sortante.

À la fin de cette phase, Alice a posé \(n - 1\) questions au total. On ne connaît encore aucune route sortante de la ville finale \(T\), tandis que chaque autre ville a exactement une route sortante connue. Le graphe non orienté des routes de sens connu est un arbre.

Phase 3. Alice demande le sens de toutes les routes entre \(T\) et une autre ville dont elle n'a pas encore demandé la route avec \(T\), en s'arrêtant si elle trouve deux routes sortantes de \(T\). Cette phase comporte au plus \(n - 2\) questions. Si elle ne trouve pas deux routes sortantes de \(T\), elle a répondu à sa question (\(T\) a au plus une route sortante) avec au plus \(2n - 3 \leq 4n - 7\) questions. On suppose donc dans la suite qu'elle en trouve deux, après \(k\) questions dans cette phase, avec \(2 \leq k \leq n - 2\) (donc \(n \geq 4\) dans la suite).

Pour chaque question où la route va vers \(T\), la ville à l'autre bout est retirée de \(S\) (elle avait déjà une route sortante connue), et la dernière question fait retirer \(T\) de \(S\). À la fin de cette phase, \(|S| = n - k + 1\), et \(n + k - 1\) questions ont été posées au total. De plus, le graphe non orienté des routes de sens connu à l'intérieur de \(S\) ne contient aucun cycle (\(T\) n'est plus dans \(S\), toutes les questions de cette phase concernaient \(T\), et le graphe était un arbre avant cette phase). Chaque ville de \(S\) a exactement une route sortante connue (pas forcément vers une ville de \(S\)).

Phase 4. Alice choisit à plusieurs reprises deux villes de \(S\) dont elle ne connaît pas la route qui les relie. Comme chaque ville de \(S\) a exactement une route sortante connue, la réponse fait toujours sortir l'une des deux villes de \(S\) (celle d'où part la route en a maintenant deux). Comme le graphe des routes de sens connu à l'intérieur de \(S\) n'a pas de cycle, on peut continuer tant qu'il reste au moins \(3\) villes dans \(S\) (un graphe sans cycle à au moins \(3\) sommets n'est pas complet).

Si la phase se termine avec \(t\) villes dans \(S\) (\(t \in \{1, 2\}\)), elle a utilisé \(n - k + 1 - t\) questions, soit \(2n - t\) questions au total.

Phase 5. Alice demande le sens de toutes les routes partant des villes restantes de \(S\) qu'elle ne connaît pas encore. Elle connaît déjà la route entre ces villes (si \(t = 2\)). Elle a aussi forcément déjà demandé, pendant les deux premières phases, au moins une autre route touchant l'une de ces villes (ces phases ont produit un arbre à \(n > 2\) sommets). Elle pose donc au plus \(t(n - t) - 1\) questions dans cette phase.

À la fin, Alice sait si une ville a au plus une route sortante (les seules candidates sont les villes de \(S\), dont elle connaît maintenant toutes les routes). Si \(t = 1\), il a fallu au plus \((2n - 1) + (n - 2) = 3n - 3 \leq 4n - 7\) questions ; si \(t = 2\), au plus \((2n - 2) + (2n - 5) = 4n - 7\) questions. \(\blacksquare\)

Remarques

Remarque 1. Le problème pourrait être posé avec un barème explicite donnant des points pour des bornes plus faibles \(cn\) avec \(c > 4\), dans le style du problème 6 de l'OIM 2014.

Remarque 2. La version proposée à l'origine demandait seulement une borne \(5n\), bien plus simple à prouver. Le comité a préféré une version avec une constante asymptotiquement optimale ; la remarque suivante montre que la constante \(4\) est optimale.

Remarque 3 (borne inférieure). Pour \(n \geq 8\), Alice ne peut pas toujours conclure avec au plus \(4n - 3\log_2 n - 15\) questions. Le Roi choisit les sens au fur et à mesure (en répétant sa réponse si une route est redemandée), de façon à rester compatible le plus longtemps possible avec les deux réponses possibles.

  • Phase 1. On regarde le graphe non orienté des arêtes de sens connu ; la phase s'arrête quand il reste exactement \(8\) composantes connexes qui sont des arbres. Invariant : dans une composante-arbre à \(k\) sommets, chaque sommet a au plus \(\lfloor \log_2 k \rfloor\) arêtes entrantes. Pour une arête interne à une composante, ou entre deux composantes dont l'une n'est pas un arbre, le Roi répond arbitrairement. Pour une arête entre deux composantes-arbres \(A\) et \(B\) à \(a \geq b\) sommets, il l'oriente de \(A\) vers \(B\) ; le nouveau nombre d'arêtes entrantes en un sommet est au plus \(\max(\lfloor \log_2 a \rfloor, \lfloor \log_2 b \rfloor + 1) \leq \lfloor \log_2(a+b) \rfloor\). Le nombre de composantes-arbres reste constant ou baisse de \(1\) ; la phase se termine donc, après au moins \(n - 8\) questions. Chaque composante-arbre contient un sommet sans arête sortante ; on en colorie un en rouge dans chacune.
  • Phase 2. Soient \(V_1, V_2, V_3\) les sommets rouges des trois plus petites composantes (qui ont ensemble au plus \(\lfloor 3n/8 \rfloor\) sommets, chacune au plus \(\lfloor 3n/8 - 2 \rfloor\)). Soient \(C_1, C_2, \ldots\) les composantes connexes obtenues en retirant les \(V_j\) ; il n'y a aucune arête de sens connu entre \(C_i\) et \(C_j\) pour \(i \neq j\), et il y a au moins cinq telles composantes. À l'intérieur d'un \(C_i\), le Roi répond arbitrairement ; entre \(C_i\) et \(C_j\), il oriente toutes les arêtes de \(C_i\) vers \(C_{i+1}\) et \(C_{i+2}\) (indices modulo le nombre de composantes) et arbitrairement pour les autres paires : tous les sommets autres que les \(V_j\) auront plus d'une arête sortante. Entre deux \(V_j\), il oriente \(V_1 \to V_2 \to V_3 \to V_1\). Entre \(V_j\) et un autre sommet, il oriente toujours l'arête vers \(V_j\), sauf pour la dernière question posée concernant ce \(V_j\), où il l'oriente en sortant de \(V_j\). Tant qu'un des \(V_j\) n'a pas eu toutes ses arêtes vers les autres sommets demandées, les réponses restent compatibles avec « tous les sommets ont plus d'une arête sortante » et avec « ce \(V_j\) n'a qu'une arête sortante ».

Au début de la phase 2, chaque \(V_j\) a au plus \(\lfloor \log_2 \lfloor 3n/8 - 2 \rfloor \rfloor < \log_2 n - 1\) arêtes entrantes. Alice ne peut donc pas conclure en au plus \(3\big(n - 3 - (\log_2 n - 1)\big) - 1\) questions dans cette phase, soit \(4n - 3\log_2 n - 15\) questions au total.

Remarque 4 (meilleure borne supérieure). On peut améliorer la borne en \(4n - 2\log_2 n + 1\). (On ne sait pas où se situe le minimum exact entre \(4n - 3\log_2 n + O(1)\) et \(4n - 2\log_2 n + O(1)\).) Supposons \(n \geq 5\). On remplace les phases 1 et 2 par une stratégie qui produit aussi un arbre couvrant où un sommet \(V\) n'a aucune arête sortante connue et tous les autres en ont exactement une, mais en contrôlant mieux les arêtes entrantes. On définit des arbres \(T_m\) à \(2^m\) sommets : \(T_0\) est un sommet, et \(T_m\) s'obtient en reliant par une arête les racines de deux copies de \(T_{m-1}\) (la racine est l'unique sommet sans arête sortante). Si \(n = 2^m\), on obtient \(T_m\) en \(n - 1\) questions : \(2^{m-1}\) paires disjointes, puis \(2^{m-2}\) paires de racines des \(T_1\) obtenus, etc. Sinon, après \(k\) étapes on a \(\lfloor n/2^k \rfloor\) arbres semblables à \(T_k\) (avec éventuellement des sommets en plus, mais une racine unique) ; s'il y en a un nombre pair, on apparie leurs racines ; s'il y en a un nombre impair (\(> 1\)), on apparie la racine du \(T_k\) restant avec celle d'un des \(T_{k+1}\). Avec \(m = \lfloor \log_2 n \rfloor\), on obtient un unique \(T_m\) (avec éventuellement des sommets en plus) de racine \(V\), qui a au moins \(m\) arêtes entrantes, provenant de sommets \(V_0, \ldots, V_{m-1}\) où \(V_i\) a au moins \(i\) arêtes entrantes.

On partage les sommets autres que \(V\) en \(A\) (distance impaire à \(V\)) et \(B\) (distance paire à \(V\)). (Le livret écrit « distance paire à \(B\) » ; il faut lire \(V\).) Les deux sont non vides ; \(A\) contient les \(V_i\), et \(B\) contient des sommets ayant au moins \(0, 1, \ldots, m - 2\) arêtes entrantes. Il n'y a aucune arête de sens connu à l'intérieur de \(A\) ni de \(B\). En phase 3, on demande les arêtes entre \(V\) et les autres sommets : d'abord ceux de \(B\), puis ceux de \(A\), chaque fois par nombre croissant d'arêtes entrantes ; cela fait au plus \(n - 1 - m\) questions. Si on ne trouve pas deux arêtes sortantes de \(V\), on a posé au plus \(2n - 2 - m \leq 4n - 2\log_2 n + 1\) questions ; sinon, \(S\) est comme dans la solution et contient encore les \(V_i\). En phase 4, on traite les sommets restant dans \(B\) par nombre croissant d'arêtes entrantes : si \(s\) est le plus petit nombre d'arêtes entrantes d'un tel sommet, pour tout \(s \leq t \leq m - 2\) il y a au moins \(m - t - 2\) sommets avec plus de \(t\) arêtes entrantes ; en demandant toujours la paire de sommets de \(B\) ayant le moins d'arêtes entrantes, il reste un seul sommet (si \(B\) n'était pas vidé) avec au moins \(m - 2\) arêtes entrantes. De même avec \(A\) (non vide), il reste un sommet avec au moins \(m - 1\) arêtes entrantes. Si seul \(A\) est non vide, la phase 5 demande au plus \(n - m\) questions, soit au plus \(3n - m - 1\) au total ; si les deux sont non vides, la phase 5 demande au plus \(2n - 2m + 1\) questions, soit au plus \(4n - 2m - 1 < 4n - 2\log_2 n + 1\) au total.