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é

On dispose d'un jeu infini de cartes, chacune portant un nombre réel. Pour tout nombre réel \(x\), il y a exactement une carte du jeu portant le nombre \(x\). Deux joueurs tirent chacun un ensemble de \(100\) cartes, \(A\) et \(B\), disjoints. On veut définir une règle qui désigne l'un des deux comme gagnant. Cette règle doit vérifier les conditions suivantes :

  1. le gagnant ne dépend que de l'ordre relatif des \(200\) cartes : si les cartes sont posées face cachée dans l'ordre croissant et qu'on nous dit à quel joueur appartient chaque carte, sans nous dire les nombres écrits dessus, on peut quand même désigner le gagnant ;
  2. si l'on écrit les éléments des deux ensembles dans l'ordre croissant, \(A = \{a_1, a_2, \ldots, a_{100}\}\) et \(B = \{b_1, b_2, \ldots, b_{100}\}\), et que \(a_i > b_i\) pour tout \(i\), alors \(A\) bat \(B\) ;
  3. si trois joueurs tirent trois ensembles disjoints \(A, B, C\) du jeu, que \(A\) bat \(B\) et que \(B\) bat \(C\), alors \(A\) bat aussi \(C\).

De combien de façons peut-on définir une telle règle ? On considère deux règles comme différentes s'il existe deux ensembles \(A\) et \(B\) tels que \(A\) batte \(B\) selon l'une des règles, mais que \(B\) batte \(A\) selon l'autre.

Énoncé original (anglais)

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.

Problèmes voisins

Sur les mêmes idées, à une difficulté proche :

  • 2024 A2 ★☆☆☆☆ : Des entiers positifs de somme \(n\) : minimiser \(\sum 2^i x_i^2\).
  • 2015 C1 ★☆☆☆☆ : Des bulldozers de tailles distinctes le long d'une route : exactement une ville ne peut être balayée par aucune autre.
  • 2009 A1 ★☆☆☆☆ : On colorie les côtés de \(2009\) triangles puis on trie les longueurs par couleur : combien de triangles subsistent à coup sûr ?
  • 2024 C7 ★★★★☆ · OIM P3 : Chaque terme compte les apparitions du précédent : l'une des deux sous-suites de parité finit par être périodique.