Tas de cailloux
Problème
On a n (n + 1) / 2 cailloux qu'on répartis en tas. à chaque tour, on prend un caillou à chaque tas, et on forme un nouveau tas.
Montrer que
après un certain nombre d'opérations, on se retrouve avec :
- un tas de 1 caillou,
- un tas de 2 cailloux,
- un tas de 3 cailloux,
- ...
- un tas de n caillonx
Solution
On va noter : Tas_i le nombre de cailloux dans le tas indicé i. Et Op_i le nombre de cailloux dans le tas i, mais après opération.
étape : stabilité.
La solution reste stable : Tas_i = i, Op_i = i - 1 , le tas i=0 disparait, et on ajoute un tas de taille n.
Collisions
On a : \sum_{i=0}^n i = n (n + 1) / 2 . Et donc, si on a plus de n tas pour seulement n (n + 1) / 2 . pierres, alors on est certain que deux tas ont la même valeur.
Boucles
Il n'existe qu'un nombre fini de répartitions de n (n + 1) / 2 cailloux en tas. Après un certain nombre d'opérations, on est donc certain de retomber sur une répartition déjà observée, et de boucler.
Dans une boucle
Soit M le plus grand nombre de tas rencontré dans la boucle, au moment ou il y a M tas, on sait que :
- aucun autre tas de cette configuration n'a été créé à partir de plus que M (puisqu'on est dans une boucle ou M est le plus grand nombre de tas)
- Comme on crée un tas par tour, on sait aussi que l'âge de chaque tas est unique.
- on a donc des âges : 0, 1, 2, \dots, M - 1
- le tas d'âge j contient au maximum M - j cailloux.
Le nombre de cailloux dans ce cycle à M tas est donc au maximum : \frac{M(M+1)}{2}
Donc : \frac{n(n+1)}{2} \le \frac{M(M+1)}{2}
Soit : n \le M
Il nous reste à montrer le cas inverse.