Shortlist 2008, C6¶
Domaine : Combinatoire · Difficulté : ★★★★☆ · Proposé par : non indiqué
Concepts : Double comptage · Récurrence et constructions récursives
Solution officielle : Shortlist officielle 2008 (avec solutions), p. 27 (page 28 du PDF)
Énoncé¶
For \(n \geq 2\), let \(S_1, S_2, \ldots, S_{2^n}\) be \(2^n\) subsets of \(A = \{1, 2, 3, \ldots, 2^{n+1}\}\) that satisfy the following property: There do not exist indices \(a\) and \(b\) with \(a < b\) and elements \(x, y, z \in A\) with \(x < y < z\) such that \(y, z \in S_a\) and \(x, z \in S_b\). Prove that at least one of the sets \(S_1, S_2, \ldots, S_{2^n}\) contains no more than \(4n\) elements.
Indices : les idées clés
- Éléments \(k\)-bons : \(z\) est \(k\)-bon pour \(S_a\) s'il y a \(x < y < z\) dans \(S_a\) avec \(z - y < 2^k \leq z - x\) ; un même \(z\) est \(k\)-bon pour au plus un ensemble, donc bon pour au plus \(n\) ensembles.
- Éléments non bons : ils vérifient \(u_m - u_1 > 2(u_{m-1} - u_1)\), donc chaque ensemble en a au plus \(n + 1\) ; le double comptage donne une somme des cardinaux au plus \((3n + 1)2^n\).
- Solution 2, récurrence sur \(n\) : \(\sum_i(\lvert S_i \rvert - n) \leq (2n - 1)2^{n-2}\), en coupant \(\{1, \ldots, 2^{n+1}\}\) en deux moitiés ; d'où un ensemble d'au plus \(2n + 1\) éléments.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2008 (deux solutions et une remarque).
Solution 1¶
Montrons qu'il existe un ensemble \(S_a\) d'au plus \(3n + 1\) éléments.
Étant donné \(k \in \{1, \ldots, n\}\), on dit qu'un élément \(z \in A\) est \(k\)-bon pour un ensemble \(S_a\) si \(z \in S_a\) et si \(S_a\) contient deux autres éléments \(x\) et \(y\) avec \(x < y < z\) tels que \(z - y < 2^k\) et \(z - x \geq 2^k\). De plus, \(z \in A\) est dit bon pour \(S_a\) s'il est \(k\)-bon pour \(S_a\) pour un certain \(k = 1, \ldots, n\).
Montrons que chaque \(z \in A\) peut être \(k\)-bon pour au plus un ensemble \(S_a\). En effet, supposons au contraire que \(z\) soit \(k\)-bon à la fois pour \(S_a\) et pour \(S_b\), avec \(a < b\). Il existe alors \(y_a \in S_a\), \(y_a < z\), et \(x_b \in S_b\), \(x_b < z\), tels que \(z - y_a < 2^k\) et \(z - x_b \geq 2^k\). D'autre part, comme \(z \in S_a \cap S_b\), la condition du problème interdit tout élément de \(S_a\) strictement entre \(x_b\) et \(z\). Donc \(y_a \leq x_b\), ce qui implique \(z - y_a \geq z - x_b\). Cela contredit \(z - y_a < 2^k\) et \(z - x_b \geq 2^k\). L'affirmation en découle.
Par conséquent, un \(z \in A\) fixé peut être bon pour au plus \(n\) des ensembles donnés (au plus un pour chaque \(k = 1, \ldots, n\)).
De plus, soient \(u_1 < u_2 < \cdots < u_m < \cdots < u_p\) tous les éléments d'un ensemble fixé \(S_a\) qui ne sont pas bons pour \(S_a\). Montrons que \(u_m - u_1 > 2(u_{m-1} - u_1)\) pour tout \(m \geq 3\).
En effet, supposons que \(u_m - u_1 \leq 2(u_{m-1} - u_1)\) pour un certain \(m \geq 3\). Cette inégalité s'écrit \(2(u_m - u_{m-1}) \leq u_m - u_1\). Prenons l'unique \(k\) tel que \(2^k \leq u_m - u_1 < 2^{k+1}\). Alors \(2(u_m - u_{m-1}) \leq u_m - u_1 < 2^{k+1}\) donne \(u_m - u_{m-1} < 2^k\). Mais alors les éléments \(z = u_m\), \(x = u_1\), \(y = u_{m-1}\) de \(S_a\) vérifient \(z - y < 2^k\) et \(z - x \geq 2^k\), de sorte que \(z = u_m\) est \(k\)-bon pour \(S_a\), ce qui est une contradiction.
Ainsi, chaque terme de la suite \(u_2 - u_1, u_3 - u_1, \ldots, u_p - u_1\) est plus que le double du précédent. Donc \(u_p - u_1 > 2^{p-1}(u_2 - u_1) \geq 2^{p-1}\). Mais \(u_p \in \{1, 2, \ldots, 2^{n+1}\}\), donc \(u_p \leq 2^{n+1}\). Cela donne \(p - 1 \leq n\), c'est-à-dire \(p \leq n + 1\).
Autrement dit, chaque ensemble \(S_a\) contient au plus \(n + 1\) éléments qui ne sont pas bons pour lui.
Pour résumer, marquons en rouge tous les éléments des ensembles \(S_a\) qui sont bons pour l'ensemble correspondant, et en bleu ceux qui ne le sont pas. Le nombre total d'éléments rouges, comptés avec multiplicité, est au plus \(n \cdot 2^{n+1}\) (chaque \(z \in A\) peut être marqué en rouge dans au plus \(n\) ensembles). Le nombre total d'éléments bleus est au plus \((n + 1)2^n\) (chaque ensemble \(S_a\) contient au plus \(n + 1\) éléments bleus). La somme des cardinaux de \(S_1, S_2, \ldots, S_{2^n}\) ne dépasse donc pas \((3n + 1)2^n\). En moyennant, le plus petit ensemble a au plus \(3n + 1\) éléments. \(\blacksquare\)
Solution 2¶
Montrons que l'un des ensembles \(S_a\) a au plus \(2n + 1\) éléments. Dans la suite, \(\lvert \cdot \rvert\) désigne le cardinal d'un ensemble (fini).
Affirmation. Pour \(n \geq 2\), supposons que \(k\) parties \(S_1, \ldots, S_k\) de \(\{1, 2, \ldots, 2^n\}\) (pas nécessairement distinctes) vérifient la condition du problème. Alors
Preuve. Remarquons que si les ensembles \(S_i\) (\(1 \leq i \leq k\)) vérifient la condition, alors des parties quelconques \(T_i \subseteq S_i\) (\(1 \leq i \leq k\)) la vérifient aussi. La condition est aussi vraie pour les ensembles \(t + S_i = \{t + x \mid x \in S_i\}\), où \(t\) est arbitraire.
Remarquons aussi qu'un ensemble ne peut apparaître plus d'une fois parmi \(S_1, \ldots, S_k\) que si son cardinal est inférieur à \(3\), auquel cas sa contribution à la somme \(\sum_{i=1}^{k}(\lvert S_i \rvert - n)\) est négative ou nulle (puisque \(n \geq 2\)).
La preuve se fait par récurrence sur \(n\). Dans le cas de base \(n = 2\), on a des parties \(S_i\) de \(\{1, 2, 3, 4\}\). D'après la remarque ci-dessus, il suffit de considérer celles de cardinal \(3\) et \(4\) ; chacune apparaît au plus une fois parmi \(S_1, \ldots, S_k\). Si \(S_i = \{1, 2, 3, 4\}\) pour un certain \(i\), alors aucun \(S_j\) n'est une partie à \(3\) éléments, d'après la condition ; donc \(\sum_{i=1}^{k}(\lvert S_i \rvert - 2) \leq 2\). D'après la condition encore, il est impossible d'avoir \(S_i = \{1, 3, 4\}\) et \(S_j = \{2, 3, 4\}\) pour certains \(i\), \(j\). Donc, si \(\lvert S_i \rvert \leq 3\) pour tout \(i\), au plus \(3\) termes \(\lvert S_i \rvert - 2\) sont strictement positifs, correspondant à des parties à \(3\) éléments. Cela implique \(\sum_{i=1}^{k}(\lvert S_i \rvert - 2) \leq 3\), et la conclusion est donc vraie pour \(n = 2\).
Supposons l'affirmation vraie pour un certain \(n \geq 2\), et soient des ensembles \(S_1, \ldots, S_k \subseteq \{1, 2, \ldots, 2^{n+1}\}\) vérifiant la propriété donnée. Notons \(U_i = S_i \cap \{1, 2, \ldots, 2^n\}\), \(V_i = S_i \cap \{2^n + 1, \ldots, 2^{n+1}\}\). Posons
Les ensembles \(S_j\) avec \(j \in J\) sont tous contenus dans \(\{2^n + 1, \ldots, 2^{n+1}\}\), donc l'hypothèse de récurrence s'applique à leurs translatés \(-2^n + S_j\), qui ont les mêmes cardinaux. Cela donne \(\sum_{j \in J}(\lvert S_j \rvert - n) \leq (2n - 1)2^{n-2}\), de sorte que
Pour \(i \in I\), notons \(v_i\) le plus petit élément de \(V_i\). Remarquons que si \(V_a\) et \(V_b\) se coupent, avec \(a < b\), \(a, b \in I\), alors \(v_a\) est leur unique élément commun. En effet, soient \(z \in V_a \cap V_b \subseteq S_a \cap S_b\) et \(m\) le plus petit élément de \(S_b\). Comme \(b \in I\), on a \(m \leq 2^n\). D'après la condition, il n'y a aucun élément de \(S_a\) strictement entre \(m \leq 2^n\) et \(z > 2^n\), ce qui implique \(z = v_a\).
Il s'ensuit que si l'on retire l'élément \(v_i\) de chaque \(V_i\), on obtient une famille d'ensembles deux à deux disjoints \(W_i = V_i \setminus \{v_i\}\), \(i \in I\) (on pose \(W_i = \varnothing\) si \(V_i = \varnothing\)). Comme \(W_i \subseteq \{2^n + 1, \ldots, 2^{n+1}\}\) pour tout \(i\), on en déduit \(\sum_{i \in I}\lvert W_i \rvert \leq 2^n\). Donc \(\sum_{i \in I}(\lvert V_i \rvert - 1) \leq \sum_{i \in I}\lvert W_i \rvert \leq 2^n\).
D'autre part, l'hypothèse de récurrence s'applique directement aux ensembles \(U_i\), \(i \in I\), de sorte que \(\sum_{i \in I}(\lvert U_i \rvert - n) \leq (2n - 1)2^{n-2}\). En résumé,
Les estimations (1) et (2) suffisent pour terminer l'hérédité :
Revenons au problème et considérons \(k = 2^n\) parties \(S_1, S_2, \ldots, S_{2^n}\) de \(\{1, 2, 3, \ldots, 2^{n+1}\}\). Si elles vérifient la condition donnée, l'affirmation implique \(\sum_{i=1}^{2^n}(\lvert S_i \rvert - (n + 1)) \leq (2n + 1)2^{n-1}\). En moyennant de nouveau, on voit que le plus petit ensemble a au plus \(2n + 1\) éléments. \(\blacksquare\)
Remarque¶
Il peut arriver que chaque ensemble \(S_i\) ait au moins \(n + 1\) éléments. Voici un exemple du proposant.
Pour \(i = 1, \ldots, 2^n\), posons \(S_i = \{i + 2^k \mid 0 \leq k \leq n\}\). Alors \(\lvert S_i \rvert = n + 1\) pour tout \(i\). Supposons qu'il existe \(a < b\) et \(x < y < z\) tels que \(y, z \in S_a\) et \(x, z \in S_b\). Alors \(z = a + 2^k = b + 2^l\) pour certains \(k > l\). Comme \(y \in S_a\) et \(y < z\), on a \(y \leq a + 2^{k-1}\). L'élément \(x \in S_b\) vérifie donc
Mais le plus petit élément de \(S_b\) est \(b + 1\), ce qui est une contradiction.