Aller au contenu

Shortlist 2021, N6

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

Concepts : Divisibilité, PGCD et algorithme d'Euclide · Congruences, théorèmes de Fermat et d'Euler · Récurrence et constructions récursives

Solution officielle : Shortlist officielle 2021 (avec solutions), p. 76 (page 76 du PDF)

Énoncé

Determine all integers \(n \geq 2\) with the following property: every \(n\) pairwise distinct integers whose sum is not divisible by \(n\) can be arranged in some order \(a_1, a_2, \ldots, a_n\) so that \(n\) divides \(1 \cdot a_1 + 2 \cdot a_2 + \cdots + n \cdot a_n\).

Indices : les idées clés
  • Contre-exemple pour \(n = 2^k a\) (\(a \geq 3\) impair) : des nombres tous congrus à \(1\) modulo \(2^k\) donnent \(\sum i a_i \equiv \frac{n(n+1)}{2} \not\equiv 0 \pmod{2^k}\).
  • PGCD et congruences : par permutation circulaire, il suffit d'obtenir \(\gcd(n, s) \mid \sum i a_i\) (lemme 1).
  • Récurrence et constructions récursives : partition de l'ensemble en paquets de \(k = n/p\) éléments (lemme 2, prouvé par récurrence), puis récurrence sur \(n\) en recollant des permutations des paquets.
Solutions

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

Réponse : tous les entiers impairs et toutes les puissances de \(2\).

Solution

Les autres \(n\) ne conviennent pas. Si \(n = 2^k a\) avec \(a \geq 3\) impair et \(k \geq 1\), considérons un ensemble formé du nombre \(2^k + 1\) et de \(n - 1\) nombres congrus à \(1\) modulo \(n\) (deux à deux distincts). La somme de ces nombres est congrue à \(2^k\) modulo \(n\), donc n'est pas divisible par \(n\) ; et pour toute permutation \((a_1, a_2, \ldots, a_n)\) de ces nombres, comme ils sont tous congrus à \(1\) modulo \(2^k\),

\[1 \cdot a_1 + 2 \cdot a_2 + \cdots + n \cdot a_n \equiv 1 + \cdots + n \equiv 2^{k-1} a (2^k a + 1) \not\equiv 0 \pmod{2^k},\]

et a fortiori \(1 \cdot a_1 + \cdots + n \cdot a_n\) n'est pas divisible par \(n\).

Désormais, \(n\) est impair ou une puissance de \(2\). Soit \(S\) l'ensemble d'entiers donné et \(s\) la somme de ses éléments.

Lemme 1. S'il existe une permutation \((a_i)\) de \(S\) telle que \(\gcd(n, s)\) divise \(\sum_{i=1}^n i a_i\), alors il existe une permutation \((b_i)\) de \(S\) telle que \(n\) divise \(\sum_{i=1}^n i b_i\).

Preuve. Soit \(r = \sum_{i=1}^n i a_i\). Considérons la permutation \((b_i)\) définie par \(b_i = a_{i+x}\), où les indices sont pris modulo \(n\) (\(a_{j+n} = a_j\)). Pour cette permutation,

\[\sum_{i=1}^n i b_i = \sum_{i=1}^n i a_{i+x} \equiv \sum_{i=1}^n (i - x) a_i \equiv r - sx \pmod n.\]

Comme \(\gcd(n, s)\) divise \(r\), la congruence \(r - sx \equiv 0 \pmod n\) admet une solution \(x\). \(\square\)

Lemme 2. Tout ensemble \(T\) de \(km\) entiers, \(m > 1\), peut être partagé en \(m\) ensembles de \(k\) entiers de sorte que, dans chaque ensemble, ou bien la somme des éléments n'est pas divisible par \(k\), ou bien tous les éléments ont le même reste modulo \(k\).

Preuve. Par récurrence sur \(m\).

Cas \(m = 2\). Si \(T\) contient \(k\) éléments de même reste modulo \(k\), on en forme un sous-ensemble \(A\) ; les éléments restants forment \(B\). Si \(k\) ne divise pas la somme des éléments de \(B\), c'est fini. Sinon, il suffit d'échanger un élément quelconque de \(A\) avec un élément de \(B\) qui ne lui est pas congru modulo \(k\) : les sommes de \(A\) et de \(B\) deviennent toutes deux non divisibles par \(k\). Ce n'est impossible que si tous les éléments de \(T\) sont congrus modulo \(k\) ; dans ce cas, toute partition convient.

Si aucun groupe de \(k\) éléments de \(T\) n'a le même reste modulo \(k\), il existe trois éléments \(a, b, c \in T\) de restes deux à deux distincts modulo \(k\). Soit \(t\) la somme des éléments de \(T\). Il suffit de trouver \(A \subset T\) avec \(|A| = k\) et \(\sum_{x \in A} x \not\equiv 0, t \pmod k\) : alors ni la somme des éléments de \(A\) ni celle de \(B = T \setminus A\) n'est divisible par \(k\). Prenons \(U' \subset T \setminus \{a, b, c\}\) avec \(|U'| = k - 1\). Les sommes des éléments des trois ensembles \(U' \cup \{a\}\), \(U' \cup \{b\}\), \(U' \cup \{c\}\) ont trois restes différents modulo \(k\), et l'une au moins n'est congrue ni à \(0\) ni à \(t\).

Cas \(m > 2\). Si \(T\) contient \(k\) éléments de même reste modulo \(k\), on en forme un sous-ensemble \(A\) et on applique l'hypothèse de récurrence aux \(k(m-1)\) éléments restants. Sinon, on choisit un \(U \subset T\) quelconque avec \(|U| = k - 1\). Comme les éléments restants ne peuvent pas être tous congrus modulo \(k\), il existe \(a \in T \setminus U\) tel que \(a \not\equiv -\sum_{x \in U} x \pmod k\). On prend alors \(A = U \cup \{a\}\) et on applique l'hypothèse de récurrence à \(T \setminus A\). \(\square\)

Preuve pour \(n\) impair et \(n = 2^k\). Par récurrence sur \(n\).

Si \(n\) est premier, l'énoncé découle immédiatement du lemme 1, puisqu'alors \(\gcd(n, s) = 1\). Dans le cas général, on trouve un nombre premier \(p\) et un entier \(t\) tels que \(p^t \mid n\) et \(p^t \nmid s\) (possible car \(n \nmid s\)). Par le lemme 2, on peut partager \(S\) en \(p\) ensembles de \(\frac{n}{p} = k\) éléments, de sorte que, dans chaque ensemble, ou bien la somme n'est pas divisible par \(k\) (première catégorie), ou bien tous les éléments ont le même reste modulo \(k\) (seconde catégorie). Notons que \(\gcd(n, s)\) divise \(k\), car \(\nu_p(\gcd(n, s)) < t \leq \nu_p(n)\).

Pour un ensemble de la première catégorie, l'hypothèse de récurrence (appliquée à \(k\), qui est impair ou une puissance de \(2\)) fournit une permutation \((a_i)\) telle que \(k \mid \sum_{i=1}^k i a_i\).

Si \(n\) (et donc \(k\)) est impair, pour toute permutation \((b_i)\) d'un ensemble de la seconde catégorie, on a

\[\sum_{i=1}^k i b_i \equiv b_1 \frac{k(k+1)}{2} \equiv 0 \pmod k.\]

En mettant bout à bout de telles permutations pour tous les ensembles de la partition, on obtient une permutation \((c_i)\) de \(S\) telle que \(k \mid \sum_{i=1}^n i c_i\) (décaler les positions d'un multiple de \(k\) ne change rien modulo \(k\)). Comme cette somme est divisible par \(k\), et que \(k\) est divisible par \(\gcd(n, s)\), le lemme 1 conclut.

Si \(n = 2^s\) (ici \(s\) désigne l'exposant), on a \(p = 2\) et \(k = 2^{s-1}\). Pour chacun des deux sous-ensembles, il existe une permutation \((a_1, \ldots, a_k)\) telle que \(\sum_{i=1}^k i a_i\) soit divisible par \(2^{s-2} = \frac{k}{2}\) : si le sous-ensemble est de la première catégorie, l'expression est même divisible par \(k\), et s'il est de la seconde,

\[\sum_{i=1}^k i a_i \equiv a_1 \frac{k(k+1)}{2} \equiv 0 \pmod{\frac{k}{2}}.\]

On affecte alors aux termes de l'une des permutations tous les coefficients impairs, et à ceux de l'autre tous les coefficients pairs au plus \(n\), dans l'ordre croissant, de sorte que les sommes obtenues soient divisibles par \(k\) :

\[\sum_{i=1}^k (2i-1) a_i \equiv \sum_{i=1}^k 2i a_i \equiv 2 \sum_{i=1}^k i a_i \equiv 0 \pmod k.\]

Précision ajoutée : la première congruence suppose \(\sum a_i \equiv 0 \pmod k\), ce qui est vrai pour un ensemble de la seconde catégorie (\(k\) éléments de même reste modulo \(k\)) ; on place donc aux positions impaires un ensemble de la seconde catégorie s'il y en a un. Si les deux ensembles sont de la première catégorie, leurs sommes \(\sum i a_i\) sont divisibles par \(k\) et il suffit de les placer l'un après l'autre (positions \(1\) à \(k\), puis \(k+1\) à \(2k\)).

En combinant ces deux sommes, on obtient de nouveau une permutation \((c_i)\) de \(S\) telle que \(k \mid \sum_{i=1}^n i c_i\), et le lemme 1 termine ce cas. \(\blacksquare\)

Remarques

Remarque. On ne peut pas se passer de l'hypothèse « \(n\) ne divise pas la somme de tous les éléments ». En effet, pour tout \(n > 1\), l'ensemble formé de \(1\), de \(-1\) et de \(n - 2\) éléments divisibles par \(n\) n'admet pas la permutation voulue (si \(1\) et \(-1\) sont aux positions \(i \neq j\), la somme est congrue à \(i - j \not\equiv 0 \pmod n\)).