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é

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.