Aller au contenu

Shortlist 2014, C6

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

Concepts : Principe extrémal · Récurrence et constructions récursives

Solution officielle : Shortlist officielle 2014 (avec solutions), p. 36 (page 37 du PDF)

Énoncé

We are given an infinite deck of cards, each with a real number on it. For every real number \(x\), there is exactly one card in the deck that has \(x\) written on it. Now two players draw disjoint sets \(A\) and \(B\) of \(100\) cards each from this deck. We would like to define a rule that declares one of them a winner. This rule should satisfy the following conditions:

  1. The winner only depends on the relative order of the \(200\) cards: if the cards are laid down in increasing order face down and we are told which card belongs to which player, but not what numbers are written on them, we can still decide the winner.
  2. If we write the elements of both sets in increasing order as \(A = \{a_1, a_2, \ldots, a_{100}\}\) and \(B = \{b_1, b_2, \ldots, b_{100}\}\), and \(a_i > b_i\) for all \(i\), then \(A\) beats \(B\).
  3. If three players draw three disjoint sets \(A, B, C\) from the deck, \(A\) beats \(B\) and \(B\) beats \(C\), then \(A\) also beats \(C\).

How many ways are there to define such a rule? Here, we consider two rules as different if there exist two sets \(A\) and \(B\) such that \(A\) beats \(B\) according to one rule, but \(B\) beats \(A\) according to the other.

Indices : les idées clés
  • Les \(n\) règles évidentes : pour \(k\) fixé, « \(A\) bat \(B\) si et seulement si \(a_k > b_k\) » ; elles sont distinctes, donc il y en a au moins \(n\) (\(n = 100\)).
  • Principe extrémal (solution 1) : on prend \(k\) minimal tel que \(A_k = \{1, \ldots, k, n + k + 1, \ldots, 2n\}\) perde contre \(B_k = \{k + 1, \ldots, n + k\}\), puis on intercale trois ensembles auxiliaires \(U\), \(V\), \(W\) pour obtenir \(X < V < W < U < Y\) dès que \(x_k < y_k\).
  • Récurrence sur \(n\) (solution 2) : on montre que le plus petit (ou le plus grand) élément de chaque ensemble ne compte pas, et l'on se ramène à \(n - 1\).
Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2014 (deux solutions et une remarque).

Réponse : \(100\).

Solution 1

On prouve un énoncé plus général pour des ensembles de cardinal \(n\) (le problème est le cas \(n = 100\), et la réponse est alors \(n\)). On écrit \(A > B\) ou \(B < A\) pour « \(A\) bat \(B\) ».

Partie I. Définissons d'abord \(n\) règles différentes qui satisfont les conditions. Fixons un indice \(k \in \{1, 2, \ldots, n\}\). On écrit \(A\) et \(B\) dans l'ordre croissant, \(A = \{a_1, a_2, \ldots, a_n\}\) et \(B = \{b_1, b_2, \ldots, b_n\}\), et l'on dit que \(A\) bat \(B\) si et seulement si \(a_k > b_k\). Cette règle vérifie clairement les trois conditions, et les règles correspondant à des \(k\) différents sont toutes différentes. Il y a donc au moins \(n\) règles.

Partie II. Montrons qu'il n'y en a pas d'autre. Supposons que notre règle vérifie les conditions, et soit \(k \in \{1, 2, \ldots, n\}\) minimal tel que

\[A_k = \{1, 2, \ldots, k, n + k + 1, n + k + 2, \ldots, 2n\} < B_k = \{k + 1, k + 2, \ldots, n + k\}.\]

Un tel \(k\) existe, car c'est vrai pour \(k = n\) par la condition 2. Considérons maintenant deux ensembles disjoints \(X = \{x_1, x_2, \ldots, x_n\}\) et \(Y = \{y_1, y_2, \ldots, y_n\}\), écrits dans l'ordre croissant (\(x_1 < x_2 < \cdots < x_n\) et \(y_1 < y_2 < \cdots < y_n\)). On affirme que \(X < Y\) si (et donc, automatiquement, seulement si) \(x_k < y_k\).

Pour le prouver, choisissons des réels \(u_i, v_i, w_i \notin X \cup Y\) tels que

\[u_1 < u_2 < \cdots < u_{k-1} < \min(x_1, y_1), \qquad \max(x_n, y_n) < v_{k+1} < v_{k+2} < \cdots < v_n,\]
\[x_k < v_1 < v_2 < \cdots < v_k < w_1 < w_2 < \cdots < w_n < u_k < u_{k+1} < \cdots < u_n < y_k,\]

et posons

\[U = \{u_1, u_2, \ldots, u_n\}, \qquad V = \{v_1, v_2, \ldots, v_n\}, \qquad W = \{w_1, w_2, \ldots, w_n\}.\]

Alors :

  • \(u_i < y_i\) et \(x_i < v_i\) pour tout \(i\), donc \(U < Y\) et \(X < V\) par la condition 2 ;
  • les éléments de \(U \cup W\) sont rangés comme ceux de \(A_{k-1} \cup B_{k-1}\), et comme \(A_{k-1} > B_{k-1}\) par le choix de \(k\), on a aussi \(U > W\) (si \(k = 1\), c'est évident) ;
  • les éléments de \(V \cup W\) sont rangés comme ceux de \(A_k \cup B_k\), et comme \(A_k < B_k\) par le choix de \(k\), on a aussi \(V < W\).

Il s'ensuit que

\[X < V < W < U < Y,\]

donc \(X < Y\) par la condition 3, ce qu'il fallait démontrer. \(\blacksquare\)

Solution 2

On peut aussi traiter la partie II par récurrence sur \(n\). Pour \(n = 1\), il n'y a évidemment qu'une règle, d'après la condition 2.

Supposons l'affirmation (il n'y a pas d'autre règle que celles de la partie I) vraie pour \(n - 1\). Commençons par une observation.

Affirmation. Au moins l'une des deux relations

\[\big(\{2\} \cup \{2i - 1 \mid 2 \leq i \leq n\}\big) < \big(\{1\} \cup \{2i \mid 2 \leq i \leq n\}\big)\]

et

\[\big(\{2i - 1 \mid 1 \leq i \leq n - 1\} \cup \{2n\}\big) < \big(\{2i \mid 1 \leq i \leq n - 1\} \cup \{2n - 1\}\big)\]

est vraie.

Preuve. Supposons la première relation fausse. Comme la règle ne dépend que de l'ordre relatif, on a aussi

\[\big(\{2\} \cup \{3i - 2 \mid 2 \leq i \leq n - 1\} \cup \{3n - 2\}\big) > \big(\{1\} \cup \{3i - 1 \mid 2 \leq i \leq n - 1\} \cup \{3n\}\big).\]

De même, si la seconde relation est fausse, on a aussi

\[\big(\{1\} \cup \{3i - 1 \mid 2 \leq i \leq n - 1\} \cup \{3n\}\big) > \big(\{3\} \cup \{3i \mid 2 \leq i \leq n - 1\} \cup \{3n - 1\}\big).\]

La condition 3 donne alors

\[\big(\{2\} \cup \{3i - 2 \mid 2 \leq i \leq n - 1\} \cup \{3n - 2\}\big) > \big(\{3\} \cup \{3i \mid 2 \leq i \leq n - 1\} \cup \{3n - 1\}\big),\]

ce qui contredit la condition 2. \(\square\)

On distingue deux cas selon la relation qui est vraie.

Premier cas : \(\big(\{2\} \cup \{2i - 1 \mid 2 \leq i \leq n\}\big) < \big(\{1\} \cup \{2i \mid 2 \leq i \leq n\}\big)\).

Soient \(A = \{a_1, a_2, \ldots, a_n\}\) et \(B = \{b_1, b_2, \ldots, b_n\}\) deux ensembles disjoints, écrits dans l'ordre croissant. On affirme que le gagnant ne dépend que de \(a_2, \ldots, a_n\) et \(b_2, \ldots, b_n\), et pas de \(a_1\) ni de \(b_1\). Supposons le contraire, et sans perte de généralité \(a_2 < b_2\). L'ordre relatif de \(a_1, a_2, \ldots, a_n, b_2, \ldots, b_n\) est alors fixé, et c'est la position de \(b_1\) qui décide du gagnant. Supposons que pour une valeur \(b_1 = x\), \(B\) gagne, et que pour une autre valeur \(b_1 = y\), \(A\) gagne.

Posons \(B_x = \{x, b_2, \ldots, b_n\}\) et \(B_y = \{y, b_2, \ldots, b_n\}\), et soit \(\varepsilon > 0\) plus petit que la moitié de la distance entre deux quelconques des nombres de \(B_x \cup B_y \cup A\). Pour un ensemble \(M\), notons \(M \pm \varepsilon\) l'ensemble obtenu en ajoutant (ou en retranchant) \(\varepsilon\) à tous ses éléments. Par le choix de \(\varepsilon\), l'ordre relatif des éléments de \((B_y + \varepsilon) \cup A\) est le même que pour \(B_y \cup A\), et celui des éléments de \((B_x - \varepsilon) \cup A\) est le même que pour \(B_x \cup A\). Donc \(A < B_x - \varepsilon\), mais \(A > B_y + \varepsilon\). De plus, si \(y > x\), alors \(B_x - \varepsilon < B_y + \varepsilon\) par la condition 2 ; sinon, l'ordre relatif des éléments de \((B_x - \varepsilon) \cup (B_y + \varepsilon)\) est le même que pour les deux ensembles \(\{2\} \cup \{2i - 1 \mid 2 \leq i \leq n\}\) et \(\{1\} \cup \{2i \mid 2 \leq i \leq n\}\), de sorte que \(B_x - \varepsilon < B_y + \varepsilon\). Dans les deux cas,

\[A < B_x - \varepsilon < B_y + \varepsilon < A,\]

ce qui contredit la condition 3.

Le gagnant ne dépend donc pas de \(a_1\), \(b_1\). On peut ainsi définir une nouvelle règle \(<^*\) sur les ensembles de cardinal \(n - 1\) en disant que \(A <^* B\) si et seulement si \(A \cup \{a\} < B \cup \{b\}\) pour certains \(a, b\) (ou, de façon équivalente, pour tous) tels que \(a < \min A\), \(b < \min B\) et \(A \cup \{a\}\), \(B \cup \{b\}\) disjoints. La règle \(<^*\) vérifie encore toutes les conditions ; par l'hypothèse de récurrence, il existe un indice \(i\) tel que \(A <^* B\) si et seulement si le \(i\)-ème plus petit élément de \(A\) est inférieur au \(i\)-ème plus petit élément de \(B\). Cela implique que \(C < D\) si et seulement si le \((i + 1)\)-ème plus petit élément de \(C\) est inférieur au \((i + 1)\)-ème plus petit élément de \(D\), ce qui achève la récurrence.

Second cas : \(\big(\{2i - 1 \mid 1 \leq i \leq n - 1\} \cup \{2n\}\big) < \big(\{2i \mid 1 \leq i \leq n - 1\} \cup \{2n - 1\}\big)\).

Posons \(-A = \{-a \mid a \in A\}\) pour \(A \subseteq \mathbb{R}\). Pour deux ensembles disjoints \(A, B \subseteq \mathbb{R}\) de cardinal \(n\), on écrit \(A <^\circ B\) pour signifier \((-B) < (-A)\). On voit facilement que \(<^\circ\) est une règle qui vérifie les trois conditions du problème ainsi que la relation du premier cas. Comme dans le premier cas, il existe donc un \(i\) tel que \(A <^\circ B\) si et seulement si le \(i\)-ème plus petit élément de \(A\) est inférieur au \(i\)-ème plus petit élément de \(B\), ce qui équivaut à dire que le \(i\)-ème plus grand élément de \(-A\) est supérieur au \(i\)-ème plus grand élément de \(-B\). La règle de départ \(<\) a donc bien la forme voulue. \(\blacksquare\)

Remarque

Le problème demande tous les ordres partiels sur les parties à \(n\) éléments de \(\mathbb{R}\) pour lesquels deux ensembles disjoints sont toujours comparables, la relation ne dépend que de l'ordre relatif des éléments, et \(\{a_1, a_2, \ldots, a_n\} < \{b_1, b_2, \ldots, b_n\}\) dès que \(a_i < b_i\) pour tout \(i\).

Comme le signale l'auteur du problème, on peut aussi chercher tous les ordres totaux sur les parties à \(n\) éléments de \(\mathbb{R}\) (en abandonnant la condition de disjonction et en demandant \(\{a_1, \ldots, a_n\} \preceq \{b_1, \ldots, b_n\}\) dès que \(a_i \leq b_i\) pour tout \(i\)). Le nombre de possibilités est alors \(n!\), et on les obtient toutes ainsi : on fixe une permutation \(\sigma \in S_n\), et pour deux parties \(A = \{a_1, \ldots, a_n\}\) et \(B = \{b_1, \ldots, b_n\}\) avec \(a_1 < \cdots < a_n\) et \(b_1 < \cdots < b_n\), on dit que \(A >_\sigma B\) si et seulement si \((a_{\sigma(1)}, \ldots, a_{\sigma(n)})\) est lexicographiquement plus grand que \((b_{\sigma(1)}, \ldots, b_{\sigma(n)})\). Cette formulation semble toutefois ajouter plus de technique que d'idées nouvelles.