Aller au contenu

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é

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,

\[\lfloor x \rfloor + \lfloor y \rfloor \geq x + y - 1. \tag{1}\]

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

\[2S = \sum_{1 \leq i, j \leq n} \left(\left\lfloor \frac{ij}{n+1} \right\rfloor + \left\lfloor \frac{ij}{n+1} \right\rfloor\right) = \sum_{1 \leq i, j \leq n} \left(\left\lfloor \frac{ij}{n+1} \right\rfloor + \left\lfloor \frac{(n+1-i)j}{n+1} \right\rfloor\right) \geq \sum_{1 \leq i, j \leq n} (j - 1) = \frac{(n-1)n^2}{2}.\]

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

\[(g - 1)k \leq j \leq gk - 1 \tag{2}\]

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

\[\sum_{j=0}^{n} r_j = \sum_{g=1}^{d} \sum_{\ell=0}^{(n+1)/d - 1} \ell d = d \cdot \frac{1}{2} \cdot \frac{n+1}{d}\left(\frac{n+1}{d} - 1\right) d = \frac{(n + 1 - d)(n + 1)}{2}. \tag{3}\]

Grâce à (3), la somme \(S_i\) de la ligne \(i\) vaut

\[S_i = \sum_{j=0}^{n} \left\lfloor \frac{ij}{n+1} \right\rfloor = \sum_{j=0}^{n} \frac{ij - r_j}{n+1} = \frac{i}{n+1} \sum_{j=0}^{n} j - \frac{1}{n+1} \sum_{j=0}^{n} r_j = \frac{i}{n+1} \cdot \frac{n(n+1)}{2} - \frac{1}{n+1} \cdot \frac{(n + 1 - d)(n + 1)}{2} = \frac{in - n - 1 + d}{2}. \tag{4}\]

L'égalité (4) donne la minoration suivante de \(S_i\), avec égalité si et seulement si \(d = \operatorname{pgcd}(i, n + 1) = 1\) :

\[S_i \geq \frac{in - n - 1 + 1}{2} = \frac{n(i - 1)}{2}. \tag{5}\]

En sommant (5) sur les lignes \(i = 1, \ldots, n\), on obtient la minoration de la somme totale

\[\sum_{i=1}^{n} S_i \geq \frac{n}{2} \sum_{i=1}^{n} (i - 1) = \frac{n^2 (n - 1)}{4}. \tag{6}\]

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.