Aller au contenu

Shortlist 2022, N6

Domaine : Théorie des nombres · Difficulté : ★★★★☆ · Proposé par : Costa Rica

Concepts : Principe des tiroirs · Fonctions arithmétiques : nombre de diviseurs, indicatrice d'Euler, somme des diviseurs

Solution officielle : Shortlist officielle 2022 (avec solutions), p. 67 (page 69 du PDF)

Énoncé

Soit \(Q\) un ensemble de nombres premiers, pas forcément fini. Pour un entier \(n\) strictement positif, on considère sa décomposition en facteurs premiers ; on note \(p(n)\) la somme de tous les exposants, et \(q(n)\) la somme des exposants des seuls nombres premiers de \(Q\). Un entier \(n\) strictement positif est dit spécial si \(p(n) + p(n + 1)\) et \(q(n) + q(n + 1)\) sont tous deux pairs. Montrer qu'il existe une constante \(c > 0\), indépendante de l'ensemble \(Q\), telle que, pour tout entier \(N > 100\), le nombre d'entiers spéciaux de \([1, N]\) soit au moins \(cN\).

(Par exemple, si \(Q = \{3, 7\}\), alors \(p(42) = 3\), \(q(42) = 2\), \(p(63) = 3\), \(q(63) = 3\), \(p(2022) = 3\), \(q(2022) = 1\).)

Énoncé original (anglais)

Let \(Q\) be a set of prime numbers, not necessarily finite. For a positive integer \(n\) consider its prime factorisation; define \(p(n)\) to be the sum of all the exponents and \(q(n)\) to be the sum of the exponents corresponding only to primes in \(Q\). A positive integer \(n\) is called special if \(p(n) + p(n + 1)\) and \(q(n) + q(n + 1)\) are both even integers. Prove that there is a constant \(c > 0\) independent of the set \(Q\) such that for any positive integer \(N > 100\), the number of special integers in \([1, N]\) is at least \(cN\).

(For example, if \(Q = \{3, 7\}\), then \(p(42) = 3\), \(q(42) = 2\), \(p(63) = 3\), \(q(63) = 3\), \(p(2022) = 3\), \(q(2022) = 1\).)

Indices : les idées clés
  • Principe des tiroirs : le couple \((p(k), q(k))\) modulo \(2\) ne prend que \(4\) valeurs, donc parmi \(5\) entiers, deux sont « amis ».
  • Fonctions additives : \(p\) et \(q\) vérifient \(f(ab) = f(a) + f(b)\), donc \(m, n\) sont amis si et seulement si \(m/d, n/d\) le sont.
  • Ensembles « intéressants » : dans \(\{72k, 72k+6, 72k+8, 72k+9, 72k+12\}\), chaque différence divise les deux nombres ; les quotients donnent des paires d'entiers consécutifs.
  • Comptage final : chaque ensemble \(S_k \subset [1, 100k]\) contient un entier spécial, et un entier n'appartient qu'à au plus \(10\) ensembles \(S_k\).
Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2022 (une solution et deux remarques).

Solution

Disons que deux entiers positifs \(m, n\) sont amis si \(p(m) + p(n)\) et \(q(m) + q(n)\) sont tous deux pairs. Ainsi \(n\) est spécial si et seulement si \(n\) et \(n+1\) sont amis.

Première observation. Les couples \((p(k), q(k))\) modulo \(2\) prennent au plus \(4\) valeurs ; donc, par le principe des tiroirs, parmi cinq entiers positifs distincts, deux sont amis.

Deuxième observation. Les fonctions \(p\) et \(q\) vérifient \(f(ab) = f(a) + f(b)\) pour tous \(a, b\). Donc, si \(m\) et \(n\) sont divisibles par \(d\), \(p\) et \(q\) vérifient \(f(m) + f(n) = f(m/d) + f(n/d) + 2f(d)\). Il en résulte que \(m, n\) sont amis si et seulement si \(m/d, n/d\) sont amis.

Ensembles intéressants. Appelons intéressant un ensemble d'entiers \(\{n_1, n_2, \ldots, n_5\}\) tel que, pour tous indices \(i, j\), la différence \(d_{ij} = |n_i - n_j|\) divise à la fois \(n_i\) et \(n_j\). Si les éléments d'un ensemble intéressant sont tous positifs, on obtient un entier spécial. En effet, d'après la première observation, il existe une paire \(\{n_i, n_j\}\) d'amis ; d'après la seconde, les quotients \(n_i/d_{ij}\) et \(n_j/d_{ij}\) sont amis, et ce sont deux entiers consécutifs : le plus petit des deux est spécial.

Construction. L'ensemble \(\{0, 6, 8, 9, 12\}\) est intéressant. Comme \(72 = 2^3 \cdot 3^2\) est le PPCM de toutes les différences deux à deux de cet ensemble, on obtient une famille d'ensembles intéressants

\[\{72k, \ 72k + 6, \ 72k + 8, \ 72k + 9, \ 72k + 12\}, \qquad k \geq 1.\]

En considérant les quotients (de ces nombres par les différences correspondantes), on obtient que l'ensemble

\[S_k = \{6k, \ 8k, \ 9k, \ 12k, \ 12k + 1, \ 18k + 2, \ 24k + 2, \ 24k + 3, \ 36k + 3, \ 72k + 8\}\]

contient au moins un entier spécial. (Par exemple, la paire \(72k, 72k+6\) donne les quotients \(12k, 12k+1\), et la paire \(72k+8, 72k+9\) donne \(72k+8, 72k+9\).)

Comptage. L'intervalle \([1, 100k]\) contient les ensembles \(S_1, S_2, \ldots, S_k\), chacun contenant un entier spécial. Un entier spécial donné appartient à au plus dix ensembles \(S_k\) (chacune des dix expressions de \(S_k\) est injective en \(k\)), donc le nombre d'entiers spéciaux dans \([1, 100k]\) est au moins \(k/10\).

Enfin, écrivons \(N = 100k + r\) avec \(k \geq 1\) et \(0 \leq r < 100\), de sorte que \(N < 100(k+1) \leq 200k\). Le nombre d'entiers spéciaux dans \([1, N]\) est alors au moins \(k/10 > N/2000\) : la constante \(c = \frac{1}{2000}\) convient, indépendamment de \(Q\). \(\blacksquare\)

Remarques

Remarque 1. L'énoncé reste vrai pour \(N \geq 15\), car au moins un des nombres \(7\), \(14\), \(15\) est spécial.

Remarque 2 (une approche qui bute). On peut remarquer que si \(p(2n)\), \(p(2n+1)\), \(p(2n+2)\) ont tous la même parité, alors l'un des nombres \(n\), \(2n\), \(2n+1\) est spécial. En effet, si \(q(n) + q(n+1)\) est pair, alors \(n\) est spécial, puisque \(p(n) + p(n+1) \equiv p(2n) + p(2n+2) \equiv 0 \pmod 2\). Sinon, \(q(n) + q(n+1)\) est impair, donc \(q(2n) + q(2n+2)\) aussi, ce qui implique qu'exactement l'un des nombres \(2n\), \(2n+1\) est spécial. Malheureusement, il semble difficile de montrer que l'ensemble de ces \(n\) a une densité positive : voir l'article https://arxiv.org/abs/1509.01545, qui montre que les huit motifs de parités de \(p(n)\), \(p(n+1)\), \(p(n+2)\) apparaissent pour une proportion positive d'entiers.

Problèmes voisins

Sur les mêmes idées, à une difficulté proche :

  • 2025 A6 ★★★★☆ : Trouver les suites non périodiques telles que \(a_n = \min_{\ell \in S} |a_{n+\ell} - \ell|\).
  • 2021 A6 ★★★★☆ · OIM P6 : Si des parties d'un ensemble fini \(A\) d'entiers ont pour sommes \(m, m^2, \ldots, m^m\), alors \(A\) a au moins \(m/2\) éléments.
  • 2018 N6 ★★★★☆ : Si \(f(m + n)\) divise \(f(m) + f(n)\), toutes les valeurs de \(f\) ont un diviseur commun.
  • 2015 N6 ★★★★☆ : Une fonction dont les itérées vérifient une condition de divisibilité et qui atteint presque tout : \(f(n) - n\) est périodique.