Aller au contenu

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é

Soient \(m, n \geq 2\) des entiers, \(X\) un ensemble à \(n\) éléments, et \(X_1, X_2, \ldots, X_m\) des parties de \(X\) non vides, deux à deux distinctes, mais pas forcément disjointes. Une fonction \(f : X \to \{1, 2, \ldots, n + 1\}\) est dite agréable s'il existe un indice \(k\) tel que

\[\sum_{x \in X_k} f(x) > \sum_{x \in X_i} f(x) \quad \text{pour tout } i \neq k.\]

Montrer que le nombre de fonctions agréables est au moins \(n^n\).

Énoncé original (anglais)

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

\[\sum_{x \in X_k} f(x) > \sum_{x \in X_i} f(x) \quad \text{for all } i \neq k.\]

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

\[f^+(X_l) = f(X_l) + |X_l| \geq f(X_j) + |X_l| > f(X_j) + |X_j \cap X_l| = f^+(X_j).\]

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\)

Problèmes voisins

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

  • 2025 C5 ★★★☆☆ : Dans un \(n\)-uplet, le nombre total d'inversions est au plus \(5\) fois celui des inversions d'écart impair, et la constante \(5\) est optimale.
  • 2008 C4 ★★★☆☆ · OIM P5 : Allumer les \(n\) premières lampes en \(k\) étapes, avec ou sans toucher aux autres : quel est le rapport des nombres de façons ?
  • 2006 C3 ★★★☆☆ : Une somme pondérée par \(x^{a(P)}(1 - x)^{b(P)}\) sur tous les polygones convexes à sommets dans \(S\) vaut toujours \(1\).
  • 2015 C6 ★★★★☆ : Un ensemble d'entiers laisse une infinité d'entiers sans écriture unique comme somme d'un nombre impair de ses éléments.