Exercice 4 — La manette défaillante (académique)

5. La position finale \((x,y)\) vaut \((\sum d_n-\sum g_n,\ \sum h_n-\sum b_n)\). Minimiser la longueur totale \(\sum b_n+\sum g_n+\sum h_n+\sum d_n\) sous ces deux contraintes revient à minimiser \(\sum b_n\) et \(\sum g_n\) séparément (leurs valeurs minimales étant imposées par les règles de démarrage de la manette).

7. Calculer directement l'abscisse (ou l'ordonnée) de la position finale de la spirale de rang \(N\) en fonction de \(N\) seul, pour en déduire le rang correspondant à \((2019,2019)\).

9. Une séquence de longueur \(n+1\) s'obtient à partir d'une séquence de longueur \(n\) de deux façons (répéter la dernière lettre, ou passer à l'unique lettre suivante autorisée) : en déduire une relation de récurrence entre \(u_{n+1}\) et \(u_n\).

11. Établir une relation de récurrence entre \(R(n,p)\), \(R(n-1,p)\) et \(R(n,p-1)\), en distinguant la dernière touche pressée (H ou D) de la séquence menant à \((n,p)\).

A1. En parcourant la séquence pas à pas (B:−4 en y, G:−2 en x, H:+4 en y, D:+1 en x, B:−1 en y, G:−3 en x, H:+2 en y, D:+5 en x, B:−2 en y, G:−3 en x) : position finale \((-2,-1)\).

A2. Par exemple BBBBB-G-H-DDDD, de position finale \(x=4-1=3\), \(y=1-5=-4\), soit \((3,-4)\) ✓.

A3. La séquence est BBB-GG-H-DDDD-B-GGGGG : \(x=4-2-5=-3\), \(y=1-3-1=-3\), position finale \((-3,-3)\).

A4. Longueur \(=3+2+1+4+1+5=\boxed{16}\).

B5. La position finale \((2019,2019)\) impose \(\sum d_n-\sum g_n=2019\) et \(\sum h_n-\sum b_n=2019\). La longueur totale \(L=\sum b_n+\sum g_n+\sum h_n+\sum d_n=2(\sum b_n+\sum g_n)+4038\) (en substituant \(\sum d_n=\sum g_n+2019\) et \(\sum h_n=\sum b_n+2019\)). Comme la séquence commence par B, \(\sum b_n\geq1\) ; et comme il faut au moins une lettre G pour pouvoir ensuite atteindre H puis D (la manette impose la chaîne B→G→H→D), \(\sum g_n\geq1\). D'où \(L\geq2(1+1)+4038=\boxed{4042}\), longueur atteinte par la séquence \(b_1=1,g_1=1,h_1=2020,d_1=2020\) (soit B-G-H…(2020 fois)-D…(2020 fois)), de position finale \((2020-1,2020-1)=(2019,2019)\) ✓.

C6. Pour la spirale de rang 3 (\(n=1,2,3\)) :

Séquence : B-G-HH-DD-BBB-GGG-HHHH-DDDD-BBBBB-GGGGG-HHHHHH-DDDDDD. Position finale : \(x=y=(2+4+6)-(1+3+5)=12-9=\boxed3\), soit \((3,3)\). Longueur \(=\sum_{n=1}^3(b_n+g_n+h_n+d_n)=6+14+22=\boxed{42}\).

C7. Pour la spirale de rang \(N\) : \(x=\sum_{k=1}^N(d_k-g_k)=\sum_{k=1}^N1=N\), et de même \(y=N\). La position \((2019,2019)\) correspond donc au rang \(N=2019\).

Longueur : \(b_k+g_k+h_k+d_k=2(2k-1)+2(2k)=8k-2\), donc \(L=\sum_{k=1}^{2019}(8k-2)=8\times\dfrac{2019\times2020}2-2\times2019=2019\times(8\times1010-2)=2019\times8078=\boxed{16\,309\,482}.\)

C8. Longueur de la spirale de rang \(N\) : \(L_N=\sum_{k=1}^N(8k-2)=4N^2+2N-2N=4N^2+2N\)... plus précisément \(L_N=8\times\frac{N(N+1)}2-2N=4N(N+1)-2N=4N^2+2N\). On résout \(4N^2+2N\geq2019\) : pour \(N=22\), \(4\times484+44=1980<2019\) ; pour \(N=23\), \(4\times529+46=2162\geq2019\). Le plus petit \(N\) qui convient est \(N=23\).

D9. Notons \(u_n\) le nombre de séquences de longueur \(n\). Une séquence de longueur \(n+1\) s'obtient à partir d'une séquence de longueur \(n\) en répétant la dernière lettre, ou en ajoutant l'unique autre lettre autorisée : \(u_{n+1}=2u_n\). Comme \(u_1=1\) (seule la séquence « B »), \((u_n)\) est géométrique de raison 2 : \(u_n=2^{n-1}\).

D10. \(M\) est la moyenne des longueurs des séquences de longueur \(\leq19\), pondérée par leur nombre \(u_k=2^{k-1}\) : \(M=\dfrac{\sum_{k=1}^{19}k\cdot2^{k-1}}{\sum_{k=1}^{19}2^{k-1}}\). En utilisant \(\sum_{k=1}^nk\cdot2^{k-1}=(n-1)2^n+1\) : numérateur \(=18\times2^{19}+1=9\,437\,185\), dénominateur \(=2^{19}-1=524\,287\). \(M=9\,437\,185/524\,287\approx18{,}0000\) — la moyenne est extrêmement proche de 19 (la longueur maximale), car les séquences longues sont exponentiellement plus nombreuses que les courtes.

E11. \(R(n,p)\) vérifie la récurrence \(R(n,p)=R(n-1,p)+R(n,p-1)\) (selon que la dernière touche est D ou H), avec \(R(0,p)=1\) pour tout \(p\geq1\) (séquence « H répété \(p\) fois ») et \(R(n,1)=1\) pour tout \(n\geq0\). C'est la construction du triangle de Pascal (par « sommes de coefficients binomiaux ») : \(R(n,p)=\dbinom{n+p-1}{n}\).