La réponse du jeudi (37) : thé ou café ?
Publié le 01/10/2015

Vous pouvez retrouver cette question au format pdf.

Question du jeudi #37 : Ana aime le hasard et déteste la monotonie. Tous les matins, elle tire à pile ou face sa boisson pour le petit déjeûner : thé ou café. Elle souhaite ainsi éviter de boire la même chose trois jours de suite. Au bout de n jours, quelle est la probabilité que sa règle de non-monotonie ait été respectée ?


Au bout de $n$ jours, il y a $2^n$ « historiques » possibles pour les petits déjeûner d'Ana. On doit se demander combien d'entre eux sont « favorables », c'est-à-dire ne présentent jamais la même boisson trois jours de suite.

Imaginons qu'Ana enregistre sur une (longue) file de carreaux ses boissons, en coloriant le $n$-ième carreau en vert si elle a bu du thé, en marron si c'était du café. Pour que l'historique soit favorable, il faut que son historique ressemble à 

c'est-à-dire qu'il s'obtienne en posant à la suite des « carreaux » et des « dominos » c'est-à-dire une des quatre pièces : 
en alternant les couleurs.

Or, pour obtenir une telle frise, le choix des couleurs est en fait très limité : une fois que l'on a choisi la « forme » des pièces, par exemple 

comme dans notre exemple, il n'y a que deux choix possibles de couleurs : on peut commencer par le vert ou le marron, puis la règle d'alternance force toutes les autres couleurs.

Autrement dit, le nombre d'historiques vérifiant la règle de non-monotonie est exactement le double du nombre $F_n$ de manières de remplir un rectangle $1 \times n$ en utilisant des carreaux $1\times 1$ et des dominos $1 \times 2$.

Or, cette définition combinatoire est une des définitions possibles1des nombres de Fibonacci2 ! En effet, il est facile de voir que le nombre de tels remplissages vérifie la relation de récurrence $F_{n+2} = F_{n+1} + F_n$ : pour remplir un rectangle de longueur $n+2$, on peut soit commencer par un carreau (auquel cas il restera un rectangle de longueur $n+1$ à remplir, et donc $F_{n+1}$ possibilités), soit par un domino (auquel cas il restera un rectangle de longueur $n$ et donc $F_n$ possibilités).

La probabilité qu'Ana échappe à la monotonie est donc de \[ P_n = \frac{2 F_n}{2^n} = \frac{F_n}{2^{n-1}}.\]

Remarque : D'après la célèbre formule de Binet \[F_n = \frac 1{\sqrt 5}\left[ \left(\frac{1+ \sqrt 5}2\right)^{n+1} - \left(\frac{1-\sqrt 5}2\right)^{n+1}\right],\] la probabilité que l'on vient de donner vaut à peu près $1,45 \times (0,8)^n$, et qu'elle tend donc très vite3 vers $0$.

  • 1. On présente souvent cette définition comme : le nombre de Fibonacci est le nombre $F_n$ de manières de monter $n$ marches d'escalier en choisissant à chaque pas de sauter ou ne pas sauter une marche.
  • 2. Noter que deux conventions existent pour la numérotation des nombres de Fibonacci : celle qui est adaptée à notre définition est celle pour laquelle $F_0 = F_1 = 1$.
  • 3. Ana a plus de chances de gagner au Loto quatre fois de suite que d'échapper à la monotonie pendant un an.
 
 
 
 
 
Dernières publications