Aller au contenu

Shortlist 2017, N3

Domaine : Théorie des nombres · Difficulté : ★★☆☆☆ · Proposé par : Thailand

Concepts : Principe des tiroirs · Congruences, théorèmes de Fermat et d'Euler

Solution officielle : Shortlist officielle 2017 (avec solutions), p. 77 (page 79 du PDF)

Énoncé

Determine all integers \(n \geq 2\) with the following property: for any integers \(a_1, a_2, \ldots, a_n\) whose sum is not divisible by \(n\), there exists an index \(1 \leq i \leq n\) such that none of the numbers

\[a_i,\ a_i + a_{i+1},\ \ldots,\ a_i + a_{i+1} + \cdots + a_{i+n-1}\]

is divisible by \(n\). (We let \(a_i = a_{i-n}\) when \(i > n\).)

Indices : les idées clés
  • Réponse : exactement les nombres premiers \(n\).
  • Contre-exemple pour \(n = ab\) composé : \(a_1 = \cdots = a_{n-1} = a\), \(a_n = 0\) ; toute fenêtre de \(b\) ou \(b+1\) termes consécutifs a pour somme \(ab = n\).
  • Principe des tiroirs : parmi \(n+1\) indices construits par récurrence, deux sont congrus modulo \(n\).
  • Congruences, théorèmes de Fermat et d'Euler : la somme entre ces deux indices vaut \(k(a_1 + \cdots + a_n)\) avec \(1 \leq k \leq n-1\), non divisible par le nombre premier \(n\).
Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2017 (une solution).

Réponse : les entiers \(n\) qui conviennent sont exactement les nombres premiers.

Solution

Les entiers composés ne conviennent pas. Soit \(n = ab\) avec \(a, b \geq 2\) entiers. Posons \(a_k = a\) pour \(1 \leq k \leq n-1\) et \(a_n = 0\). La somme \(a_1 + \cdots + a_n = a(n-1)\) n'est pas divisible par \(n\) (précision ajoutée : \(a(n-1) \equiv -a \pmod n\) et \(0 < a < n\)). Soit \(i\) un indice quelconque, \(1 \leq i \leq n\). En prenant \(j = b\) si \(1 \leq i \leq n - b\), et \(j = b + 1\) si \(n - b < i \leq n\), la fenêtre \(a_i, \ldots, a_{i+j-1}\) contient exactement \(b\) termes égaux à \(a\) (précision ajoutée : et éventuellement le terme nul \(a_n\)), donc

\[a_i + a_{i+1} + \cdots + a_{i+j-1} = a \cdot b = n \equiv 0 \pmod n.\]

C'est donc bien un contre-exemple à la propriété.

Les nombres premiers conviennent. Soit \(n\) premier et supposons par l'absurde que la propriété soit fausse. Il existe alors des entiers \(a_1, \ldots, a_n\) de somme non divisible par \(n\) tels que, pour tout \(i\), il existe \(j\), \(1 \leq j \leq n\), avec \(a_i + a_{i+1} + \cdots + a_{i+j-1}\) divisible par \(n\). Nécessairement \(1 \leq j \leq n-1\), puisque \(a_1 + \cdots + a_n\) n'est pas divisible par \(n\).

On construit alors par récurrence des entiers \(0 = i_0 < i_1 < \cdots < i_n\) avec \(i_{s+1} - i_s \leq n-1\) et

\[a_{i_s + 1} + a_{i_s + 2} + \cdots + a_{i_{s+1}} \equiv 0 \pmod n \qquad (0 \leq s \leq n-1)\]

(les indices étant pris modulo \(n\)) : pour \(0 \leq s < n\), on applique l'observation précédente à \(i = i_s + 1\) et on pose \(i_{s+1} = i_s + j\).

Parmi les \(n+1\) indices \(i_0, i_1, \ldots, i_n\), d'après le principe des tiroirs, deux sont congrus modulo \(n\) : il existe \(0 \leq r < s \leq n\) avec \(i_s \equiv i_r \pmod n\), et

\[a_{i_r + 1} + a_{i_r + 2} + \cdots + a_{i_s} = \sum_{j=r}^{s-1} \left(a_{i_j + 1} + \cdots + a_{i_{j+1}}\right) \equiv 0 \pmod n.\]

Comme \(i_s \equiv i_r \pmod n\), on a \(i_s - i_r = kn\) pour un entier \(k \geq 1\) ; et comme \(i_{j+1} - i_j \leq n - 1\), on a \(i_s - i_r \leq (n-1)n\), donc \(k \leq n-1\). Mais alors

\[a_{i_r + 1} + \cdots + a_{i_s} = k(a_1 + a_2 + \cdots + a_n)\]

ne peut pas être multiple de \(n\), puisque \(n\) est premier et que ni \(k\) ni \(a_1 + \cdots + a_n\) ne sont multiples de \(n\). Contradiction. \(\blacksquare\)