Shortlist 2009, C3¶
Domaine : Combinatoire · Difficulté : ★★★☆☆ · Proposé par : Russia
Concepts : Récurrence et constructions récursives · Suites et récurrences
Solution officielle : Shortlist officielle 2009 (avec solutions), p. 29 (page 31 du PDF)
Énoncé¶
Soit \(n\) un entier strictement positif. Étant donnée une suite \(\varepsilon_1, \ldots, \varepsilon_{n-1}\) avec \(\varepsilon_i = 0\) ou \(\varepsilon_i = 1\) pour tout \(i = 1, \ldots, n - 1\), on construit les suites \(a_0, \ldots, a_n\) et \(b_0, \ldots, b_n\) par les règles suivantes :
Montrer que \(a_n = b_n\).
Énoncé original (anglais)
Let \(n\) be a positive integer. Given a sequence \(\varepsilon_1, \ldots, \varepsilon_{n-1}\) with \(\varepsilon_i = 0\) or \(\varepsilon_i = 1\) for each \(i = 1, \ldots, n - 1\), the sequences \(a_0, \ldots, a_n\) and \(b_0, \ldots, b_n\) are constructed by the following rules:
Prove that \(a_n = b_n\).
Indices : les idées clés
- Mots binaires : on code la suite par un mot \(w\) et l'on définit \((u, v)^w\) par la même récurrence à partir de \((u, v)\) ; alors \(a_n = (1, 7)^w\) et \(b_n = (1, 7)^{\overline{w}}\), où \(\overline{w}\) est le mot renversé.
- Linéarité et décalage : \((u, v)^w\) est linéaire en \((u, v)\), et \((u, v)^{\varepsilon w} = (v, (u, v)^\varepsilon)^w\).
- Récurrence sur la longueur : grâce à \((2, 1)^\sigma = 7 = (1, 7)^\emptyset\), \((1, 7)^0 = 23\) et \((1, 7)^1 = 10\), on montre \((1, 7)^w = (1, 7)^{\overline{w}}\).
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2009 (une solution et une remarque).
Solution¶
Pour un mot binaire \(w = \sigma_1 \ldots \sigma_n\) de longueur \(n\) et une lettre \(\sigma \in \{0, 1\}\), posons \(w\sigma = \sigma_1 \ldots \sigma_n\sigma\) et \(\sigma w = \sigma\sigma_1 \ldots \sigma_n\). Posons de plus \(\overline{w} = \sigma_n \ldots \sigma_1\), et notons \(\emptyset\) le mot vide (de longueur \(0\), avec \(\overline{\emptyset} = \emptyset\)). Soit \((u, v)\) un couple de deux réels. Pour les mots binaires \(w\), on définit récursivement les nombres \((u, v)^w\) ainsi :
Une récurrence sur la longueur de \(w\) montre facilement que, pour tous réels \(u_1, v_1, u_2, v_2, \lambda_1\) et \(\lambda_2\),
et que, pour \(\varepsilon \in \{0, 1\}\),
Évidemment, pour \(n \geq 1\) et \(w = \varepsilon_1 \ldots \varepsilon_{n-1}\), on a \(a_n = (1, 7)^w\) et \(b_n = (1, 7)^{\overline{w}}\). Il suffit donc de prouver que
pour tout mot binaire \(w\). On procède par récurrence sur la longueur de \(w\). L'affirmation est évidente si \(w\) est de longueur \(0\) ou \(1\). Soit maintenant \(w\sigma\varepsilon\) un mot binaire de longueur \(n \geq 2\), et supposons l'affirmation vraie pour tous les mots binaires de longueur au plus \(n - 1\).
Remarquons que \((2, 1)^\sigma = 7 = (1, 7)^\emptyset\) pour \(\sigma \in \{0, 1\}\), que \((1, 7)^0 = 23\) et que \((1, 7)^1 = 10\).
Soit d'abord \(\varepsilon = 0\). Vu l'hypothèse de récurrence et les égalités (1) et (2), on obtient
Soit maintenant \(\varepsilon = 1\). De même, on obtient
L'hérédité est donc établie, et (3), donc aussi \(a_n = b_n\), est démontré. \(\blacksquare\)
Remarque¶
La solution originale utilise la relation
qu'on prouve par récurrence sur la longueur de \(w\). Alors (3) découle aussi d'une récurrence sur la longueur de \(w\) :
Ici, \(w\) peut être le mot vide.
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2017 C3 ★★☆☆☆ : On place des puissances de \(2\) et on fusionne les égales sur \(9\) cases : combien de coups au plus pour finir avec \(2^n\) ?
- 2022 C6 ★★★☆☆ : On fusionne des cailloux pris en quantités égales dans deux tas : combien de tas au minimum ?
- 2011 A5 ★★★☆☆ : Partager \(\{2, \ldots, 3n + 1\}\) en \(n\) triplets formant chacun les côtés d'un triangle obtusangle.
- 2010 C4 ★★★☆☆ · OIM P5 : Six piles de pièces et deux types de coups : peut-on obtenir \(2010^{2010^{2010}}\) pièces sur la dernière pile ?