Shortlist 2021, A2¶
Domaine : Algèbre · Difficulté : ★☆☆☆☆ · Proposé par : non indiqué
Concepts : Partie entière et majorations · Divisibilité, PGCD et algorithme d'Euclide
Solution officielle : Shortlist officielle 2021 (avec solutions), p. 14 (page 14 du PDF)
Énoncé¶
Pour tout entier \(n \geq 1\), on considère le tableau \(n \times n\) dont la case située à l'intersection de la ligne \(i\) et de la colonne \(j\) contient \(\left\lfloor \frac{ij}{n+1} \right\rfloor\), pour tous \(i = 1, \ldots, n\) et \(j = 1, \ldots, n\). Déterminer tous les entiers \(n \geq 1\) pour lesquels la somme des \(n^2\) nombres du tableau vaut \(\frac{1}{4} n^2 (n - 1)\).
Énoncé original (anglais)
For every integer \(n \geq 1\) consider the \(n \times n\) table with entry \(\left\lfloor \frac{ij}{n+1} \right\rfloor\) at the intersection of row \(i\) and column \(j\), for every \(i = 1, \ldots, n\) and \(j = 1, \ldots, n\). Determine all integers \(n \geq 1\) for which the sum of the \(n^2\) entries in the table is equal to \(\frac{1}{4} n^2 (n - 1)\).
Indices : les idées clés
- Partie entière : si \(x + y\) est entier, \(\lfloor x \rfloor + \lfloor y \rfloor \geq x + y - 1\), avec égalité si et seulement si \(x\) et \(y\) ne sont pas entiers.
- Apparier \(i\) et \(n + 1 - i\) (solution 1) : les deux termes \(\frac{ij}{n+1}\) et \(\frac{(n+1-i)j}{n+1}\) ont une somme entière \(j\).
- Divisibilité, PGCD (solution 2) : avec \(d = \operatorname{pgcd}(i, n+1)\), les restes de \(ij\) modulo \(n + 1\) parcourent les multiples de \(d\), ce qui donne une formule exacte de la somme de chaque ligne.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2021 (deux solutions et une remarque).
Réponse. Ce sont exactement les entiers \(n\) tels que \(n + 1\) est premier.
Solution 1¶
Observons d'abord que pour tous réels \(x, y\) dont la somme \(x + y\) est entière,
L'inégalité est stricte si \(x\) et \(y\) sont entiers (il y a alors égalité \(\lfloor x \rfloor + \lfloor y \rfloor = x + y\)), et c'est une égalité sinon (partie entière : les parties fractionnaires de \(x\) et \(y\) sont alors non nulles et de somme \(1\)).
Notons \(S\) la somme du tableau. En appariant la ligne \(i\) avec la ligne \(n + 1 - i\) :
L'inégalité de la dernière étape découle de (1) avec \(x = \frac{ij}{n+1}\) et \(y = \frac{(n+1-i)j}{n+1}\), de sorte que \(x + y = j\) est entier.
Ainsi \(S = \frac{1}{4} n^2 (n - 1)\) si et seulement si cette dernière inégalité est une égalité, c'est-à-dire si et seulement si aucune des valeurs \(\frac{ij}{n+1}\), \(1 \leq i, j \leq n\), n'est entière.
Si \(n + 1\) est composé, avec une factorisation \(n + 1 = ab\) où \(2 \leq a, b \leq n\), on obtient une inégalité stricte pour \(i = a\) et \(j = b\). Si \(n + 1\) est premier, \(\frac{ij}{n+1}\) n'est jamais entier et \(S = \frac{1}{4} n^2 (n - 1)\). \(\blacksquare\)
Solution 2¶
Pour simplifier les indices, on ajoute au tableau une colonne fantôme d'indice \(0\) remplie de zéros (ce qui ne change pas la somme). Fixons une ligne \(i\), \(1 \leq i \leq n\), et posons \(d := \operatorname{pgcd}(i, n + 1)\) et \(k := (n + 1)/d\). Pour les colonnes \(j = 0, \ldots, n\), notons \(r_j := ij \bmod (n + 1)\) le reste de \(ij\) modulo \(n + 1\).
Affirmation. Pour tout entier \(g\) avec \(1 \leq g \leq d\), les restes \(r_j\) d'indices \(j\) dans l'intervalle
forment une permutation des \(k\) nombres \(0 \cdot d, 1 \cdot d, 2 \cdot d, \ldots, (k - 1) \cdot d\).
Preuve. Si \(r_{j'} = r_j\) pour deux indices \(j'\) et \(j\) de (2), alors \(i(j' - j) \equiv 0 \pmod{n + 1}\), donc (PGCD : en divisant par \(d\), \(\frac{i}{d}\) est premier avec \(k\)) \(j' - j\) est un multiple de \(k\) ; comme \(|j' - j| \leq k - 1\), on a \(j' = j\). Les \(k\) restes sont donc deux à deux distincts. De plus, chaque reste \(r_j = ij \bmod (n + 1)\) est un multiple de \(d = \operatorname{pgcd}(i, n + 1)\), compris entre \(0\) et \(n = kd - 1\). Cela prouve l'affirmation. \(\square\)
On en déduit
Grâce à (3), la somme \(S_i\) de la ligne \(i\) vaut
L'égalité (4) donne la minoration suivante de \(S_i\), avec égalité si et seulement si \(d = \operatorname{pgcd}(i, n + 1) = 1\) :
En sommant (5) sur les lignes \(i = 1, \ldots, n\), on obtient la minoration de la somme totale
Il y a égalité dans (6) si et seulement s'il y a égalité dans (5) pour chaque \(i = 1, \ldots, n\), c'est-à-dire si et seulement si \(\operatorname{pgcd}(i, n + 1) = 1\) pour tout \(i = 1, \ldots, n\), ce qui équivaut à : \(n + 1\) est premier. Ainsi la somme vaut \(\frac{1}{4} n^2 (n - 1)\) si et seulement si \(n + 1\) est premier. \(\blacksquare\)
Remarques¶
Remarque 1. Pour simplifier la réponse, on pourrait poser \(m := n + 1\) et tout écrire en fonction de \(m\). L'inconvénient est que la somme s'écrirait alors \(\frac{1}{4}(m - 1)^2 (m - 2)\), ce qui paraît plus artificiel.
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\) ?
- 2023 A1 ★☆☆☆☆ : Distribuer \(100\) kg de nourriture en portions entières à \(100\) Pokémon : quelle insatisfaction totale peut-on toujours garantir ?
- 2021 A3 ★★☆☆☆ : Minimiser \(\lfloor a_1/1 \rfloor + \cdots + \lfloor a_n/n \rfloor\) sur les permutations de \(1, \ldots, n\).
- 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.