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é

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

\[\left(1 - \frac{1}{s_1}\right)\left(1 - \frac{1}{s_2}\right) \cdots \left(1 - \frac{1}{s_n}\right) = \frac{51}{2010}.\]

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,

\[\begin{aligned} \frac{51}{2010} &= \left(1 - \frac{1}{s_1}\right)\left(1 - \frac{1}{s_2}\right) \cdots \left(1 - \frac{1}{s_n}\right) \\ &\geq \left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right) \cdots \left(1 - \frac{1}{n + 1}\right) = \frac{1}{2} \cdot \frac{2}{3} \cdots \frac{n}{n + 1} = \frac{1}{n + 1}, \end{aligned}\]

ce qui implique

\[n + 1 \geq \frac{2010}{51} = \frac{670}{17} > 39,\]

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

\[\frac{1}{2} \cdot \frac{2}{3} \cdots \frac{32}{33} \cdot \frac{34}{35} \cdots \frac{39}{40} \cdot \frac{66}{67} = \frac{1}{33} \cdot \frac{34}{40} \cdot \frac{66}{67} = \frac{17}{670} = \frac{51}{2010}, \tag{1}\]

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

\[\frac{42}{2010} \geq \frac{1}{2} \cdot \frac{2}{3} \cdots \frac{n - 1}{n} \cdot \left(1 - \frac{1}{67}\right) = \frac{66}{67n},\]

ce qui implique

\[n \geq \frac{2010 \cdot 66}{42 \cdot 67} = \frac{330}{7} > 47,\]

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

\[\frac{1}{2} \cdot \frac{2}{3} \cdots \frac{32}{33} \cdot \frac{35}{36} \cdots \frac{49}{50} \cdot \frac{66}{67} = \frac{1}{33} \cdot \frac{35}{50} \cdot \frac{66}{67} = \frac{7}{335} = \frac{42}{2010},\]

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

\[\frac{1}{2} \cdot \frac{2}{3} \cdots \frac{46}{47} \cdot \frac{66}{67} \cdot \frac{329}{330} = \frac{1}{67} \cdot \frac{66}{330} \cdot \frac{329}{47} = \frac{7}{67 \cdot 5} = \frac{42}{2010}.\]

Remarque 2. N1' était la formulation du proposant. Le comité propose N1, en accord avec le numéro de l'OIM en cours.