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)
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
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
En considérant les quotients (de ces nombres par les différences correspondantes), on obtient que l'ensemble
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.