Eléments de recherche

On peut voir la situation comme un "système dynamique" : le système peut se trouver en un certain nombre d'états (ou configurations), et on passe d'un état à un autre par une loi précise. La question "Que se passe-t-il à la longue" dirige l'attention vers le comportement asymptotique du système, mais d'autres propriétés intéressantes pourront également être découvertes et étudiées par les élèves (voir plus loin).

Pour arriver à comprendre ce que la question (volontairement vague) peut vouloir dire, il est certainement nécessaire de recourir à l'expérience. La pratique du jeu, en se donnant des configurations initiales différentes, amène en général les élèves à des observations, des éléments de conjecture et des questions de représentation intéressantes et importantes.

Par exemple:

• le nombre total de billes est constant (observation triviale, mais importante)
  

• les tas finissent par disparaître (un tas de n billes disparaît en n coups)
  

• si on joue assez longtemps, on finit par retomber sur une configuration déjà rencontrée, et le système boucle indéfiniment ; d'ailleurs si on change de configuration initiale en gardant le même nombre de billes on retombe forcément sur le même cycle.
  

• il existe des configurations qui sont fixes, ie. qui sont envoyées sur elles-mêmes
  

• tout état a un unique état "successeur" (par définition), mais certains états n'ont pas d'antécédents, et d'autres en ont plusieurs.

La question de ce qu'est précisément une configuration se pose généralement assez tôt dans la recherche :

• les tas sont-ils ordonnés, par exemple de gauche à droite ? Et dans ce cas, où place-t-on le nouveau tas à chaque coup ?
  

• Garde-t-on la trace des tas qui disparaissent ?
  

• Comment représenter les tas de manière intéressante ?

Prenons ces questions en ordre inverse :

• Les élèves les plus jeunes commencent souvent par dessiner explicitement des tas de billes (en représentant les billes par des petits ronds). Les plus avancés, puis les autres lorsqu'ils se fatiguent des dessins explicites assez laborieux, prennent une représentation par des nombres : un tas est représenté par le nombre de billes qu'il contient.
  

• Il est raisonnable de ne pas garder la trace des tas qui disparaissent : sinon le nombre total de tas augmenterait indéfiniment, et l'observation que le système finit par boucler ne tiendrait plus. Remarquons que c'est l'aspect remarquable et attrayant de cette observation qui conduit à privilégier une formalisation du problème dans laquelle elle reste pertinente et démontrable. Dans la suite, on oublie donc les tas vides.
  

• On peut décider d'ordonner initialement les tas de gauche à droite d'une certaine manière, et de placer le nouveau tas toujours à gauche des précédents, d'autres conventions étant évidemment possibles. Par exemple la configuration initiale 241 donne ensuite 313. Au contraire, on peut décider que dans une configuration les tas ne sont pas ordonnés, ce qui permet de les représenter par une suite décroissante (ou croissante, autre choix) de nombres. La configuration précédente s'écrirait alors 421 et son successeur serait 331.

Il est clair que le système bouclera en général plus vite (en moins de coups) dans le cas où les tas ne sont pas ordonnés. Dans le cas où les tas sont ordonnés avec la convention ci-dessus (nouveau tas toujours à gauche), on observe néanmoins ceci par l'expérience : les tas finissent toujours par s'ordonner de manière décroissante (de la gauche vers la droite).

Dans les deux cas, un argument de finitude (effectivement trouvé par certains élèves) permet de prouver que le système est toujours "éventuellement périodique" : puisque le nombre total de billes est constant il n'y a qu'un nombre fini de configurations possibles, et donc on tombe toujours sur une configuration déjà rencontrée, à partir de quoi le système boucle.

Quelques questions restent à résoudre :

• Quelles sont les configurations fixes ? Les configurations du type n, n-1,..., 2,1 sont-elles les seules de ce type ?
  

• Quelles sont les configurations périodiques ?
  

• Comment reconnaître une configuration qui n'a pas d'antécédent ?
  

• Comment reconnaître une configuration qui a plusieurs antécédents ?
  

• Est-il vrai que, pour un nombre de billes donné, quelle que soit la configuration initiale le système boucle toujours sur le même cycle ?
  

• Peut-on estimer le nombre de coups qu'il faudra au maximum pour tomber sur un cycle ?

La dernière question est vraiment difficile et constitue un sujet de recherche pour les experts du sujet. Les autres sont plus simples et accessibles. Pour l'avant-dernière, on peut suggérer une étude systématique : étant donné un nombre n (le nombre total de billes) on représente toutes les configurations à n billes possibles, et on en fait un graphe orienté (sans forcément le dire) en reliant une configuration à son successeur (voir éléments de solution).