Shortlist 2010, N1¶
Domaine : Théorie des nombres · Difficulté : ★☆☆☆☆ · Proposé par : Canada
Concepts : Divisibilité, PGCD et algorithme d'Euclide · Sommes, télescopage et transformation d'Abel
Solution officielle : Shortlist officielle 2010 (avec solutions), p. 64 (page 65 du PDF)
Énoncé¶
Trouver le plus petit entier \(n\) strictement positif pour lequel il existe un ensemble \(\{s_1, s_2, \ldots, s_n\}\) de \(n\) entiers strictement positifs distincts tel que
Énoncé original (anglais)
Find the least positive integer \(n\) for which there exists a set \(\{s_1, s_2, \ldots, s_n\}\) consisting of \(n\) distinct positive integers such that
Indices : les idées clés
- Minoration : avec \(s_1 < \cdots < s_n\) on a \(s_i \geq i + 1\), donc le produit est au moins le produit télescopique \(\frac{1}{2} \cdot \frac{2}{3} \cdots \frac{n}{n+1} = \frac{1}{n+1}\), d'où \(n \geq 39\).
- Exemple : \(\{2, 3, \ldots, 33, 35, 36, \ldots, 40, 67\}\) donne exactement \(\frac{51}{2010}\).
- Variante N1' : le dénominateur \(335\) impose un \(s_i\) divisible par \(67\), ce qui améliore la minoration et donne \(n = 48\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2010 (une solution pour N1, une pour la variante N1', et trois remarques). La variante N1' du livret remplace \(\frac{51}{2010}\) par \(\frac{42}{2010}\).
Réponse : \(n = 39\).
Solution¶
Supposons que, pour un certain \(n\), les nombres voulus existent ; on peut supposer \(s_1 < s_2 < \cdots < s_n\). Sûrement \(s_1 > 1\), sinon \(1 - \frac{1}{s_1} = 0\). On a donc \(2 \leq s_1 \leq s_2 - 1 \leq \cdots \leq s_n - (n - 1)\), d'où \(s_i \geq i + 1\) pour tout \(i = 1, \ldots, n\). Par conséquent,
ce qui implique
donc \(n \geq 39\).
Il reste à montrer que \(n = 39\) convient. Considérons l'ensemble \(\{2, 3, \ldots, 33, 35, 36, \ldots, 40, 67\}\), qui contient exactement \(39\) nombres. On a
donc pour \(n = 39\) il existe un exemple convenable. \(\blacksquare\)
Remarque. On peut montrer que l'exemple (1) est unique.
Variante N1'¶
Réponse pour N1' : \(n = 48\).
Supposons que, pour un certain \(n\), les nombres voulus existent. On obtient de même \(s_i \geq i + 1\). De plus, comme le dénominateur de la fraction \(\frac{42}{2010} = \frac{7}{335}\) est divisible par \(67\), l'un des \(s_i\) doit être divisible par \(67\), donc \(s_n \geq s_i \geq 67\). Cela signifie que
ce qui implique
donc \(n \geq 48\).
Il reste à montrer que \(n = 48\) convient. Considérons l'ensemble \(\{2, 3, \ldots, 33, 36, 37, \ldots, 50, 67\}\), qui contient exactement \(48\) nombres. On a
donc pour \(n = 48\) il existe un exemple convenable. \(\blacksquare\)
Remarques¶
Remarque 1. Dans cette version du problème, l'estimation demande une étape de plus ; elle est donc un peu plus difficile. D'autre part, l'exemple n'est pas unique dans cette version. Un autre exemple est
Remarque 2. N1' était la formulation du proposant. Le comité propose N1, en accord avec le numéro de l'OIM en cours.
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2025 N2 ★☆☆☆☆ : Un koala traverse un tableau \(n \times n\) dont la case \((i, j)\) porte \(\gcd(i, j)\) feuilles : combien peut-il en manger au plus ?
- 2024 N1 ★☆☆☆☆ : Trouver les \(n\) tels que, pour chaque diviseur \(d\), soit \(d + 1\) divise \(n\), soit \(d + 1\) est premier.
- 2023 N1 ★☆☆☆☆ · OIM P1 : Quels entiers composés ont chaque diviseur qui divise la somme des deux diviseurs suivants ?
- 2015 N2 ★☆☆☆☆ : Si \(a! + b!\) divise \(a!\,b!\), alors \(3a \geq 2b + 2\).