Aller au contenu

Shortlist 2018, A3

Domaine : Algèbre · Difficulté : ★★☆☆☆ · Proposé par : Luxembourg

Concepts : Partie entière et majorations

Solution officielle : Shortlist officielle 2018 (avec solutions), p. 12 (page 14 du PDF)

Énoncé

Given any set \(S\) of positive integers, show that at least one of the following two assertions holds:

(1) There exist distinct finite subsets \(F\) and \(G\) of \(S\) such that \(\sum_{x \in F} 1/x = \sum_{x \in G} 1/x\);

(2) There exists a positive rational number \(r < 1\) such that \(\sum_{x \in F} 1/x \neq r\) for all finite subsets \(F\) of \(S\).

Indices : les idées clés
  • Raisonner par l'absurde sur l'unicité (solution 1) : si (1) et (2) sont fausses, chaque rationnel \(r \in [0, 1)\) s'écrit de façon unique \(\sum_{x \in F_r} 1/x\).
  • Lemme d'alternance (solution 1) : si \(q - r = 1/x\), alors \(x \in F_q \iff x \notin F_r\).
  • Partie entière et majorations (solution 1) : on en déduit \(x \in F_r \iff \lfloor rx \rfloor\) est impair, puis on compare \(F_{2/3}\) et \(F_{2/3 - \varepsilon}\).
  • Majoration par une série géométrique (solution 2) : si \(x_{n+1} \geq 2x_n\) pour tout \(n\), les sommes restent sous \(2/x_1\) ; sinon \(\frac{1}{x_n} - \frac{1}{x_{n+1}} < \frac{1}{x_{n+1}}\) fournit soit une valeur manquée, soit deux représentations.
Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2018 (deux solutions et une remarque).

Solution 1

On raisonne par l'absurde : supposons que ni (1) ni (2) ne soit vérifiée. Convenons, comme d'habitude, qu'une somme vide vaut \(0\), afin de considérer les rationnels de \([0, 1)\) ; ajouter \(0\) ne pose pas de problème, puisque \(\sum_{x \in F} 1/x = 0\) pour aucune partie finie non vide \(F\) de \(S\). Pour tout rationnel \(r \in [0, 1)\), soit alors \(F_r\) l'unique partie finie de \(S\) telle que \(\sum_{x \in F_r} 1/x = r\). L'argument repose sur le lemme suivant.

Lemme. Si \(x \in S\) et si \(q, r\) sont des rationnels de \([0, 1)\) tels que \(q - r = 1/x\), alors \(x \in F_q\) si et seulement si \(x \notin F_r\).

Preuve. Si \(x \in F_q\), alors

\[\sum_{y \in F_q \setminus \{x\}} \frac{1}{y} = \sum_{y \in F_q} \frac{1}{y} - \frac{1}{x} = q - \frac{1}{x} = r = \sum_{y \in F_r} \frac{1}{y},\]

donc \(F_r = F_q \setminus \{x\}\), et \(x \notin F_r\). Réciproquement, si \(x \notin F_r\), alors

\[\sum_{y \in F_r \cup \{x\}} \frac{1}{y} = \sum_{y \in F_r} \frac{1}{y} + \frac{1}{x} = r + \frac{1}{x} = q = \sum_{y \in F_q} \frac{1}{y},\]

donc \(F_q = F_r \cup \{x\}\), et \(x \in F_q\). \(\square\)

Soient maintenant \(x \in S\) et \(r\) un rationnel strictement positif, \(r < 1\). Posons \(n = \lfloor rx \rfloor\) (partie entière) et considérons les ensembles \(F_{r - k/x}\), \(k = 0, \ldots, n\). Comme \(0 \leq r - n/x < 1/x\), l'ensemble \(F_{r - n/x}\) ne contient pas \(x\) (sinon sa somme serait au moins \(1/x\)), et une application répétée du lemme montre que les \(F_{r - (n-2k)/x}\) ne contiennent pas \(x\), tandis que les \(F_{r - (n-2k-1)/x}\) le contiennent. Par conséquent, \(x \in F_r\) si et seulement si \(n = \lfloor rx \rfloor\) est impair.

Considérons enfin \(F_{2/3}\). D'après ce qui précède, \(\lfloor 2x/3 \rfloor\) est impair pour tout \(x \in F_{2/3}\), donc \(2x/3\) n'est pas entier. (Précision ajoutée : si \(2x/3 = m\) était un entier impair, \(2x = 3m\) serait impair.) Comme \(F_{2/3}\) est fini, il existe un rationnel \(\varepsilon > 0\) tel que \(\lfloor (2/3 - \varepsilon)x \rfloor = \lfloor 2x/3 \rfloor\) pour tout \(x \in F_{2/3}\). Ainsi tout élément de \(F_{2/3}\) appartient à \(F_{2/3 - \varepsilon}\), c'est-à-dire \(F_{2/3} \subseteq F_{2/3 - \varepsilon}\), ce qui est impossible puisque la somme sur \(F_{2/3 - \varepsilon}\) vaudrait alors au moins \(2/3\). \(\blacksquare\)

Solution 2

Un ensemble \(S\) fini vérifie clairement (2) ; supposons donc \(S\) infini. Si \(S\) ne vérifie aucune des deux conditions, \(S \setminus \{1\}\) non plus. On peut donc supposer que \(S\) est formé d'entiers supérieurs à \(1\). Rangeons ses éléments dans l'ordre croissant : \(x_1 < x_2 < \cdots\), avec \(x_1 \geq 2\).

Cas où \(x_{n+1} \geq 2x_n\) pour tout \(n\). Montrons que \(S\) vérifie (2). On a \(x_n \geq 2^{n-1} x_1\) pour tout \(n\), donc

\[s = \sum_{n \geq 1} \frac{1}{x_n} \leq \sum_{n \geq 1} \frac{1}{2^{n-1} x_1} = \frac{2}{x_1}.\]

Si \(x_1 \geq 3\), ou si \(x_1 = 2\) et \(x_{n+1} > 2x_n\) pour un certain \(n\), alors \(\sum_{x \in F} 1/x < s < 1\) pour toute partie finie \(F\) de \(S\), donc \(S\) vérifie (2). Si \(x_1 = 2\) et \(x_{n+1} = 2x_n\) pour tout \(n\), c'est-à-dire \(x_n = 2^n\) pour tout \(n\), alors toute partie finie \(F\) de \(S\) est formée de puissances de \(2\), donc \(\sum_{x \in F} 1/x \neq 1/3\), et \(S\) vérifie encore (2).

Cas où \(x_{n+1} < 2x_n\) pour un certain \(n\). Considérons le rationnel positif

\[r = \frac{1}{x_n} - \frac{1}{x_{n+1}} < \frac{1}{x_{n+1}}.\]

Si \(r = \sum_{x \in F} 1/x\) pour aucune partie finie \(F\) de \(S\), alors \(S\) vérifie (2). Supposons maintenant que \(r = \sum_{x \in F_0} 1/x\) pour une partie finie \(F_0\) de \(S\) ; montrons que \(S\) vérifie (1). Comme \(\sum_{x \in F_0} 1/x = r < 1/x_{n+1}\), l'élément \(x_{n+1}\) n'appartient pas à \(F_0\), donc

\[\sum_{x \in F_0 \cup \{x_{n+1}\}} \frac{1}{x} = \sum_{x \in F_0} \frac{1}{x} + \frac{1}{x_{n+1}} = r + \frac{1}{x_{n+1}} = \frac{1}{x_n}.\]

Par conséquent, \(F = F_0 \cup \{x_{n+1}\}\) et \(G = \{x_n\}\) sont deux parties finies distinctes de \(S\) telles que \(\sum_{x \in F} 1/x = \sum_{x \in G} 1/x\), et \(S\) vérifie (1). \(\blacksquare\)

Remarques

Remarque 1. La solution 1 s'adapte pour montrer que l'énoncé reste vrai si l'on remplace la condition \(r < 1\) dans (2) par \(r < \delta\), pour un \(\delta > 0\) arbitraire. Il en découle que, si \(S\) ne vérifie pas (1), il existe une infinité de rationnels positifs \(r < 1\) tels que \(\sum_{x \in F} 1/x \neq r\) pour toute partie finie \(F\) de \(S\).