Shortlist 2022, C5¶
Domaine : Combinatoire · Difficulté : ★★★☆☆ · Proposé par : Germany
Concepts : Bijections et dénombrement · Principe extrémal
Solution officielle : Shortlist officielle 2022 (avec solutions), p. 31 (page 33 du PDF)
Énoncé¶
Let \(m, n \geq 2\) be integers, let \(X\) be a set with \(n\) elements, and let \(X_1, X_2, \ldots, X_m\) be pairwise distinct non-empty, not necessarily disjoint subsets of \(X\). A function \(f : X \to \{1, 2, \ldots, n + 1\}\) is called nice if there exists an index \(k\) such that
Prove that the number of nice functions is at least \(n^n\).
Indices : les idées clés
- Bijections et dénombrement : on construit une injection de l'ensemble des \(n^n\) fonctions \(X \to \{1, \ldots, n\}\) dans l'ensemble des fonctions sympathiques.
- Principe extrémal : on choisit un ensemble \(X_l\) qui maximise \(f(X_l)\), puis on ajoute \(1\) à \(f\) sur \(X_l\) pour rendre ce maximum unique.
- Inverser la construction : le maximum de \(f^+\) étant unique, on retrouve \(X_l\), donc \(f\), à partir de \(f^+\).
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2022 (une solution).
Solution¶
Pour \(Y \subseteq X\), on note \(f(Y) = \sum_{y \in Y} f(y)\). Une fonction \(f : X \to \{1, \ldots, n+1\}\) est sympathique si et seulement si \(f(X_i)\) atteint son maximum en un unique indice \(i \in \{1, \ldots, m\}\).
On s'intéresse d'abord à l'ensemble \(\mathcal{F}\) des fonctions \(f : X \to \{1, \ldots, n\}\) ; on a \(|\mathcal{F}| = n^n\).
À toute \(f \in \mathcal{F}\), on associe une fonction \(f^+ : X \to \{1, 2, \ldots, n+1\}\) de la façon suivante. On choisit un ensemble \(X_l\) qui maximise \(f(X_l)\) (principe extrémal), puis :
- pour tout \(x \in X_l\), \(f^+(x) = f(x) + 1\) ;
- pour tout \(x \in X \setminus X_l\), \(f^+(x) = f(x)\).
Affirmation. La fonction \(f^+\) est sympathique.
Preuve. On a \(f^+(X_i) = f(X_i) + |X_i \cap X_l|\) pour tout \(i\). Montrons que \(f^+(X_i)\) est maximal uniquement en \(i = l\). Soit \(j \neq l\). L'inclusion \(X_l \subsetneq X_j\) est impossible : elle entraînerait \(f(X_j) > f(X_l)\) (les valeurs de \(f\) sont positives), contredisant le choix de \(X_l\). En particulier, \(|X_l| > |X_j \cap X_l|\). Alors
La première inégalité vient du choix de \(X_l\) (qui maximise \(f(X_l)\)), la seconde (stricte) de \(|X_l| > |X_j \cap X_l|\). \(\square\)
Injectivité. On peut reconstruire \(f\) à partir de \(f^+\) de façon unique : d'après l'affirmation, \(f^+\) a un unique ensemble maximisant \(X_l\), et en diminuant de \(1\) les valeurs de \(f^+\) sur \(X_l\), on retrouve toutes les valeurs de \(f\). Ainsi l'application \(f \mapsto f^+\) est injective (dénombrement). Comme chacune des \(n^n\) fonctions \(f \in \mathcal{F}\) fournit une fonction sympathique \(f^+\) différente, il y a au moins \(n^n\) fonctions sympathiques. \(\blacksquare\)