Shortlist 2020, C7¶
Domaine : Combinatoire · Difficulté : ★★★★☆ · Proposé par : Thailand
Concepts : Récurrence et constructions récursives
Solution officielle : Shortlist officielle 2020 (avec solutions), p. 40 (page 42 du PDF)
Énoncé¶
Consider any rectangular table having finitely many rows and columns, with a real number \(a(r, c)\) in the cell in row \(r\) and column \(c\). A pair \((R, C)\), where \(R\) is a set of rows and \(C\) a set of columns, is called a saddle pair if the following two conditions are satisfied:
(i) For each row \(r'\), there is \(r \in R\) such that \(a(r, c) \geq a(r', c)\) for all \(c \in C\);
(ii) For each column \(c'\), there is \(c \in C\) such that \(a(r, c) \leq a(r, c')\) for all \(r \in R\).
A saddle pair \((R, C)\) is called a minimal pair if for each saddle pair \((R', C')\) with \(R' \subseteq R\) and \(C' \subseteq C\), we have \(R' = R\) and \(C' = C\).
Prove that any two minimal pairs contain the same number of rows.
Indices : les idées clés
- Applications de « domination » entre deux paires selles : la définition fournit des applications \(\rho_1, \rho_2, \sigma_1, \sigma_2\) entre les lignes et les colonnes de deux paires selles, qu'on compose.
- Itérer une application d'un ensemble fini dans lui-même (solution 1) : les images \(\rho^i(R_1)\) se stabilisent, et une puissance convenable de \(\rho\) devient l'identité sur l'image stable.
- Récurrence et constructions récursives (solution 2) : récurrence sur le nombre total de lignes et de colonnes, après s'être ramené au cas où les deux paires minimales partagent le tableau.
- Sommer des inégalités pour forcer l'égalité (solution 2) : une somme sur une permutation est invariante, donc toutes les inégalités de la chaîne sont des égalités.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2020 (deux solutions et deux remarques).
Solution 1¶
On dit qu'une paire \((R', C')\) d'ensembles non vides est une sous-paire de \((R, C)\) si \(R' \subseteq R\) et \(C' \subseteq C\) ; elle est propre si l'une au moins des inclusions est stricte.
Soient \((R_1, C_1)\) et \((R_2, C_2)\) deux paires selles avec \(|R_1| > |R_2|\). Nous allons trouver une sous-paire selle \((R', C')\) de \((R_1, C_1)\) avec \(|R'| \leq |R_2|\) ; cela entraîne clairement le résultat (une paire minimale ne peut pas avoir strictement plus de lignes qu'une autre paire selle).
Étape 1 : on construit \(\rho : R_1 \to R_1\) et \(\sigma : C_1 \to C_1\) telles que \(|\rho(R_1)| \leq |R_2|\) et \(a(\rho(r_1), c_1) \geq a(r_1, \sigma(c_1))\) pour tous \(r_1 \in R_1\), \(c_1 \in C_1\).
Comme \((R_1, C_1)\) est une paire selle, pour chaque \(r_2 \in R_2\) il existe \(r_1 \in R_1\) tel que \(a(r_1, c_1) \geq a(r_2, c_1)\) pour tout \(c_1 \in C_1\) ; notons \(\rho_1(r_2)\) un tel \(r_1\). On définit de même quatre applications :
Posons \(\rho = \rho_1 \circ \rho_2 : R_1 \to R_1\) et \(\sigma = \sigma_1 \circ \sigma_2 : C_1 \to C_1\). On a
De plus, pour tous \(r_1 \in R_1\) et \(c_1 \in C_1\),
comme voulu.
Étape 2 : à partir de \(\rho\) et \(\sigma\), on construit une sous-paire selle propre \((R', C')\) de \((R_1, C_1)\).
Les propriétés de \(\rho\) et \(\sigma\) donnent, en itérant,
pour tout entier \(i \geq 1\) et tous \(r_1 \in R_1\), \(c_1 \in C_1\).
Considérons les images \(R^i = \rho^i(R_1)\) et \(C^i = \sigma^i(C_1)\). On a \(R_1 = R^0 \supseteq R^1 \supseteq R^2 \supseteq \cdots\) et \(C_1 = C^0 \supseteq C^1 \supseteq C^2 \supseteq \cdots\). Ces chaînes étant formées d'ensembles finis, il existe un indice \(n\) tel que \(R^n = R^{n+1} = \cdots\) et \(C^n = C^{n+1} = \cdots\). Alors \(\rho^n(R^n) = R^{2n} = R^n\), donc la restriction de \(\rho^n\) à \(R^n\) est une bijection de \(R^n\) sur lui-même ; de même pour \(\sigma^n\) sur \(C^n\). Par conséquent, il existe un entier \(k \geq 1\) tel que \(\rho^{nk}\) soit l'identité sur \(R^n\) et \(\sigma^{nk}\) l'identité sur \(C^n\) (une permutation d'un ensemble fini a une puissance égale à l'identité).
Montrons que \((R^n, C^n)\) est une sous-paire selle de \((R_1, C_1)\) ; comme \(|R^n| \leq |R^1| = |\rho(R_1)| \leq |R_2|\), c'est ce que l'on voulait. Prenons une ligne quelconque \(r'\). Comme \((R_1, C_1)\) est une paire selle, il existe \(r_1 \in R_1\) tel que \(a(r_1, c_1) \geq a(r', c_1)\) pour tout \(c_1 \in C_1\). Posons \(r_* = \rho^{nk}(r_1) \in R^n\). Pour tout \(c \in C^n\), on a \(c = \sigma^{nk}(c)\), donc
ce qui établit la condition (i). La condition (ii) se vérifie de façon analogue. \(\blacksquare\)
Solution 2¶
Notons \(\mathcal{R}\) et \(\mathcal{C}\) l'ensemble de toutes les lignes et de toutes les colonnes, \(\mathcal{T}\) le tableau, et \(\mathcal{T}[R, C]\) le sous-tableau formé des lignes de \(R\) et des colonnes de \(C\).
On dit que la ligne \(r_1\) domine la ligne \(r_2\) sur les colonnes \(C\) (où \(C \subseteq \mathcal{C}\)), et on écrit \(r_1 \succeq_C r_2\) ou \(r_2 \preceq_C r_1\), si \(a(r_1, c) \geq a(r_2, c)\) pour tout \(c \in C\). On écrit \(r_1 \equiv_C r_2\) si \(a(r_1, c) = a(r_2, c)\) pour tout \(c \in C\). On utilise les mêmes notations pour les colonnes. Les conditions de la définition s'écrivent alors : (i) pour tout \(r' \in \mathcal{R}\), il existe \(r \in R\) avec \(r \succeq_C r'\) ; (ii) pour tout \(c' \in \mathcal{C}\), il existe \(c \in C\) avec \(c \preceq_R c'\).
Lemme. Soit \((R, C)\) une paire minimale. Supprimons du tableau des lignes hors de \(R\) et/ou des colonnes hors de \(C\). Alors \((R, C)\) reste une paire minimale dans le nouveau tableau.
Preuve. Évidemment, \((R, C)\) reste une paire selle. Soit \((R', C')\) une sous-paire propre de \((R, C)\). Comme \((R, C)\) est selle, pour toute ligne \(r^*\) du tableau initial, il existe \(r \in R\) avec \(r \succeq_C r^*\). Si \((R', C')\) devenait selle après la suppression, il existerait \(r' \in R'\) avec \(r' \succeq_{C'} r\) (car \(r\) n'a pas été supprimée). On aurait donc \(r' \succeq_{C'} r^*\), ce qui est exactement la condition (i) pour \((R', C')\) dans le tableau initial ; la condition (ii) se vérifie de même. Ainsi \((R', C')\) serait selle dans le tableau initial, ce qui contredit la minimalité de \((R, C)\). \(\square\)
D'après le lemme, il suffit de traiter le cas \(\mathcal{R} = R_1 \cup R_2\) et \(\mathcal{C} = C_1 \cup C_2\). Ensuite, si certaines lignes appartiennent à la fois à \(R_1\) et à \(R_2\), on duplique chacune d'elles, on attribue une copie à \(R_1\) et l'autre à \(R_2\) : \((R_1, C_1)\) et \((R_2, C_2)\) restent des paires minimales du nouveau tableau, avec les mêmes nombres de lignes et de colonnes, mais \(R_1\) et \(R_2\) deviennent disjoints. On fait de même pour les colonnes de \(C_1 \cap C_2\). Il suffit donc de traiter le cas \(R_1 \cap R_2 = \varnothing\) et \(C_1 \cap C_2 = \varnothing\).
La suite consiste à prouver l'affirmation suivante, qui contient l'énoncé.
Affirmation. Soient \((R_1, C_1)\) et \((R_2, C_2)\) deux paires minimales du tableau \(\mathcal{T}\) telles que \(R_2 = \mathcal{R} \setminus R_1\) et \(C_2 = \mathcal{C} \setminus C_1\). Alors \(|R_1| = |R_2|\), \(|C_1| = |C_2|\), et il existe quatre bijections
On démontre l'affirmation par récurrence sur \(|\mathcal{R}| + |\mathcal{C}|\).
Initialisation. On a \(|R_1| = |R_2| = |C_1| = |C_2| = 1\) ; notons \(R_i = \{r_i\}\), \(C_i = \{c_i\}\). Les deux paires étant selles,
donc le tableau est formé de quatre nombres égaux, et l'affirmation est vraie.
Hérédité. Introduisons \(\rho_1, \rho_2, \sigma_1, \sigma_2\) comme dans la solution 1, voir (1).
Cas où les quatre applications sont surjectives. Alors \(|R_1| = |R_2|\), \(|C_1| = |C_2|\), et les quatre applications sont bijectives. Pour tous \(r_2 \in R_2\) et \(c_2 \in C_2\),
En sommant,
Comme \(\rho_2 \circ \rho_1\) et \(\sigma_1^{-1} \circ \sigma_2^{-1}\) sont des permutations de \(R_2\) et de \(C_2\), cette inégalité est en fait une égalité. (Le livret écrit \(\rho_1 \circ \rho_2\) ; il faut lire \(\rho_2 \circ \rho_1\), qui est bien une permutation de \(R_2\).) Donc toutes les inégalités de (4) sont des égalités, ce qui donne les relations (3) (par exemple la deuxième inégalité, appliquée à \(c_2\) parcourant \(C_2\), donne \(\rho_1(r_2) \equiv_{C_1} r_2\)) et achève l'hérédité dans ce cas.
Il reste à montrer que les quatre applications sont surjectives. Supposons par l'absurde que \(\rho_1\) ne l'est pas. Posons \(R_1' = \rho_1(R_2)\), \(C_1' = \sigma_1(C_2)\), \(R^* = R_1 \setminus R_1'\) et \(C^* = C_1 \setminus C_1'\). Par hypothèse, \(R^* \neq \varnothing\).
Soit \(\mathcal{Q}\) le tableau obtenu à partir de \(\mathcal{T}\) en supprimant les lignes de \(R^*\) et les colonnes de \(C^*\) ; autrement dit \(\mathcal{Q} = \mathcal{T}[R_1' \cup R_2, C_1' \cup C_2]\). Par définition de \(\rho_1\), pour tout \(r_2 \in R_2\) on a \(\rho_1(r_2) \succeq_{C_1} r_2\), donc a fortiori \(\rho_1(r_2) \succeq_{C_1'} r_2\), et de plus \(\rho_1(r_2) \in R_1'\). De même, \(C_1' \ni \sigma_1(c_2) \preceq_{R_1'} c_2\) pour tout \(c_2 \in C_2\). Les lignes et colonnes de \(R_1'\) et \(C_1'\) se dominent trivialement elles-mêmes, donc \((R_1', C_1')\) est une paire selle de \(\mathcal{Q}\). Par ailleurs, \((R_2, C_2)\) reste une paire minimale de \(\mathcal{Q}\), d'après le lemme.
Par conséquent, \(\mathcal{Q}\) possède une paire minimale \((\overline{R}_1, \overline{C}_1)\) avec \(\overline{R}_1 \subseteq R_1'\) et \(\overline{C}_1 \subseteq C_1'\). Restreignons-nous un instant au sous-tableau \(\overline{\mathcal{Q}} = \mathcal{Q}[\overline{R}_1 \cup R_2, \overline{C}_1 \cup C_2]\). D'après le lemme, \((\overline{R}_1, \overline{C}_1)\) et \((R_2, C_2)\) sont aussi minimales dans \(\overline{\mathcal{Q}}\). Comme \(\overline{\mathcal{Q}}\) est strictement plus petit que \(\mathcal{T}\), l'hypothèse de récurrence donne
donc toutes ces inégalités sont des égalités. Ainsi \(\overline{R}_1 = R_1'\) et \(\rho_1\) est une bijection de \(R_2\) sur \(R_1'\). (Le livret écrit \(\overline{R}_2 = R_2'\) ; il faut lire \(\overline{R}_1 = R_1'\).) De même, \(\overline{C}_1 = C_1'\) et \(\sigma_1\) est une bijection de \(C_2\) sur \(C_1'\). En particulier, \((R_1', C_1')\) est une paire minimale de \(\mathcal{Q}\).
Par l'hypothèse de récurrence à nouveau (appliquée dans \(\mathcal{Q}\)), \(|R_1'| = |R_2|\), \(|C_1'| = |C_2|\), et il existe quatre bijections
Remarquons que \(\sigma_1\) et \(\sigma_1'\) sont deux bijections \(C_2 \to C_1'\) telles que \(\sigma_1'(c_2) \equiv_{R_1'} c_2 \succeq_{R_1'} \sigma_1(c_2)\) pour tout \(c_2 \in C_2\). Si l'on avait \(\sigma_1'(c_2) \neq \sigma_1(c_2)\) pour un certain \(c_2\), on pourrait retirer la colonne \(\sigma_1'(c_2)\) de \(C_1'\) et obtenir une autre paire selle \(\bigl(R_1', C_1' \setminus \{\sigma_1'(c_2)\}\bigr)\) dans \(\mathcal{Q}\) (la colonne retirée est dominée, au sens de (ii), par \(\sigma_1(c_2)\), qui reste). C'est impossible pour une paire minimale ; donc \(\sigma_1 = \sigma_1'\).
Montrons enfin que \((R_1', C_1')\) est une paire selle de \(\mathcal{T}\) : ce sera la contradiction cherchée, puisque c'est une sous-paire propre de \((R_1, C_1)\) (\(R^* \neq \varnothing\)), qui est minimale. Par symétrie, il suffit de trouver, pour tout \(r' \in \mathcal{R}\), une ligne \(r_1 \in R_1'\) telle que \(r_1 \succeq_{C_1'} r'\). Si \(r' \in R_2\), on prend \(r_1 = \rho_1(r')\). Supposons donc \(r' \in R_1\).
Il existe \(r_2 \in R_2\) tel que \(r' \preceq_{C_2} r_2\) ; posons \(r_1 = (\rho_2')^{-1}(r_2) \in R_1'\) et rappelons que \(r_1 \equiv_{C_2} r_2 \succeq_{C_2} r'\). En utilisant la bijection \(\sigma_1 = \sigma_1'\), pour tout \(c_1 \in C_1'\) :
ce qui montre \(r' \preceq_{C_1'} r_1\), comme voulu. (La première inégalité vient de la définition de \(\sigma_1\), la deuxième de \(r_1 \succeq_{C_2} r'\) puisque \(\sigma_1^{-1}(c_1) \in C_2\), l'égalité de \(\sigma_1'(c_2) \equiv_{R_1'} c_2\).) L'hérédité est établie. \(\blacksquare\)
Remarques¶
Remarque 1. Pour deux paires minimales \((R_1, C_1)\) et \((R_2, C_2)\), la solution 2 prouve non seulement \(|R_1| = |R_2|\) et \(|C_1| = |C_2|\), mais aussi l'existence des bijections (3) : les quatre sous-tableaux \(\mathcal{T}[R_1, C_1]\), \(\mathcal{T}[R_1, C_2]\), \(\mathcal{T}[R_2, C_1]\), \(\mathcal{T}[R_2, C_2]\) ne diffèrent que par une permutation des lignes et des colonnes. Cela entraîne aussitôt que \((R_1, C_2)\) et \((R_2, C_1)\) sont aussi des paires minimales.
Cette version forte découle aussi des arguments de la solution 1, même sans supposer \(R_1 \cap R_2 = \varnothing\) et \(C_1 \cap C_2 = \varnothing\) : si \(|R_1| = |R_2|\) et \(|C_1| = |C_2|\), on montre de même que \(R^n = R_1\), \(C^n = C_1\), et pour \(r \in R^n\), \(c \in C^n\),
donc toutes ces inégalités, puis toutes celles de (2), sont des égalités ; ainsi \(\rho_1, \rho_2, \sigma_1, \sigma_2\) vérifient (3).
On ne peut pas toujours choisir les bijections de (3) de sorte que \(\rho_1 = \rho_2^{-1}\) et \(\sigma_1 = \sigma_2^{-1}\), comme le montre le tableau suivant (les deux premières lignes et colonnes forment une paire minimale, les deux dernières une autre) :
Remarque 2. Une formulation plus concrète du même problème : sur un marché, des détaillants vendent tous les mêmes produits, chacun à ses propres prix. Le détaillant \(r_1\) domine \(r_2\) pour un ensemble de produits \(P\) si son prix pour chaque \(p \in P\) ne dépasse pas celui de \(r_2\) ; le produit \(p_1\) surpasse \(p_2\) pour un ensemble de détaillants \(R\) si, chez chaque \(r \in R\), le prix de \(p_1\) est au moins celui de \(p_2\). Un ensemble \(R\) de détaillants et un ensemble \(P\) de produits forment une paire selle si tout détaillant est dominé (pour \(P\)) par un détaillant de \(R\), et tout produit est surpassé (pour \(R\)) par un produit de \(P\) ; la paire est minimale si aucune paire selle n'est strictement contenue dedans. Montrer que deux paires minimales contiennent le même nombre de détaillants.