Aller au contenu

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 :

\[a_0 = b_0 = 1, \qquad a_1 = b_1 = 7,\]
\[a_{i+1} = \begin{cases} 2a_{i-1} + 3a_i, & \text{si } \varepsilon_i = 0, \\ 3a_{i-1} + a_i, & \text{si } \varepsilon_i = 1, \end{cases} \qquad \text{pour tout } i = 1, \ldots, n - 1,\]
\[b_{i+1} = \begin{cases} 2b_{i-1} + 3b_i, & \text{si } \varepsilon_{n-i} = 0, \\ 3b_{i-1} + b_i, & \text{si } \varepsilon_{n-i} = 1, \end{cases} \qquad \text{pour tout } i = 1, \ldots, n - 1.\]

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:

\[a_0 = b_0 = 1, \qquad a_1 = b_1 = 7,\]
\[a_{i+1} = \begin{cases} 2a_{i-1} + 3a_i, & \text{if } \varepsilon_i = 0, \\ 3a_{i-1} + a_i, & \text{if } \varepsilon_i = 1, \end{cases} \qquad \text{for each } i = 1, \ldots, n - 1,\]
\[b_{i+1} = \begin{cases} 2b_{i-1} + 3b_i, & \text{if } \varepsilon_{n-i} = 0, \\ 3b_{i-1} + b_i, & \text{if } \varepsilon_{n-i} = 1, \end{cases} \qquad \text{for each } i = 1, \ldots, n - 1.\]

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 :

\[(u, v)^\emptyset = v, \qquad (u, v)^0 = 2u + 3v, \qquad (u, v)^1 = 3u + v,\]
\[(u, v)^{w\sigma\varepsilon} = \begin{cases} 2(u, v)^w + 3(u, v)^{w\sigma}, & \text{si } \varepsilon = 0, \\ 3(u, v)^w + (u, v)^{w\sigma}, & \text{si } \varepsilon = 1. \end{cases}\]

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\),

\[(\lambda_1u_1 + \lambda_2u_2, \lambda_1v_1 + \lambda_2v_2)^w = \lambda_1(u_1, v_1)^w + \lambda_2(u_2, v_2)^w, \tag{1}\]

et que, pour \(\varepsilon \in \{0, 1\}\),

\[(u, v)^{\varepsilon w} = (v, (u, v)^\varepsilon)^w. \tag{2}\]

É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

\[(1, 7)^w = (1, 7)^{\overline{w}} \tag{3}\]

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

\[\begin{aligned} (1, 7)^{w\sigma 0} &= 2(1, 7)^w + 3(1, 7)^{w\sigma} = 2(1, 7)^{\overline{w}} + 3(1, 7)^{\sigma\overline{w}} = 2(2, 1)^{\sigma\overline{w}} + 3(1, 7)^{\sigma\overline{w}} \\ &= (7, 23)^{\sigma\overline{w}} = (1, 7)^{0\sigma\overline{w}}. \end{aligned}\]

Soit maintenant \(\varepsilon = 1\). De même, on obtient

\[\begin{aligned} (1, 7)^{w\sigma 1} &= 3(1, 7)^w + (1, 7)^{w\sigma} = 3(1, 7)^{\overline{w}} + (1, 7)^{\sigma\overline{w}} = 3(2, 1)^{\sigma\overline{w}} + (1, 7)^{\sigma\overline{w}} \\ &= (7, 10)^{\sigma\overline{w}} = (1, 7)^{1\sigma\overline{w}}. \end{aligned}\]

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

\[(1, 7)^{\alpha\beta w} = \big((1, 7)^w, (1, 7)^{\beta w}\big)^\alpha, \qquad \alpha, \beta \in \{0, 1\},\]

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\) :

\[(1, 7)^{\alpha\beta w} = \big((1, 7)^w, (1, 7)^{\beta w}\big)^\alpha = \big((1, 7)^{\overline{w}}, (1, 7)^{\overline{w}\beta}\big)^\alpha = (1, 7)^{\overline{w}\beta\alpha}.\]

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 ?