Shortlist 2006, N3

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

Concepts : Fonctions arithmétiques : nombre de diviseurs, indicatrice d'Euler, somme des diviseurs · Partie entière et majorations

Solution officielle : Shortlist officielle 2006 (avec solutions), p. 57 (page 58 du PDF)

Énoncé

The sequence \(f(1), f(2), f(3), \ldots\) is defined by

\[f(n) = \frac{1}{n}\left(\left\lfloor \frac{n}{1} \right\rfloor + \left\lfloor \frac{n}{2} \right\rfloor + \cdots + \left\lfloor \frac{n}{n} \right\rfloor\right),\]

where \(\lfloor x \rfloor\) denotes the integer part of \(x\).

(a) Prove that \(f(n + 1) > f(n)\) infinitely often.

(b) Prove that \(f(n + 1) < f(n)\) infinitely often.

Indices : les idées clés

• Parties entières : \(\lfloor n/k \rfloor - \lfloor (n - 1)/k \rfloor\) vaut \(1\) si \(k \mid n\) et \(0\) sinon, donc \(g(n) = nf(n)\) vérifie \(g(n) = g(n - 1) + d(n)\).
• Moyenne : \(f(n)\) est la moyenne de \(d(1), \ldots, d(n)\) (nombre de diviseurs) ; il suffit que \(d(n + 1)\) soit infiniment souvent au-dessus et en dessous de cette moyenne.
• Premiers et records : \(d(p) = 2 < f(p - 1)\) pour \(p\) premier assez grand, et \(d\) n'est pas bornée, donc atteint une infinité de records.

Solutions

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

Solution

Posons \(g(n) = nf(n)\) pour \(n \geq 1\) et \(g(0) = 0\). Remarquons que, pour \(k = 1, \ldots, n\),

\[\left\lfloor \frac{n}{k} \right\rfloor - \left\lfloor \frac{n - 1}{k} \right\rfloor = 0\]

si \(k\) ne divise pas \(n\), et

\[\left\lfloor \frac{n}{k} \right\rfloor - \left\lfloor \frac{n - 1}{k} \right\rfloor = 1\]

si \(k\) divise \(n\). Il s'ensuit que, si \(d(n)\) désigne le nombre de diviseurs positifs de \(n \geq 1\), alors

\[\begin{aligned} g(n) &= \left\lfloor \frac{n}{1} \right\rfloor + \left\lfloor \frac{n}{2} \right\rfloor + \cdots + \left\lfloor \frac{n}{n - 1} \right\rfloor + \left\lfloor \frac{n}{n} \right\rfloor \\ &= \left\lfloor \frac{n - 1}{1} \right\rfloor + \left\lfloor \frac{n - 1}{2} \right\rfloor + \cdots + \left\lfloor \frac{n - 1}{n - 1} \right\rfloor + \left\lfloor \frac{n - 1}{n} \right\rfloor + d(n) = g(n - 1) + d(n). \end{aligned}\]

Donc

\[g(n) = g(n - 1) + d(n) = g(n - 2) + d(n - 1) + d(n) = \cdots = d(1) + d(2) + \cdots + d(n),\]

ce qui signifie que

\[f(n) = \frac{d(1) + d(2) + \cdots + d(n)}{n}.\]

Autrement dit, \(f(n)\) est la moyenne arithmétique de \(d(1), d(2), \ldots, d(n)\). Pour prouver les affirmations, il suffit donc de montrer que \(d(n + 1) > f(n)\) et \(d(n + 1) < f(n)\) sont chacune vraies une infinité de fois.

Remarquons que \(d(1) = 1\). Pour \(n > 1\), on a \(d(n) \geq 2\), avec égalité si et seulement si \(n\) est premier. Comme \(f(6) = 7/3 > 2\), il s'ensuit que \(f(n) > 2\) pour tout \(n \geq 6\).

Comme il y a une infinité de nombres premiers, \(d(n + 1) = 2\) pour une infinité de valeurs de \(n\), et pour chacune de ces valeurs \(n \geq 6\), on a \(d(n + 1) = 2 < f(n)\). Cela prouve l'affirmation (b).

Pour prouver (a), remarquons que la suite \(d(1), d(2), d(3), \ldots\) n'est pas bornée (par exemple \(d(2^k) = k + 1\) pour tout \(k\)). Donc \(d(n + 1) > \max\{d(1), d(2), \ldots, d(n)\}\) pour une infinité de \(n\). Pour tous ces \(n\), on a \(d(n + 1) > f(n)\). Cela termine la solution. \(\blacksquare\)