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é

Soit \(S\) un ensemble quelconque d'entiers strictement positifs. Montrer que l'une au moins des deux assertions suivantes est vraie :

(1) il existe des parties finies distinctes \(F\) et \(G\) de \(S\) telles que \(\sum_{x \in F} 1/x = \sum_{x \in G} 1/x\) ;

(2) il existe un nombre rationnel \(r\) strictement positif avec \(r < 1\) tel que \(\sum_{x \in F} 1/x \neq r\) pour toute partie finie \(F\) de \(S\).

Énoncé original (anglais)

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

Problèmes voisins

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

  • 2024 A1 ★☆☆☆☆ · OIM P1 : Pour quels réels \(\alpha\) la somme \(\lfloor \alpha \rfloor + \cdots + \lfloor n\alpha \rfloor\) est-elle toujours un multiple de \(n\) ?
  • 2021 A3 ★★☆☆☆ : Minimiser \(\lfloor a_1/1 \rfloor + \cdots + \lfloor a_n/n \rfloor\) sur les permutations de \(1, \ldots, n\).
  • 2006 A1 ★★☆☆☆ : La suite \(a_{i+1} = \lfloor a_i \rfloor \cdot \langle a_i \rangle\) finit par être périodique de période \(2\).
  • 2024 N5 ★★★☆☆ : Avec les entiers dont les facteurs premiers sont dans \(S\), on peut presque toujours atteindre l'arrondi supérieur de la somme de leurs inverses.