Exercice 107

Idée. Si le premier passager s'assied à la place $k$, avec $2 \leqslant k \leqslant n - 1$, les passagers $2$ à $k - 1$ s'assoient normalement, et le passager $k$ se retrouve exactement dans la situation du premier passager d'un avion plus petit, où la place $1$ joue le rôle de sa propre place. On obtient une relation de récurrence forte.

Le modèle. Le déroulement est déterminé par la suite des places choisies au hasard. Comme dans l'exemple qui suit la proposition 9, l'énoncé fixe les probabilités conditionnelles : chaque passager qui choisit au hasard prend chaque place libre avec la même probabilité, et la probabilité d'un déroulement est le produit des inverses des nombres de places libres lors des choix successifs. On note $q_{n}$ la probabilité que le dernier passager s'asseye à sa place, et $C_{1}$ la place prise par le premier passager, de loi uniforme sur $\llbracket 1\,,n \rrbracket$.

Conditionnement par la place du premier passager.

• Si $C_{1} = 1$, chaque passager trouve sa place libre : le dernier s'assied à sa place.

• Si $C_{1} = n$, la place $n$ est prise : le dernier ne s'assied pas à sa place.

• Si $C_{1} = k$ avec $2 \leqslant k \leqslant n - 1$, les passagers $2$, …, $k - 1$ trouvent leur place libre et s'y assoient. Le passager $k$ trouve sa place prise ; les places libres sont $1$, $k + 1$, …, $n$, au nombre de $n' = n - k + 1$. Renumérotons : le passager $k$ et la place $1$ deviennent le passager et la place $1'$, et, pour $\ell \in \llbracket 1\,,n - k \rrbracket$, le passager et la place $k + \ell$ deviennent $(\ell + 1)'$. Le passager $1'$ choisit une place au hasard parmi les $n'$ places ; chacun des suivants s'assied à sa place si elle est libre, et sinon au hasard parmi les places libres. C'est exactement le problème initial avec $n'$ passagers, et les déroulements se correspondent avec les mêmes probabilités, produits des mêmes facteurs. Le dernier passager, $n$, devient $n'$ et sa place devient $n'$, donc $$\mathrm{P}_{(C_{1} = k)}(\text{le dernier est à sa place}) = q_{n-k+1}.$$

Récurrence. La formule des probabilités totales (théorème 5), appliquée au système complet $\big((C_{1} = k)\big)_{1 \leqslant k \leqslant n}$, donne, en posant $m = n - k + 1$, $$q_{n} = \frac{1}{n}\Big(1 + 0 + \sum_{k=2}^{n-1} q_{n-k+1}\Big) = \frac{1}{n}\Big(1 + \sum_{m=2}^{n-1} q_{m}\Big).$$ Pour $n = 2$, la somme est vide et $q_{2} = \frac{1}{2}$ : le premier passager prend sa place ou celle du second. Supposons $q_{m} = \frac{1}{2}$ pour $2 \leqslant m \leqslant n - 1$. Alors $$q_{n} = \frac{1}{n}\Big(1 + \frac{n - 2}{2}\Big) = \frac{1}{n} \cdot \frac{n}{2} = \frac{1}{2},$$ et, par récurrence forte, $$\boxed{\text{le dernier passager s'assied à sa place avec la probabilité } \frac{1}{2}, \text{ quel que soit } n \geqslant 2}$$ Le calcul exact, en énumérant tous les déroulements avec leurs probabilités, le confirme pour $n \leqslant 8$ ✓.

Remarque. Le résultat s'explique sans calcul. Pour $2 \leqslant j \leqslant n - 1$, la place $j$ est occupée au plus tard quand le passager $j$ s'assied ; à l'arrivée du dernier passager, la place libre est donc la place $1$ ou la place $n$. Or, à chaque choix au hasard, tant qu'aucune des deux n'est prise, elles sont toutes deux libres et ont la même probabilité d'être choisies : celle qui est prise la première l'est avec probabilité $\frac{1}{2}$ pour chacune, et le problème se résout au moment de ce choix. La récurrence ci-dessus est la forme rigoureuse de cet argument de symétrie.