Shortlist 2006, C5¶
Domaine : Combinatoire · Difficulté : ★★★☆☆ · Proposé par : Argentina
Concepts : Graphes : degrés, chemins, arbres · Récurrence et constructions récursives
Solution officielle : Shortlist officielle 2006 (avec solutions), p. 27 (page 28 du PDF)
Énoncé¶
An \((n, k)\)-tournament is a contest with \(n\) players held in \(k\) rounds such that:
(i) Each player plays in each round, and every two players meet at most once.
(ii) If player \(A\) meets player \(B\) in round \(i\), player \(C\) meets player \(D\) in round \(i\), and player \(A\) meets player \(C\) in round \(j\), then player \(B\) meets player \(D\) in round \(j\).
Determine all pairs \((n, k)\) for which there exists an \((n, k)\)-tournament.
Indices : les idées clés
- Réponse : avec \(t_k\) défini par \(2^{t_k - 1} < k + 1 \leq 2^{t_k}\), un tournoi existe si et seulement si \(2^{t_k} \mid n\).
- Construction : les joueurs sont les suites de \(\{0, 1\}^t\), et au tour \(i\) le joueur \(\alpha\) rencontre \(\alpha + \omega(i)\) (addition modulo \(2\), \(\omega(i)\) écriture binaire de \(i\)).
- Composantes : la composante d'un joueur dans le graphe des \(i\) premiers tours double ou reste la même à chaque tour ; elle a donc une taille \(2^u \geq k + 1\).
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2006 (une solution).
Réponse : en notant \(t_k\) l'unique entier tel que \(2^{t_k - 1} < k + 1 \leq 2^{t_k}\), un \((n, k)\)-tournoi existe si et seulement si \(2^{t_k}\) divise \(n\).
Solution¶
Montrons d'abord que si \(n = 2^t\) pour un certain \(t\), il existe un \((n, k)\)-tournoi pour tout \(k \leq 2^t - 1\). Soit \(S\) l'ensemble des suites de \(0\) et de \(1\) de longueur \(t\). On étiquette les \(2^t\) joueurs par les éléments de \(S\) de façon arbitraire (c'est possible puisqu'il y a exactement \(2^t\) suites dans \(S\)). Dans la construction ci-dessous, on identifie les joueurs à leurs étiquettes. Si \(\alpha, \beta \in S\), soit \(\alpha + \beta \in S\) le résultat de l'addition terme à terme modulo \(2\) de \(\alpha\) et \(\beta\) (avec les règles \(0 + 0 = 0\), \(0 + 1 = 1 + 0 = 1\), \(1 + 1 = 0\) ; il n'y a pas de retenue). Pour tout \(i = 1, \ldots, 2^t - 1\), soit \(\omega(i) \in S\) la suite des chiffres de \(i\) en base \(2\), complétée par des zéros en tête si nécessaire pour atteindre la longueur \(t\).
Définissons maintenant un tournoi à \(n = 2^t\) joueurs en \(k \leq 2^t - 1\) tours ainsi : pour tout \(i = 1, \ldots, k\), le joueur \(\alpha\) rencontre le joueur \(\alpha + \omega(i)\) au tour \(i\). Le tournoi est bien défini, car \(\alpha + \omega(i) \in S\) et \(\alpha + \omega(i) = \beta + \omega(i)\) implique \(\alpha = \beta\) ; de plus, \([\alpha + \omega(i)] + \omega(i) = \alpha\) pour tout \(\alpha \in S\) (le joueur \(\alpha + \omega(i)\) rencontre donc bien le joueur \(\alpha\) au tour \(i\)). Chaque joueur joue à chaque tour. Ensuite, deux joueurs se rencontrent au plus une fois (exactement une fois si \(k = 2^t - 1\)), puisque \(\omega(i) \neq \omega(j)\) si \(i \neq j\). La condition (i) est donc vérifiée, et la condition (ii) se vérifie aussi facilement.
Supposons que le joueur \(\alpha\) rencontre le joueur \(\beta\) au tour \(i\), que le joueur \(\gamma\) rencontre le joueur \(\delta\) au tour \(i\), et que le joueur \(\alpha\) rencontre le joueur \(\gamma\) au tour \(j\). Alors \(\beta = \alpha + \omega(i)\), \(\delta = \gamma + \omega(i)\) et \(\gamma = \alpha + \omega(j)\). Par définition, au tour \(j\), \(\beta\) jouera contre
comme le demande (ii).
Il existe donc un \((n, k)\)-tournoi pour les couples \((n, k)\) tels que \(n = 2^t\) et \(k \leq 2^t - 1\). La même conclusion est immédiate pour \(n\) de la forme \(n = 2^ts\) et \(k \leq 2^t - 1\). En effet, considérons \(s\) tournois \((2^t, k)\) différents \(T_1, \ldots, T_s\), sans joueurs communs deux à deux. Leur réunion peut être vue comme un \((2^ts, k)\)-tournoi \(T\) dont chaque tour est la réunion des tours correspondants de \(T_1, \ldots, T_s\).
En résumé, la condition « \(2^{t_k}\) divise \(n\) » est suffisante pour qu'un \((n, k)\)-tournoi existe. Montrons qu'elle est aussi nécessaire.
Considérons un \((n, k)\)-tournoi quelconque. Représentons chaque joueur par un point et, après chaque tour, relions par une arête chaque paire de joueurs qui se sont rencontrés à ce tour. À chaque tour \(i = 1, \ldots, k\) correspond ainsi un graphe \(G_i\). On dit que le joueur \(Q\) est un \(i\)-voisin du joueur \(P\) s'il existe un chemin d'arêtes de \(G_i\) de \(P\) à \(Q\) ; autrement dit, s'il existe des joueurs \(P = X_1, X_2, \ldots, X_m = Q\) tels que le joueur \(X_j\) rencontre le joueur \(X_{j+1}\) lors de l'un des \(i\) premiers tours, \(j = 1, 2, \ldots, m - 1\). L'ensemble des \(i\)-voisins d'un joueur s'appelle sa \(i\)-composante. Évidemment, deux \(i\)-composantes sont soit disjointes, soit confondues.
Après chaque tour \(i\), l'ensemble des joueurs est donc partitionné en \(i\)-composantes deux à deux disjointes. Pour atteindre notre but, il suffit de montrer que toutes les \(k\)-composantes ont une taille divisible par \(2^{t_k}\).
Pour cela, voyons comment évolue la \(i\)-composante \(\Gamma\) d'un joueur \(A\) après le tour \(i + 1\). Supposons que \(A\) rencontre au tour \(i + 1\) un joueur \(B\) de \(i\)-composante \(\Delta\) (les composantes \(\Gamma\) et \(\Delta\) ne sont pas forcément distinctes). Montrons qu'alors, au tour \(i + 1\), chaque joueur de \(\Gamma\) rencontre un joueur de \(\Delta\), et inversement.
En effet, soit \(C\) un joueur quelconque de \(\Gamma\), et supposons que \(C\) rencontre \(D\) au tour \(i + 1\). Comme \(C\) est un \(i\)-voisin de \(A\), il existe une suite de joueurs \(A = X_1, X_2, \ldots, X_m = C\) telle que \(X_j\) rencontre \(X_{j+1}\) lors de l'un des \(i\) premiers tours, \(j = 1, 2, \ldots, m - 1\). Supposons que \(X_j\) rencontre \(Y_j\) au tour \(i + 1\), pour \(j = 1, 2, \ldots, m\) ; en particulier, \(Y_1 = B\) et \(Y_m = D\). Les joueurs \(Y_j\) existent vu la condition (i). Supposons que \(X_j\) et \(X_{j+1}\) se soient rencontrés au tour \(r\), avec \(r \leq i\). La condition (ii) implique alors que \(Y_j\) et \(Y_{j+1}\) se sont aussi rencontrés au tour \(r\). Donc \(B = Y_1, Y_2, \ldots, Y_m = D\) est un chemin de \(G_i\) de \(B\) à \(D\). Autrement dit, \(D\) est dans la \(i\)-composante \(\Delta\) de \(B\), comme annoncé. Par symétrie, chaque joueur de \(\Delta\) rencontre un joueur de \(\Gamma\) au tour \(i + 1\). Il s'ensuit en particulier que \(\Gamma\) et \(\Delta\) ont le même cardinal.
Il est alors immédiat que la \((i + 1)\)-composante de \(A\) est \(\Gamma \cup \Delta\), réunion de deux ensembles de même taille. Comme \(\Gamma\) et \(\Delta\) sont soit disjoints, soit confondus, on a \(\lvert \Gamma \cup \Delta \rvert = 2\lvert \Gamma \rvert\) ou \(\lvert \Gamma \cup \Delta \rvert = \lvert \Gamma \rvert\).
Soient \(\Gamma_1, \ldots, \Gamma_k\) les composantes successives d'un joueur donné \(A\). On a obtenu que \(\lvert \Gamma_{i+1} \rvert = 2\lvert \Gamma_i \rvert\) ou \(\lvert \Gamma_{i+1} \rvert = \lvert \Gamma_i \rvert\) pour \(i = 1, \ldots, k - 1\). Comme \(\lvert \Gamma_1 \rvert = 2\), chaque \(\lvert \Gamma_i \rvert\) est une puissance de \(2\). En particulier, \(\lvert \Gamma_k \rvert = 2^u\) pour un certain \(u\).
D'autre part, d'après (i), le joueur \(A\) a joué contre \(k\) adversaires différents. Ils appartiennent tous à \(\Gamma_k\), donc \(\lvert \Gamma_k \rvert \geq k + 1\).
Ainsi \(2^u \geq k + 1\), et comme \(t_k\) est le plus petit entier vérifiant \(2^{t_k} \geq k + 1\), on conclut que \(u \geq t_k\). La taille de chaque \(k\)-composante est donc divisible par \(2^{t_k}\), ce qui termine la preuve. \(\blacksquare\)