Shortlist 2024, A1

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

Concepts : Partie entière et majorations · Récurrence et constructions récursives · Congruences, théorèmes de Fermat et d'Euler

Solution officielle : Shortlist officielle 2024 (avec solutions), section A1 (livret PDF)

Problème 1 de l'OIM 2024

Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2024, où il était le problème 1 (jour 1).

Énoncé

Determine all real numbers \(\alpha\) such that the number

\[\lfloor \alpha \rfloor + \lfloor 2\alpha \rfloor + \cdots + \lfloor n\alpha \rfloor\]

is a multiple of \(n\) for every positive integer \(n\). (Here \(\lfloor z \rfloor\) denotes the greatest integer less than or equal to \(z\).)

Indices : les idées clés

• Partie entière et majorations : écrire \(\alpha = k + \epsilon\), ou se ramener à \(0 \leq \alpha < 2\) (ajouter un entier pair ne change rien), puis encadrer \(\lfloor n\alpha \rfloor\).
• Récurrence (solutions 1 et 3) : une récurrence forte détermine \(\lfloor n\epsilon \rfloor\), ou \(\lfloor \alpha \rfloor + \cdots + \lfloor n\alpha \rfloor\), pour tout \(n\).
• Congruences (solution 2) : \(S_n \equiv 0 \pmod n\) et \(S_n \equiv \lfloor n\alpha \rfloor \pmod{n-1}\) se combinent, car \(n\) et \(n-1\) sont premiers entre eux.
• Suite d'entiers strictement croissante (solution 4) : les moyennes \(b_n = S_n / n\) croissent d'au moins \(1\), ce qui est trop rapide.

Solutions

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

Réponse. Les réels \(\alpha\) qui conviennent sont exactement les entiers pairs.

Solution 1

Les entiers pairs conviennent. Si \(\alpha = 2m\) avec \(m\) entier,

\[\lfloor \alpha \rfloor + \lfloor 2\alpha \rfloor + \cdots + \lfloor n\alpha \rfloor = 2m + 4m + \cdots + 2mn = mn(n+1),\]

qui est un multiple de \(n\).

Ce sont les seuls. Écrivons \(\alpha = k + \epsilon\) avec \(k\) entier et \(0 \leq \epsilon < 1\). Le nombre

\[\lfloor \alpha \rfloor + \cdots + \lfloor n\alpha \rfloor = (k + \lfloor \epsilon \rfloor) + (2k + \lfloor 2\epsilon \rfloor) + \cdots + (nk + \lfloor n\epsilon \rfloor) = \frac{kn(n+1)}{2} + \lfloor \epsilon \rfloor + \lfloor 2\epsilon \rfloor + \cdots + \lfloor n\epsilon \rfloor\]

doit être un multiple de \(n\). On distingue deux cas selon la parité de \(k\).

Cas 1 : \(k\) pair. Alors \(\frac{kn(n+1)}{2}\) est un multiple de \(n\), donc \(\lfloor \epsilon \rfloor + \lfloor 2\epsilon \rfloor + \cdots + \lfloor n\epsilon \rfloor\) aussi. Montrons par récurrence forte que \(\lfloor n\epsilon \rfloor = 0\) pour tout \(n \geq 1\). Pour \(n = 1\), cela vient de \(0 \leq \epsilon < 1\). Si \(\lfloor m\epsilon \rfloor = 0\) pour tout \(1 \leq m < n\), alors \(\lfloor \epsilon \rfloor + \cdots + \lfloor n\epsilon \rfloor = \lfloor n\epsilon \rfloor\) doit être un multiple de \(n\) ; comme \(0 \leq n\epsilon < n\), on a \(\lfloor n\epsilon \rfloor = 0\).

L'égalité \(\lfloor n\epsilon \rfloor = 0\) signifie \(0 \leq \epsilon < \frac{1}{n}\). Comme c'est vrai pour tout \(n\), \(\epsilon = 0\), et \(\alpha\) est un entier pair.

Cas 2 : \(k\) impair. Montrons par récurrence forte que \(\lfloor n\epsilon \rfloor = n - 1\) pour tout \(n \geq 1\). Le cas \(n = 1\) découle à nouveau de \(0 \leq \epsilon < 1\). Si \(\lfloor m\epsilon \rfloor = m - 1\) pour tout \(1 \leq m < n\), le nombre

\[\begin{aligned} \frac{kn(n+1)}{2} + \lfloor \epsilon \rfloor + \cdots + \lfloor n\epsilon \rfloor &= \frac{kn(n+1)}{2} + 0 + 1 + \cdots + (n-2) + \lfloor n\epsilon \rfloor \\ &= \frac{kn(n+1)}{2} + \frac{(n-2)(n-1)}{2} + \lfloor n\epsilon \rfloor \\ &= \frac{k+1}{2} n^2 + \frac{k-3}{2} n + 1 + \lfloor n\epsilon \rfloor \end{aligned}\]

doit être un multiple de \(n\). Comme \(k\) est impair, \(\frac{k+1}{2}\) et \(\frac{k-3}{2}\) sont entiers, donc \(n\) doit diviser \(1 + \lfloor n\epsilon \rfloor\). Comme \(0 \leq n\epsilon < n\), on obtient \(\lfloor n\epsilon \rfloor = n - 1\).

Cela implique \(1 - \frac{1}{n} \leq \epsilon < 1\) pour tout \(n\), ce qui est absurde. Il n'y a donc pas d'autre solution dans ce cas. \(\blacksquare\)

Solution 2

Comme dans la solution 1, les entiers pairs conviennent. Ajouter un entier pair \(2m\) à \(\alpha\) ajoute \(mn(n+1)\) à la somme, donc on peut supposer \(0 \leq \alpha < 2\). Posons \(S_n = \lfloor \alpha \rfloor + \lfloor 2\alpha \rfloor + \cdots + \lfloor n\alpha \rfloor\). Pour \(n \geq 2\),

\[S_n \equiv 0 \pmod n, \tag{1}\]

\[S_n \equiv S_n - S_{n-1} = \lfloor n\alpha \rfloor \pmod{n-1}. \tag{2}\]

Comme \(\gcd(n, n-1) = 1\), (1) et (2) entraînent

\[S_n \equiv n \lfloor n\alpha \rfloor \pmod{n(n-1)}. \tag{3}\]

De plus,

\[0 \leq n\lfloor n\alpha \rfloor - S_n = \sum_{k=1}^{n} \big(\lfloor n\alpha \rfloor - \lfloor k\alpha \rfloor\big) < \sum_{k=1}^{n} (n\alpha - k\alpha + 1) = \frac{n(n-1)}{2}\alpha + n. \tag{4}\]

Pour \(n\) assez grand, le membre de droite de (4) est inférieur à \(n(n-1)\) (car \(\alpha < 2\)). Alors (3) impose

\[0 = n\lfloor n\alpha \rfloor - S_n = \sum_{k=1}^{n} \big(\lfloor n\alpha \rfloor - \lfloor k\alpha \rfloor\big) \tag{5}\]

pour \(n\) assez grand. Comme \(\lfloor n\alpha \rfloor - \lfloor k\alpha \rfloor \geq 0\) pour \(1 \leq k \leq n\), (5) montre que toutes ces différences sont nulles ; en particulier \(\lfloor \alpha \rfloor = \lfloor n\alpha \rfloor\) pour tout \(n\) assez grand, ce qui est absurde sauf si \(\alpha = 0\). \(\blacksquare\)

Solution 3

Comme dans les autres solutions, on peut supposer \(0 \leq \alpha < 2\) ; les entiers pairs conviennent, donc on suppose \(0 < \alpha < 2\) et l'on cherche une contradiction. Montrons par récurrence sur \(n\) que, simultanément,

\[\lfloor \alpha \rfloor + \lfloor 2\alpha \rfloor + \cdots + \lfloor n\alpha \rfloor = n^2 \tag{6}\]

\[\text{et} \quad \frac{2n-1}{n} \leq \alpha < 2. \tag{7}\]

Initialisation (\(n = 1\)). Si \(\alpha < 1\), considérons \(m = \left\lceil \frac{1}{\alpha} \right\rceil > 1\) ; alors \(\lfloor \alpha \rfloor + \lfloor 2\alpha \rfloor + \cdots + \lfloor m\alpha \rfloor = 1\) n'est pas un multiple de \(m\). Donc \(\alpha \geq 1\), ce qui est (7) ; ainsi \(\lfloor \alpha \rfloor = 1\) et (6) est vraie.

Hérédité. Supposons (6) et (7) vraies pour \(n\). D'après (7),

\[2n + 1 - \frac{1}{n} \leq (n+1)\alpha < 2n + 2.\]

Donc

\[n^2 + 2n \leq \lfloor \alpha \rfloor + \cdots + \lfloor n\alpha \rfloor + \lfloor (n+1)\alpha \rfloor = n^2 + \lfloor (n+1)\alpha \rfloor < n^2 + 2n + 2.\]

Pour obtenir un multiple de \(n+1\), il faut nécessairement \(\lfloor (n+1)\alpha \rfloor = 2n + 1\) et

\[\lfloor \alpha \rfloor + \cdots + \lfloor (n+1)\alpha \rfloor = (n+1)^2.\]

Ces deux égalités donnent respectivement (7) et (6) au rang \(n+1\).

Enfin, (7) vraie pour tout \(n\) donne \(\alpha \geq 2\), contradiction. \(\blacksquare\)

Solution 4

Comme dans les autres solutions, on suppose \(0 < \alpha < 2\) et l'on cherche une contradiction. Pour tout \(n\), posons

\[b_n = \frac{\lfloor \alpha \rfloor + \lfloor 2\alpha \rfloor + \cdots + \lfloor n\alpha \rfloor}{n},\]

qui est un entier positif ou nul d'après l'hypothèse. Pour tout \(n > \frac{1}{\alpha}\), on a

\[\lfloor (n+1)\alpha \rfloor \geq \lfloor \alpha \rfloor, \lfloor 2\alpha \rfloor, \ldots, \lfloor n\alpha \rfloor \quad \text{et} \quad \lfloor (n+1)\alpha \rfloor > \lfloor \alpha \rfloor.\]

Donc \(\lfloor (n+1)\alpha \rfloor > b_n\), et \((n+1) b_{n+1} = n b_n + \lfloor (n+1)\alpha \rfloor > (n+1) b_n\) : ainsi \(b_{n+1} > b_n\), soit \(b_{n+1} \geq b_n + 1\), pour \(n > \frac{1}{\alpha}\). Par conséquent, il existe un entier fixe \(C\) tel que, pour tous ces \(n\),

\[b_n \geq n + C.\]

D'autre part, par définition,

\[b_n = \frac{\lfloor \alpha \rfloor + \cdots + \lfloor n\alpha \rfloor}{n} \leq \frac{\alpha + 2\alpha + \cdots + n\alpha}{n} = \frac{\alpha}{2}(n+1),\]

ce qui est contradictoire pour \(n\) assez grand, puisque \(\frac{\alpha}{2} < 1\). \(\blacksquare\)

Précision ajoutée : l'étape « \(b_{n+1} > b_n\) » utilise que \(\lfloor (n+1)\alpha \rfloor\) est strictement supérieur à la moyenne \(b_n\) des \(\lfloor k\alpha \rfloor\), \(k \leq n\).

Remarques

Remarque (autre fin pour la solution 2). Par définition, \(S_n \leq \alpha \frac{n(n+1)}{2}\) ; d'autre part, (5) implique \(S_n = n\lfloor n\alpha \rfloor \geq \alpha n^2 - n\) pour tout \(n\) assez grand. Donc \(\alpha n^2 - n \leq \alpha \frac{n(n+1)}{2}\) pour \(n\) grand, ce qui force \(\alpha = 0\).