Shortlist 2013, N2

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

Concepts : Récurrence et constructions récursives · Sommes, télescopage et transformation d'Abel · Congruences, théorèmes de Fermat et d'Euler

Solution officielle : Shortlist officielle 2013 (avec solutions), p. 53 (page 53 du PDF)

Problème 1 de l'OIM 2013

Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2013, où il était le problème 1 (jour 1).

Énoncé

Prove that for any pair of positive integers \(k\) and \(n\) there exist \(k\) positive integers \(m_1, m_2, \ldots, m_k\) such that

\[1 + \frac{2^k - 1}{n} = \left(1 + \frac{1}{m_1}\right)\left(1 + \frac{1}{m_2}\right) \cdots \left(1 + \frac{1}{m_k}\right).\]

Indices : les idées clés

• Récurrence sur \(k\) (solution 1) : on détache un facteur \(1 + \frac{1}{m}\) et l'on se ramène à \(1 + \frac{2^{k-1} - 1}{t}\), en distinguant \(n = 2t - 1\) et \(n = 2t\).
• Produit télescopique (solution 2) : \(1 + \frac{2^k - 1}{n}\) s'écrit comme un produit de quotients consécutifs \(\frac{n + \cdots}{n + \cdots}\).
• Écriture binaire et congruences : on écrit \(n - 1\) et \(-n\) modulo \(2^k\) en base \(2\) ; leurs chiffres se complètent, et chaque \(m_i\) est entier car \(n + T_s \equiv 0 \pmod{2^k}\).

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2013 (deux solutions).

Solution 1

Procédons par récurrence sur \(k\). Pour \(k = 1\), l'énoncé est évident. Supposons-le prouvé pour \(k = j - 1\), et prouvons-le pour \(k = j\).

Cas 1 : \(n = 2t - 1\) pour un entier \(t \geq 1\). On a

\[1 + \frac{2^j - 1}{2t - 1} = \frac{2(t + 2^{j-1} - 1)}{2t} \cdot \frac{2t}{2t - 1} = \left(1 + \frac{2^{j-1} - 1}{t}\right)\left(1 + \frac{1}{2t - 1}\right).\]

Par hypothèse de récurrence, on peut trouver \(m_1, \ldots, m_{j-1}\) tels que

\[1 + \frac{2^{j-1} - 1}{t} = \left(1 + \frac{1}{m_1}\right)\left(1 + \frac{1}{m_2}\right) \cdots \left(1 + \frac{1}{m_{j-1}}\right),\]

et \(m_j = 2t - 1\) donne l'écriture voulue.

Cas 2 : \(n = 2t\) pour un entier \(t \geq 1\). On a cette fois

\[1 + \frac{2^j - 1}{2t} = \frac{2t + 2^j - 1}{2t + 2^j - 2} \cdot \frac{2t + 2^j - 2}{2t} = \left(1 + \frac{1}{2t + 2^j - 2}\right)\left(1 + \frac{2^{j-1} - 1}{t}\right),\]

en remarquant que \(2t + 2^j - 2 > 0\). On utilise à nouveau

\[1 + \frac{2^{j-1} - 1}{t} = \left(1 + \frac{1}{m_1}\right)\left(1 + \frac{1}{m_2}\right) \cdots \left(1 + \frac{1}{m_{j-1}}\right),\]

et \(m_j = 2t + 2^j - 2\) donne l'écriture voulue. \(\blacksquare\)

Solution 2

Considérons les écritures en base \(2\) des restes de \(n - 1\) et de \(-n\) modulo \(2^k\) :

\[n - 1 \equiv 2^{a_1} + 2^{a_2} + \cdots + 2^{a_r} \pmod{2^k} \quad \text{où } 0 \leq a_1 < a_2 < \cdots < a_r \leq k - 1,\]

\[-n \equiv 2^{b_1} + 2^{b_2} + \cdots + 2^{b_s} \pmod{2^k} \quad \text{où } 0 \leq b_1 < b_2 < \cdots < b_s \leq k - 1.\]

Comme \(-1 \equiv 2^0 + 2^1 + \cdots + 2^{k-1} \pmod{2^k}\), on a \(\{a_1, \ldots, a_r\} \cup \{b_1, \ldots, b_s\} = \{0, 1, \ldots, k - 1\}\) et \(r + s = k\). Posons

\[S_p = 2^{a_p} + 2^{a_{p+1}} + \cdots + 2^{a_r} \quad \text{pour } 1 \leq p \leq r, \qquad T_q = 2^{b_1} + 2^{b_2} + \cdots + 2^{b_q} \quad \text{pour } 1 \leq q \leq s,\]

et \(S_{r+1} = T_0 = 0\). On remarque que \(S_1 + T_s = 2^k - 1\) et \(n + T_s \equiv 0 \pmod{2^k}\). On a, par télescopage,

\[\begin{aligned} 1 + \frac{2^k - 1}{n} &= \frac{n + S_1 + T_s}{n} = \frac{n + S_1 + T_s}{n + T_s} \cdot \frac{n + T_s}{n} = \prod_{p=1}^{r} \frac{n + S_p + T_s}{n + S_{p+1} + T_s} \cdot \prod_{q=1}^{s} \frac{n + T_q}{n + T_{q-1}} \\ &= \prod_{p=1}^{r} \left(1 + \frac{2^{a_p}}{n + S_{p+1} + T_s}\right) \cdot \prod_{q=1}^{s} \left(1 + \frac{2^{b_q}}{n + T_{q-1}}\right), \end{aligned}\]

donc, si l'on pose

\[m_p = \frac{n + S_{p+1} + T_s}{2^{a_p}} \quad \text{pour } 1 \leq p \leq r \qquad \text{et} \qquad m_{r+q} = \frac{n + T_{q-1}}{2^{b_q}} \quad \text{pour } 1 \leq q \leq s,\]

l'égalité voulue est vérifiée. Il reste à vérifier que chaque \(m_i\) est entier. Pour \(1 \leq p \leq r\),

\[n + S_{p+1} + T_s \equiv n + T_s \equiv 0 \pmod{2^{a_p}},\]

et pour \(1 \leq q \leq s\) (le livret écrit \(1 \leq q \leq r\) ; il faut lire \(1 \leq q \leq s\)),

\[n + T_{q-1} \equiv n + T_s \equiv 0 \pmod{2^{b_q}}.\]

Le résultat suit. \(\blacksquare\)