Le fantôme de Pascal

Bougies, parité et pari dans un château circulaire

Château de quatre salles, une seule bougie allumée : quatre coups de minuit plus tard tout est éteint, non sans avoir embrasé le château entier. Château de trois salles, même règle, même bougie : le fantôme tourne en rond et ne s’en ira jamais. Ce qui sépare $3$ de $4$ se lit dans le triangle de Pascal, à condition de ne retenir que la parité, et l’on pourra même parier dessus.

La partie I met le triangle de Pascal en évidence et peut être traitée seule ; la partie II, qui en reprend les notations $S$ et $T$, sépare les configurations qui s’éteignent de celles qui se répètent ; la partie III en tire un pari.

Dans un château, $N\geqslant 2$ salles sont disposées en cercle et numérotées de $0$ à $N-1$.
Chacune contient une bougie.
À minuit, le fantôme de Pascal se réveille.
À chaque coup de l’horloge, il applique simultanément la règle suivante dans toutes les salles :

Une bougie sera allumée si, et seulement si, juste avant le coup, son état était différent de celui de la bougie de la salle précédente.

Une unique bougie allumée donne donc naissance à deux flammes.
Les indices des salles sont toujours pris modulo $N$.
Le fantôme disparaît dès que toutes les bougies sont éteintes.

On note $x_i(t)\in\{0,1\}$ l’état de la bougie $i$ après $t$ coups, où $1$ signifie « allumée », et $x(t)=(x_0(t),\ldots,x_{N-1}(t))$.
Pour la configuration initiale $x=x(0)$, le temps de disparition est
$$\tau(x)=\min\{t\in\mathbb N:x(t)=0\},$$avec $\tau(x)=+\infty$ si cet ensemble est vide. En particulier, $\tau(0)=0$.

I. L’empreinte du fantôme

Figure 1 – L’empreinte du fantôme dans un château de $16$ salles : à minuit, seule la bougie de la salle $0$ est allumée. Les lignes, de haut en bas, donnent l’état des bougies après $t=0,1,\ldots,16$ coups d’horloge, les colonnes, de gauche à droite, correspondent aux salles $0$ à $15$ ; une case noire est une bougie allumée. Au seizième coup, tout est éteint.

1. Dans un château de quatre salles, partir de $(1,0,0,0)$ et déterminer les configurations successives jusqu’à la disparition du fantôme.
Recommencer dans un château de trois salles en partant de $(1,0,0)$, jusqu’à rencontrer une configuration déjà obtenue.
Le fantôme disparaît-il toujours ?

2. On travaille désormais dans le corps $\mathbb{F}_2=\{0,1\}$, où $1+1=0$.
La règle s’écrit donc $x_i(t+1)=x_i(t)+x_{i-1}(t)$.
On pose
$$S(x_0,x_1,\ldots,x_{N-1})=(x_{N-1},x_0,\ldots,x_{N-2}), \qquad T=I+S,$$où $I$ est l’identité. Montrer que $x(t)=T^t x(0)$ et que
$$x_i(t)=\sum_{k=0}^{t}\binom{t}{k}x_{i-k}(0) \qquad\text{dans }\mathbb{F}_2.$$Pour $x(0)=(1,0,\ldots,0)$ et $0\leqslant t<N$, interpréter la configuration obtenue à l’aide du triangle de Pascal, et expliquer le motif de la figure 1.

3. Soit $t=\sum_{j=0}^{r}\varepsilon_j2^j$ l’écriture binaire de $t$, avec $\varepsilon_j\in\{0,1\}$.
Établir, dans $\mathbb{F}_2[X]$, l’identité
$$(1+X)^t=\prod_{\{j:\varepsilon_j=1\}}(1+X^{2^j}).$$En déduire le nombre de coefficients impairs de la ligne $t$ du triangle de Pascal, puis le nombre de bougies allumées à l’instant $t<N$ lorsque la salle $0$ était initialement la seule éclairée.

4. Montrer que $T^{2^a}=I+S^{2^a}$ pour tout entier $a\geqslant 0$.
En déduire que, si $N=2^a$, toute configuration s’éteint en au plus $N$ coups.
Montrer que cette borne est atteinte.

II. Les configurations que l’on peut exorciser

On conserve les calculs dans $\mathbb{F}_2$.
À une configuration $x=(x_0,\ldots,x_{N-1})$, on associe son polynôme
$$C_x(X)=\sum_{i=0}^{N-1}x_iX^i.$$On écrit de manière unique $N=Lm$, où $L=2^a$ est une puissance de $2$ et $m$ est impair.
On pose
$$Q(X)=1+X+\cdots+X^{m-1},\qquad R(X)=Q(X)^L.$$Lorsque $m=1$, on a $Q=R=1$.

5. Montrer que $C_{Sx}$ est le reste de la division euclidienne de $XC_x$ par $X^N-1$.
En déduire que, pour tout $t\geqslant 0$,
$$T^t x=0 \quad\Longleftrightarrow\quad X^N-1\ \text{divise}\ (1+X)^t C_x(X).$$6. Justifier les identités et la propriété suivantes :
$$X^N-1=(X+1)^L R(X),\qquad R(X)=\sum_{j=0}^{m-1}X^{jL},\qquad R(1)=1.$$Pourquoi $R$ est-il premier avec $X+1$ ?

7. Montrer l’équivalence
$$\tau(x)<+\infty\quad\Longleftrightarrow\quad R\mid C_x.$$Montrer aussi qu’une configuration qui finit par s’éteindre s’éteint en au plus $L$ coups.
En déduire la réciproque de la question 4 : toute configuration s’éteint si, et seulement si, $N$ est une puissance de $2$.

8. Montrer que les configurations qui finissent par s’éteindre sont exactement celles obtenues en répétant $m$ fois un même bloc de longueur $L$.
Combien y en a-t-il ?
Que devient ce résultat lorsque $N$ est impair ?

9. Pour $0\leqslant t\leqslant L$, montrer que
$$T^t x=0 \quad\Longleftrightarrow\quad (X+1)^{L-t}R(X)\mid C_x(X).$$En comptant les multiples de ce polynôme de degré strictement inférieur à $N$, déterminer le nombre de configurations telles que $\tau(x)\leqslant t$, puis le nombre de celles telles que $\tau(x)=t$.

10. Soit une configuration non nulle qui finit par s’éteindre.
On écrit $C_x=AR$, avec $\deg A<L$, et l’on note $v$ la multiplicité de la racine $1$ dans $A$ : ainsi $A=(X+1)^vB$, avec $B(1)=1$.
Exprimer $\tau(x)$ en fonction de $L$ et de $v$.
Donner explicitement toutes les configurations qui s’éteignent lorsque $N=6$, ainsi que leurs temps de disparition.

11. On note $W$ l’ensemble des configurations $y$ telles que $(X+1)^L$ divise $C_y$.
Montrer que $T^Lx\in W$ pour toute configuration $x$, que $T(W)\subset W$ et que $T$ est injective sur $W$.
En déduire que, pour toute configuration initiale, la suite $(x(t))_{t\geqslant L}$ est périodique : passé le $L$-ième coup, le fantôme a disparu ou se répète indéfiniment.
Combien $W$ compte-t-il d’éléments ?

Le fantôme peut donc hanter éternellement un petit château, et être condamné à disparaître dans un château beaucoup plus grand. Reste à savoir si l’on peut parier sur sa disparition.

III. Le dernier pari de Pascal

Oui, mais il faut parier. Cela n’est pas volontaire, vous êtes embarqué.

— Blaise Pascal, Pensées,

Avant le premier coup de l’horloge, on décide de l’état de chaque bougie par un lancer d’une pièce équilibrée, indépendamment des autres bougies.
Les $2^N$ configurations sont donc équiprobables.
On note $\tau$ le temps de disparition aléatoire et $D=\{\tau<+\infty\}$.

Les résultats de la partie II peuvent être admis pour traiter cette partie.

12. Calculer $\mathbb{P}(D)$ en fonction de $N$ et de $L$.
En particulier, si $N$ est impair, quelle est la probabilité de faire disparaître le fantôme ?

13. Déterminer la loi de $\tau$ conditionnellement à $D$, en distinguant $\tau=0$ et $1\leqslant\tau\leqslant L$.
Vérifier que les probabilités obtenues ont pour somme $1$.
Calculer $\mathbb{P}(\tau=L\mid D)$ et interpréter le résultat.

14. Montrer que
$$\mathbb{E}[\tau\mid D]=L-1+2^{-L}.$$On pourra établir d’abord la formule $\sum_{t=1}^{L}t2^{t-1}=(L-1)2^L+1$.
Quelle est l’espérance non conditionnelle de $\tau$, à valeurs dans $[0,+\infty]$, selon que $N$ est ou non une puissance de $2$ ?

15. Le fantôme vous propose de choisir entre trois châteaux : le premier possède $2026$ salles, le deuxième $2028$ salles et le troisième $2048$ salles.
Vous gagnez si le château choisi finit par être entièrement éteint.

a) Quel château choisissez-vous pour maximiser votre probabilité de gagner ?
Comparer exactement les probabilités de gain dans les trois cas.

b) Dans chacun des châteaux, calculer le délai maximal de disparition parmi les configurations qui s’éteignent et le délai moyen conditionnellement à la disparition.

c) Le fantôme ajoute une clause : pour gagner, toutes les bougies doivent être éteintes après au plus dix coups.
Votre choix change-t-il ?

d) Un visiteur affirme : « Après cent coups, il reste une bougie allumée dans le château de $2028$ salles ; attendons encore, cela finira peut-être par s’arranger. »
Que lui répondre ?

Sous les flammes, un triangle ; derrière le hasard, une parité.