Shortlist 2016, C2¶

Domaine : Combinatoire · Difficulté : ★☆☆☆☆ · Proposé par : non indiqué

Concepts : Principe extrémal · Divisibilité, PGCD et algorithme d'Euclide · Fonctions arithmétiques : nombre de diviseurs, indicatrice d'Euler, somme des diviseurs

Solution officielle : Shortlist officielle 2016 (avec solutions), p. 31 (page 34 du PDF)

Énoncé¶

Find all positive integers \(n\) for which all positive divisors of \(n\) can be put into the cells of a rectangular table under the following constraints:

each cell contains a distinct divisor;
the sums of all rows are equal; and
the sums of all columns are equal.

Indices : les idées clés

Principe extrémal (solution 1) : regarder le plus grand nombre \(d_j\) de chaque colonne et le plus petit de ces maxima.
Divisibilité : parmi \(l\) diviseurs distincts de \(n\), le plus petit est au plus \(\frac{n}{l}\).
Fonctions arithmétiques (solution 2) : comparer le nombre de diviseurs \(\tau(n) = kl\) et la somme des diviseurs \(\sigma(n)\), facteur premier par facteur premier.

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2016 (deux solutions).

Réponse. Seul \(n = 1\) convient.

Solution 1¶

Supposons que tous les diviseurs positifs de \(n\) puissent être disposés dans un tableau à \(k\) lignes et \(l\) colonnes, où le nombre de lignes \(k\) ne dépasse pas le nombre de colonnes \(l\). Soit \(s\) la somme commune des colonnes. Comme \(n\) figure dans l'une des colonnes, \(s \geq n\), avec égalité seulement si \(n = 1\) (pour \(n > 1\) : si \(k \geq 2\), la colonne de \(n\) contient un autre diviseur ; si \(k = 1\), les colonnes ont un seul élément et ne peuvent pas avoir la même somme).

Pour \(j = 1, 2, \ldots, l\), soit \(d_j\) le plus grand nombre de la \(j\)-ième colonne. Sans perte de généralité, \(d_1 > d_2 > \cdots > d_l\). Ce sont \(l\) diviseurs distincts de \(n\) ; le \(l\)-ième plus grand diviseur de \(n\) est au plus \(\frac{n}{l}\), donc

\[d_l \leq \frac{n}{l}. \tag{1}\]

Comme \(d_l\) est le plus grand des \(k\) nombres de la \(l\)-ième colonne, dont la somme est \(s\),

\[d_l \geq \frac{s}{k} \geq \frac{n}{k}. \tag{2}\]

En combinant (1) et (2), on obtient \(\frac{n}{l} \geq \frac{n}{k}\), c'est-à-dire \(k \geq l\). Avec \(k \leq l\), on conclut \(k = l\). Alors toutes les inégalités de (1) et (2) sont des égalités ; en particulier \(s = n\), donc \(n = 1\). Dans ce cas, les conditions sont évidemment satisfaites. \(\blacksquare\)

Solution 2¶

Clairement \(n = 1\) convient. Supposons \(n > 1\) et écrivons sa décomposition en facteurs premiers \(n = p_1^{r_1} p_2^{r_2} \cdots p_t^{r_t}\). Supposons que le tableau ait \(k\) lignes et \(l\) colonnes avec \(1 < k \leq l\) (s'il n'y avait qu'une ligne, chaque colonne contiendrait un seul diviseur et les sommes des colonnes ne pourraient pas être égales). Le produit \(kl\) est le nombre de diviseurs positifs de \(n\), et la somme de tous les nombres du tableau est la somme des diviseurs \(\sigma(n)\). Considérons la colonne contenant \(n\) : la somme d'une colonne vaut \(\frac{\sigma(n)}{l}\), et cette colonne contient \(n\) et au moins un autre diviseur, donc \(\frac{\sigma(n)}{l} > n\). Par conséquent

\[(r_1+1)(r_2+1)\cdots(r_t+1) = kl \leq l^2 < \left(\frac{\sigma(n)}{n}\right)^2 = \left(1 + \frac{1}{p_1} + \cdots + \frac{1}{p_1^{r_1}}\right)^2 \cdots \left(1 + \frac{1}{p_t} + \cdots + \frac{1}{p_t^{r_t}}\right)^2.\]

Cela se réécrit

\[f(p_1, r_1)\, f(p_2, r_2) \cdots f(p_t, r_t) < 1, \tag{3}\]

où

\[f(p, r) = \frac{r + 1}{\left(1 + \frac{1}{p} + \cdots + \frac{1}{p^r}\right)^2} = \frac{(r+1)\left(1 - \frac{1}{p}\right)^2}{\left(1 - \frac{1}{p^{r+1}}\right)^2}.\]

Un calcul direct donne

\[f(2, 1) = \frac{8}{9}, \qquad f(2, 2) = \frac{48}{49}, \qquad f(3, 1) = \frac{9}{8}.\]

De plus,

\[\begin{aligned} f(2, r) &\geq \left(1 - \frac{1}{2^{r+1}}\right)^{-2} > 1 && \text{pour } r \geq 3, \\ f(3, r) &\geq \frac{4}{3}\left(1 - \frac{1}{3^{r+1}}\right)^{-2} > \frac{4}{3} > \frac{9}{8} && \text{pour } r \geq 2, \\ f(p, r) &\geq \frac{32}{25}\left(1 - \frac{1}{p^{r+1}}\right)^{-2} > \frac{32}{25} > \frac{9}{8} && \text{pour } p \geq 5. \end{aligned}\]

Le premier \(2\) apparaît au plus une fois, donc au plus un facteur est inférieur à \(1\) (\(f(2,1)\) ou \(f(2,2)\)), et tout facteur associé à un premier impair vaut au moins \(\frac{9}{8}\), ce qui compense (\(\frac{8}{9} \cdot \frac{9}{8} = 1\)). D'après ces valeurs et ces bornes, (3) n'est vérifiée que pour \(n = 2\) ou \(n = 4\). Dans ces deux cas, on voit facilement que les conditions ne sont pas satisfaites (le nombre de diviseurs, \(2\) ou \(3\), ne permet pas \(1 < k \leq l\)). Donc le seul \(n\) possible est \(n = 1\). \(\blacksquare\)