Probleme – Le sac de billes

1. Les deux candidats naturels échouent, et spectaculairement. Partant du sac $\{1\}$, un coup peut le remplacer par un milliard de billes de valeur $0$ : le nombre de billes est passé de $1$ à $10^9$, et leur somme de $1$ à $0$ — donc la somme, elle, a bien baissé. Mais partons de $\{2\}$ : on peut le remplacer par $\{1,1,\dots ,1\}$ avec un milliard de $1$, et la somme passe de $2$ à $10^9$. Ni le cardinal ni la somme ne décroissent.

Pire : aucune quantité bornée d'avance ne peut convenir, puisque le joueur choisit combien de billes il ajoute, après que la quantité a été fixée.

2. L'ordre multi-ensemble. Un sac est un multi-ensemble d'entiers ; représentons-le par la suite de ses effectifs, lue des plus grandes valeurs vers les plus petites :

$$\Phi (S)=(e_K,e_{K-1},\dots ,e_1,e_0),$$

où $e_j$ est le nombre de billes valant $j$ et $K$ un majorant fixé des valeurs présentes. On compare deux sacs par l'ordre lexicographique sur ces suites.

Cet ordre est bien fondé sur ${\mathbb{N}}^{K+1}$ à $K$ fixé — c'est l'ordre lexicographique du cours, itéré. Et $K$ ne bouge jamais : un coup ne crée que des valeurs strictement inférieures à celle qu'il retire, donc le maximum ne peut qu'être conservé ou baisser.

Un coup fait strictement décroître $\Phi$. Le coup retire une bille de valeur $k$ : la composante $e_k$ baisse de $1$. Les composantes $e_K,\dots ,e_{k+1}$, elles, sont inchangées — aucune bille ajoutée ne vaut $k$ ou plus. Sur la première composante qui change, on a donc baissé : la suite est lexicographiquement plus petite, quoi qu'il arrive aux composantes $e_{k-1},\dots ,e_0$, qui peuvent exploser.

C'est exactement le mécanisme d'Ackermann, à ceci près qu'il y a $K+1$ composantes au lieu de deux : on s'autorise n'importe quelle explosion à droite pourvu qu'on gagne un rang à gauche.

3. Non, le nombre de coups n'est pas borné, et c'est ce qui rend le résultat frappant. Mesures, pour la stratégie qui remplace systématiquement chaque bille $k\ge 1$ par dix billes de valeur $k-1$ :

Une seule bille de valeur $5$ mène à $11111$ coups. Et rien n'empêche de remplacer par un million au lieu de dix : le nombre de coups devient astronomique, sans jamais devenir infini.

Six parties jouées au hasard depuis $\{6\}$, avec au plus huit billes ajoutées par coup, se sont terminées en $1$, $1$, $2$, $22$, $28$ et $40$ coups.

La morale, et elle est le cœur du chapitre. « Ce processus termine » et « je peux dire en combien de temps » sont deux affirmations sans rapport. La première se prouve avec un ordre bien fondé ; la seconde demande un majorant, et il n'y en a pas ici. Le joueur peut retarder la fin aussi longtemps qu'il veut — il ne peut pas l'empêcher, et c'est tout ce que l'ordre bien fondé affirme.

Prolongement. Le même argument, avec des ordinaux à la place des suites finies, démontre la terminaison du jeu de l'hydre de Kirby et Paris — un résultat vrai que l'arithmétique de Peano ne peut pas prouver. La frontière entre « termine » et « on peut prouver que ça termine » est plus proche qu'on ne croit.