Shortlist 2007, C7

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

Concepts : Bijections et dénombrement · Récurrence et constructions récursives

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

Énoncé

Let \(\alpha < \frac{3 - \sqrt{5}}{2}\) be a positive real number. Prove that there exist positive integers \(n\) and \(p > \alpha \cdot 2^n\) for which one can select \(2p\) pairwise distinct subsets \(S_1, \ldots, S_p, T_1, \ldots, T_p\) of the set \(\{1, 2, \ldots, n\}\) such that \(S_i \cap T_j \neq \varnothing\) for all \(1 \leq i, j \leq p\).

Indices : les idées clés

• Construction par blocs : on découpe \(\{1, \ldots, n\}\) en \(k\) blocs \(A_i\) de taille \(m\) ; \(\mathcal{S}\) = ensembles qui rencontrent tous les blocs, \(\mathcal{T}\) = ensembles qui contiennent un bloc mais ne sont pas dans \(\mathcal{S}\).
• Dénombrement : \(\lvert \mathcal{S} \rvert = (2^m - 1)^k\) et \(\lvert \mathcal{T} \rvert = 2^{km} - 2(2^m - 1)^k + (2^m - 2)^k\).
• Limite : avec \(k \approx 2^m\ln\frac{1}{\delta}\) et \(\delta = \frac{3 - \sqrt{5}}{2}\), les deux proportions tendent vers \(\delta\) et \(1 - 2\delta + \delta^2 = \delta\).

Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2007 (une solution et une remarque).

Solution

Soient \(k\) et \(m\) des entiers strictement positifs (à déterminer plus tard), et posons \(n = km\). Découpons \(\{1, 2, \ldots, n\}\) en \(k\) parties disjointes de taille \(m\) chacune ; notons-les \(A_1, \ldots, A_k\). Définissons les familles d'ensembles suivantes :

\[\mathcal{S} = \{S \subset \{1, 2, \ldots, n\} : \forall i \ S \cap A_i \neq \varnothing\},\]

\[\mathcal{T}_1 = \{T \subset \{1, 2, \ldots, n\} : \exists i \ A_i \subset T\}, \qquad \mathcal{T} = \mathcal{T}_1 \setminus \mathcal{S}.\]

Pour tout ensemble \(T \in \mathcal{T} \subset \mathcal{T}_1\), il existe un indice \(1 \leq i \leq k\) tel que \(A_i \subset T\). Alors, pour tout \(S \in \mathcal{S}\), \(S \cap T \supset S \cap A_i \neq \varnothing\). Donc chaque \(S \in \mathcal{S}\) et chaque \(T \in \mathcal{T}\) ont au moins un élément commun.

Montrons ci-dessous qu'on peut choisir \(m\) et \(k\) de sorte que \(\lvert \mathcal{S} \rvert, \lvert \mathcal{T} \rvert > \alpha \cdot 2^n\). Alors, en choisissant \(p = \min\{\lvert \mathcal{S} \rvert, \lvert \mathcal{T} \rvert\}\), on peut sélectionner les \(2p\) ensembles voulus \(S_1, \ldots, S_p\) et \(T_1, \ldots, T_p\) dans les familles \(\mathcal{S}\) et \(\mathcal{T}\) respectivement. Comme les familles \(\mathcal{S}\) et \(\mathcal{T}\) sont disjointes, les ensembles \(S_i\) et \(T_j\) seront deux à deux distincts.

Pour compter les ensembles \(S \in \mathcal{S}\), remarquons que chaque \(A_i\) a \(2^m - 1\) parties non vides, d'où \(2^m - 1\) choix pour \(S \cap A_i\). Ces intersections déterminent \(S\) de façon unique, donc

\[\lvert \mathcal{S} \rvert = (2^m - 1)^k. \tag{1}\]

De même, si un ensemble \(H \subset \{1, 2, \ldots, n\}\) ne contient pas un certain ensemble \(A_i\), on a \(2^m - 1\) choix pour \(H \cap A_i\) : toutes les parties de \(A_i\) sauf \(A_i\) lui-même. Le complémentaire de \(\mathcal{T}_1\) contient donc \((2^m - 1)^k\) ensembles, et

\[\lvert \mathcal{T}_1 \rvert = 2^{km} - (2^m - 1)^k. \tag{2}\]

Considérons ensuite la famille \(\mathcal{S} \setminus \mathcal{T}_1\). Si un ensemble \(S\) rencontre tous les \(A_i\) mais n'en contient aucun, il y a \(2^m - 2\) valeurs possibles pour chaque \(S \cap A_i\) : toutes les parties de \(A_i\) sauf \(\varnothing\) et \(A_i\). Le nombre de ces ensembles \(S\) est donc \((2^m - 2)^k\), de sorte que

\[\lvert \mathcal{S} \setminus \mathcal{T}_1 \rvert = (2^m - 2)^k. \tag{3}\]

De (1), (2) et (3), on obtient

\[\lvert \mathcal{T} \rvert = \lvert \mathcal{T}_1 \rvert - \lvert \mathcal{S} \cap \mathcal{T}_1 \rvert = \lvert \mathcal{T}_1 \rvert - \big(\lvert \mathcal{S} \rvert - \lvert \mathcal{S} \setminus \mathcal{T}_1 \rvert\big) = 2^{km} - 2(2^m - 1)^k + (2^m - 2)^k.\]

Posons \(\delta = \frac{3 - \sqrt{5}}{2}\) et \(k = k(m) = \left[2^m\ln\frac{1}{\delta}\right]\). Alors

\[\lim_{m \to \infty}\frac{\lvert \mathcal{S} \rvert}{2^{km}} = \lim_{m \to \infty}\left(1 - \frac{1}{2^m}\right)^k = \exp\left(-\lim_{m \to \infty}\frac{k}{2^m}\right) = \delta\]

et de même

\[\lim_{m \to \infty}\frac{\lvert \mathcal{T} \rvert}{2^{km}} = 1 - 2\lim_{m \to \infty}\left(1 - \frac{1}{2^m}\right)^k + \lim_{m \to \infty}\left(1 - \frac{2}{2^m}\right)^k = 1 - 2\delta + \delta^2 = \delta.\]

Donc, si \(m\) est assez grand, \(\frac{\lvert \mathcal{S} \rvert}{2^{mk}}\) et \(\frac{\lvert \mathcal{T} \rvert}{2^{mk}}\) sont supérieurs à \(\alpha\) (puisque \(\alpha < \delta\)). Ainsi \(\lvert \mathcal{S} \rvert, \lvert \mathcal{T} \rvert > \alpha \cdot 2^{mk} = \alpha \cdot 2^n\). \(\blacksquare\)

Remarque

On peut prouver que la constante \(\frac{3 - \sqrt{5}}{2}\) est optimale. En effet, si \(S_1, \ldots, S_p, T_1, \ldots, T_p\) sont des parties distinctes de \(\{1, 2, \ldots, n\}\) telles que chaque \(S_i\) rencontre chaque \(T_j\), alors \(p < \frac{3 - \sqrt{5}}{2} \cdot 2^n\).