Shortlist 2015, C6¶
Domaine : Combinatoire · Difficulté : ★★★★☆ · Proposé par : U.S.A.
Concepts : Principe extrémal · Bijections et dénombrement
Solution officielle : Shortlist officielle 2015 (avec solutions), p. 35 (page 36 du PDF)
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
Let \(S\) be a nonempty set of positive integers. We say that a positive integer \(n\) is clean if it has a unique representation as a sum of an odd number of distinct elements from \(S\). Prove that there exist infinitely many positive integers that are not clean.
Indices : les idées clés
- Représentations paires et impaires : en supposant que presque tout entier est propre, on montre que tout entier a au plus une représentation impaire et au plus une représentation paire (ajouter un ou deux grands éléments de \(S\)), puis que presque tout entier a exactement une de chaque.
- Principe extrémal (solution 1) : la représentation paire de \(s_i\) contient tous les \(s_k, \ldots, s_{i-1}\) ; en choisissant l'indice \(p\) où le « reste » \(R_p\) est minimal, on obtient \(s_{p+1} \geq 2s_p\), et la représentation paire de \(2s_p\) fournit une contradiction.
- Bijections et dénombrement (solution 2) : les \(2^{n-1}\) sous-ensembles impairs de \(\{s_1, \ldots, s_n\}\) ont des sommes distinctes, ce qui encadre \(s_{n+1}\) et \(\sigma_{n+1}\) ; le passage au complémentaire donne les symétries \(E_{2n} = \sigma_{2n} - E_{2n}\), \(O_{2n+1} = \sigma_{2n+1} - E_{2n+1}\), etc.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2015 (deux solutions).
Solution 1¶
Une représentation impaire (resp. paire) de \(n\) est une écriture de \(n\) comme somme d'un nombre impair (resp. pair) d'éléments distincts de \(S\). Supposons par l'absurde qu'il n'y ait qu'un nombre fini d'entiers non propres : il existe \(N\) tel que tout \(n > N\) ait exactement une représentation impaire. Clairement, \(S\) est infini.
Propriété 1. Tout entier \(n \geq 1\) a au plus une représentation impaire et au plus une représentation paire.
Preuve. Comme \(S\) est infini, il existe \(x \in S\) avec \(x > \max\{n, N\}\). Alors \(n + x\) est propre, et \(x\) n'apparaît dans aucune représentation paire de \(n\). Si \(n\) avait deux représentations paires, en leur ajoutant \(x\) on obtiendrait deux représentations impaires distinctes de \(n + x\) : impossible. De même, en prenant \(y \neq z\) dans \(S\) avec \(y, z > \max\{n, N\}\), deux représentations impaires de \(n\) donneraient, en ajoutant \(y\) et \(z\), deux représentations impaires distinctes de \(n + y + z\). \(\square\)
Propriété 2. Soit \(s \in S\) et \(n > N\) sans représentation paire. Alors \(n + 2as\) a une représentation paire contenant \(s\) pour tout entier \(a \geq 1\).
Preuve. Par récurrence, il suffit de montrer : si \(n > N\) n'a pas de représentation paire sans \(s\), alors \(n + 2s\) a une représentation paire contenant \(s\) (et donc, par la propriété 1, aucune sans \(s\)). La représentation impaire de \(n + s\) ne contient pas \(s\) : sinon, en retirant \(s\), on aurait une représentation paire de \(n\) sans \(s\). En lui ajoutant \(s\), on obtient une représentation paire de \(n + 2s\) contenant \(s\). \(\square\)
Propriété 3. Tout entier assez grand a une représentation paire.
Preuve. Fixons \(s \in S\) et \(r \in \{1, 2, \ldots, 2s\}\). D'après la propriété 2, l'ensemble \(Z_r = \{r + 2as : a \geq 0\}\) contient au plus un entier \(> N\) sans représentation paire. Donc \(Z_r\) ne contient qu'un nombre fini d'entiers sans représentation paire, et il en est de même de \(\mathbb{Z}_{>0} = \bigcup_{r=1}^{2s} Z_r\). \(\square\)
D'après les propriétés 1 et 3, quitte à augmenter \(N\), tout \(n > N\) a exactement une représentation impaire et exactement une représentation paire. En particulier, tout élément \(s > N\) de \(S\) a une représentation paire.
Propriété 4. Pour \(s, t \in S\) avec \(N < s < t\), la représentation paire de \(t\) contient \(s\).
Preuve. Sinon, \(s + t\) aurait deux représentations impaires : l'une obtenue en ajoutant \(s\) à la représentation paire de \(t\), l'autre en ajoutant \(t\) à la représentation paire de \(s\). Cette dernière ne contient pas \(s\) (une représentation paire de \(s\) n'utilise que des éléments \(< s\)), alors que la première le contient : elles sont distinctes, contradiction. \(\square\)
Soient \(s_1 < s_2 < \cdots\) les éléments de \(S\) et \(\sigma_n = \sum_{i=1}^{n} s_i\) (avec \(\sigma_0 = 0\)). Fixons \(k\) tel que \(s_k > N\). Pour tout \(i > k\), la propriété 4 montre que la représentation paire de \(s_i\) (dont tous les termes sont \(< s_i\)) contient \(s_k, s_{k+1}, \ldots, s_{i-1}\). Donc
où \(R_i\) est une somme de certains des \(s_1, \ldots, s_{k-1}\) ; en particulier \(0 \leq R_i \leq \sigma_{k-1}\).
Soit \(j_0 > k\) tel que \(\sigma_{j_0} > 2\sigma_{k-1}\). D'après (1), pour tout \(j \geq j_0\),
Précision ajoutée : le livret énonce (2) pour \(j > j_0\), mais la même preuve vaut pour \(j = j_0\), ce qui est utilisé plus bas avec \(j = p - 1\).
Soit maintenant \(p > j_0\) un indice tel que \(R_p = \min_{i > j_0} R_i\) (principe extrémal : les \(R_i\) ne prennent qu'un nombre fini de valeurs). Alors
Il n'y a donc aucun élément de \(S\) strictement entre \(s_p\) et \(2s_p\). La représentation paire \(\tau\) de \(2s_p\) ne contient donc aucun élément plus grand que \(s_p\) (le seul candidat serait \(2s_p\) lui-même, mais il formerait à lui seul une représentation impaire). D'autre part, (2) donne \(2s_p > s_1 + \cdots + s_{p-1}\), donc \(\tau\) contient un terme plus grand que \(s_{p-1}\) : c'est \(s_p\). En retirant \(s_p\) de \(\tau\), on obtient une représentation impaire de \(s_p\) ne contenant pas \(s_p\) ; comme \(s_p\) seul en est une autre, cela contredit la propriété 1. \(\blacksquare\)
Solution 2¶
On utilise aussi la propriété 1 de la solution 1. Toutes les sommes considérées sont des sommes d'éléments distincts de \(S\) ; une somme est paire ou impaire selon la parité de son nombre de termes. Les intervalles désignent des ensembles d'entiers, par exemple \([a, b] = \{x \in \mathbb{Z} : a \leq x \leq b\}\). Soient \(s_1 < s_2 < \cdots\) les éléments de \(S\), \(\sigma_n = \sum_{i=1}^n s_i\), et \(O_n\) (resp. \(E_n\)) l'ensemble des nombres qui sont somme impaire (resp. paire) d'éléments de \(\{s_1, \ldots, s_n\}\), avec \(0 \in E_n\) (somme vide). On pose \(E = \bigcup_n E_n\) et \(O = \bigcup_n O_n\).
Supposons par l'absurde qu'il n'y ait qu'un nombre fini d'entiers non propres, et notons \(m - 1\) leur nombre. Clairement \(S\) est infini, et par la propriété 1, tout entier positif a au plus une représentation impaire et au plus une paire.
Étape 1 : encadrement de \(s_{n+1}\) et \(\sigma_{n+1}\). Majorations. La propriété 1 donne \(|O_n| = |E_n| = 2^{n-1}\) (des sous-ensembles distincts ont des sommes distinctes), donc \(\big|[1, 2^{n-1} + m] \setminus O_n\big| \geq m\). Il existe ainsi un entier propre \(x_n \in [1, 2^{n-1} + m] \setminus O_n\) ; sa représentation impaire contient un terme plus grand que \(s_n\), donc \(s_{n+1} \leq x_n \leq 2^{n-1} + m\). Par ailleurs, tout entier propre est \(\geq s_1\), donc \(1, \ldots, s_1 - 1\) sont non propres et \(\sigma_1 = s_1 \leq m\). D'où
estimation valable aussi pour \(n = 0\).
Minorations. Comme \(O_{n+1} \subseteq [1, \sigma_{n+1}]\), on a \(\sigma_{n+1} \geq |O_{n+1}| = 2^n\). Puis \(s_{n+1} = \sigma_{n+1} - \sigma_n \geq 2^n - (2^{n-1} - 1 + nm) = 2^{n-1} + 1 - nm\). En résumé, pour tout \(n \geq 1\),
Étape 2 : tout entier assez grand a une représentation paire. Pour un entier \(x\) et un ensemble \(Y\), notons \(x \pm Y = \{x \pm y : y \in Y\}\). Par la propriété 1,
(réunions disjointes). De plus \(s_{n+2} \geq 2^n + 1 - (n+1)m > 2^{n-1} - 1 + nm \geq \sigma_n\) pour \(n\) assez grand.
Affirmation 1. Pour \(n\) assez grand, \((\sigma_n - s_{n+1}, s_{n+2} - s_{n+1}) \subseteq E_n\).
Preuve. Pour \(n\) assez grand, tous les éléments de \((\sigma_n, s_{n+2})\) sont propres, donc dans \(O\). Ils ne sont ni dans \(O_n \subseteq [0, \sigma_n]\), ni dans \(O \setminus O_{n+1}\) (dont les éléments ont un terme \(\geq s_{n+2}\)). Donc \((\sigma_n, s_{n+2}) \subseteq O_{n+1} \setminus O_n = s_{n+1} + E_n\). \(\square\)
Avec (3), pour \(n\) assez grand,
Ces intervalles recouvrent tous les entiers assez grands, donc \(\mathbb{Z}_{\geq 0} \setminus E\) est fini. Comme \(\mathbb{Z}_{\geq 0} \setminus O\) l'est aussi, il existe (propriété 1) un entier \(N\) tel que tout \(n > N\) ait exactement une représentation paire et une impaire.
Étape 3 : structure de \(E_n\) et \(O_n\). Si \(z \in E_{2n}\), le complémentaire de sa représentation dans \(\{s_1, \ldots, s_{2n}\}\) est aussi de cardinal pair, donc \(\sigma_{2n} - z \in E_{2n}\). En raisonnant ainsi (passage au complémentaire) :
Affirmation 2. Pour \(n\) assez grand, \([0, \sigma_n] \supseteq O_n \supseteq (N, \sigma_n - N)\) et \([0, \sigma_n] \supseteq E_n \supseteq (N, \sigma_n - N)\).
Preuve. Les inclusions dans \([0, \sigma_n]\) sont claires. Pour \(n\) assez grand, \(s_{n+1} \geq 2^{n-1} + 1 - nm > \frac{1}{2}(2^{n-1} - 1 + nm) \geq \frac{\sigma_n}{2}\). La représentation impaire d'un élément de \((N, \sigma_n/2]\) ne peut donc pas contenir de terme plus grand que \(s_n\) : \((N, \sigma_n/2] \subseteq O_n\). De même, comme \(s_{n+1} + s_1 > \sigma_n/2\) (une représentation paire non vide a au moins deux termes), \((N, \sigma_n/2] \subseteq E_n\). Les relations (4) donnent alors, pour \(n\) assez grand, \((N, \sigma_n - N) \subseteq O_n\) et \((N, \sigma_n - N) \subseteq E_n\). \(\square\)
Étape 4 : contradiction. On a \(0 \notin O\) et \(1 \notin E\) (une somme paire non vide vaut au moins \(s_1 + s_2 \geq 3\)), donc \(\mathbb{Z}_{\geq 0} \setminus O\) et \(\mathbb{Z}_{\geq 0} \setminus E\) sont non vides et finis. Posons \(o = \max(\mathbb{Z}_{\geq 0} \setminus O)\) et \(e = \max(\mathbb{Z}_{\geq 0} \setminus E)\) ; on a \(e, o \leq N\). Prenons \(k\) assez grand pour que \(\sigma_{2k} > 2N\) et que l'affirmation 2 vaille pour tout \(n \geq 2k\). D'après (4) et l'affirmation 2, \(\sigma_{2k} - e\) est le plus petit entier \(> N\) qui n'est pas dans \(E_{2k}\) ; c'est donc le plus petit élément de \(E \setminus E_{2k}\), à savoir \(s_{2k+1} + s_1\). De même,
Par conséquent
ce qui est impossible puisque \(s_1 > 0\). \(\blacksquare\)