Devinette avec des baballes

Dans le jeu suivant :

Chaque bille, quand on clique dessus, va se diviser en deux : une qui part vers la case du dessus, l'autre qui part vers la case de droite. Ces deux cases doivent être vides.

La grille est infinie.

But du jeu

libérer les trois cases du coin en bas à gauche.

configuration plus amusante

La position de départ intéressante c'est : trois cases en bas à gauche contiennent une bille : une dans le coin, une juste au dessus, une juste à droite.

Question :

Quelle taille de grille minimale faut-il pour pouvoir "vider" ces trois cases ?

Naivement, on pourrait penser que pour pousser une bille de façon à ce que toutes ses descendantes, soient à une distance de levenstein > N , il faut faire 2^N - 1 mouvements. Le problème, c'est que faire haut+droite, ou droite+haut, donne la même case. Et donc pour N = 2, on a une collision : deux billes veulent avancer sur la même case.

En N générations, la bille la plus éloignée sera à distance N+1 alors qu'on aura 2*N billes à l'écran.

Là, on a une intuition qu'il y a un problème.

Démonstration :

En affectant à chaque case, un poids : w_(x,y) qui correspond à : si une bille arrive sur cette case à partir de l'origine, quelle est la "fraction" associée ? (quand la bille se divise en deux, elle affecte la moitié de son poids à ses deux filles)

Le point est le suivant : la somme des poids des cases occupées ne change pas.

La grille a pour poids total : W = \sum_{x \geq 0} \sum_{y \geq 0} 2^{-x-y} = \sum_{x \geq 0} [ 2^{-x} \times \sum_{y \geq 0} 2^{-y} ]

W = \sum_{x \geq 0} 2^{-x} \times \sum_{y \geq 0} 2^{-y}

or : \sum_{y \geq 0} 2^{-y} = 1 + \frac{1}{2} + \frac{1}{4} \dots = 2

Et donc : W = 2 * 2

Le problème est donc : si les trois cases du bas à gauche sont prises, alors qu'elles ont comme w_(x,y) : 1, \frac{1}{2} et \frac{1}{2} donc une somme de deux, alors on devrait occuper toute une grille infinie pour libérer les cases du bas à gauche. On arrivera donc jamais en un nombre de coups finis, à libérer l'espace nécessaire pour déplacer ces cases.