Invariants

Pour trouver la solution d'un problème par itérations, il est souvent plus simple de considérer ce qui ne change pas à chaque itération ... :

Exemple: On a une urne contenant $b$ billes blanches et $n$ billes noires, tant que l'urne contient au moins deux billes on procède ainsi:

• Prendre 2 billes dans l'urne,
  • Si les deux billes ont la même couleur les jeter,
  • Si les deux billes sont de couleurs différentes, jeter la bille noire et remettre dans l'urne la bille blanche,
  De plus si l'urne est vide on remet une bille noire dans l'urne.

Question:

• Montrer que ce processus termine toujours (facile)
• Quelle est, suivant $b$ et $n$, la couleur de la dernière bille dans l'urne (moins facile)

Remarques:

• Il est difficile de trouver la solution en essayant des valeurs particulières de $n$ et $b$,
• Il vaut mieux s'intéresser à ce qui ne change pas à chaque itération:
  la parité de $b$ reste la même à chaque itération !

Solution:
La dernière bille est blanche si et seulement si $b$ est impair:

• On termine toujours car, si le nombre de billes dans l'urne n'est pas nul, le nombre de billes diminue d'au moins un à chaque tirage.
• Soit $B$ le nombre de billes blanches avant un tirage, et $B'$ le nombre de billes blanches à la fin de ce tirage.
  On a les cas suivants :
  • soit les deux billes choisies sont deux billes blanches alors $B'=B-2$,
  • soit les deux billes choisies sont deux billes noires alors $B'=B$,
  • soit les deux billes sont de couleurs différentes alors $B'=B$,
  • soit l'urne était vide et on a rajouté une bille noire alors $B'=B$,
  Dans tous les cas, $B'$ est pair si et seulement si $B$ est pair.
• On arrête les tirages quand le nombre de billes est égal à un. D'après ce qui précède, à ce tirage le nombre $B_0$ de billes blanches a la même parité que $b$ :
  • Si $b$ est pair, alors $B_0$ est pair, comme $0\leq B_0\leq 1$ on a $B_0=0$ et la dernière bille est donc noire,
  • Si $b$ est impair, $B_0$ est impair, comme $0\leq B_0\leq 1$ on a $B_0=1$ et la dernière bille est blanche.