Découvrir Logiciels & programmation Liens Web Propriétés remarquables Recherche automatisée Documentation Zoo

Le jeu de la Vie
Vitesse limite des vaisseaux : démonstration


Histoire d'avoir les idées claires : un vaisseau (ou navire) est une structure finie (de cellules vivantes) qui, après un certain nombre de générations réapparaît, mais translatée dans une certaine direction (et avec une distance non nulle). Le plus petit nombre de générations au bout desquelles elle réapparaît translatée est sa période.

On définit la vitesse d'un vaisseau par la distance de translation (mesurée par la longueur du plus court chemin entre deux cellules : deux cellules adjacentes (cote à cote ou en diagonale) étant distantes de 1) divisée par la période.
La vitesse d'une cellule par génération est notée usuellement c, par analogie avec la vitesse de la lumière.
En effet un vaisseau ne peut avoir une vitesse égale ou supérieure à c.

Voici une démonstration.



Résultat préalable, d'après J.H.Conway (lui-même).  
Bilan : si une structure est en dessous d'une diagonale à une génération, elle est en dessous de la diagonale suivante deux générations plus tard.

A partir de là, supposons qu'en une période p, un vaisseau donné se déplace de A cases horizontalement et de B cases verticalement. Supposons de plus A et B positifs (au sens large, mais l'un des deux devant être non nul).

A t=0 le vaisseau est précisement en dessous de la diagonale d0.
D'après le résultat précédent on sait qu'à t=2n, le vaisseau est nécessairement en dessous de la diagonale d2n.

On suppose de plus que p est paire : on peut toujours se ramener à ce cas, car 2p est toujours paire est est aussi une période du vaisseau (pour un déplacement 2A, 2B).

Schema explicatif
On a donc qu'après son déplacement le vaisseau est en dessous de dp. (on est obligé de considérer p pair car dp n'est définie que pour p pair).

Or (cf. figure) à t=p le vaisseau est exactement en dessous de la droite d2(A+B) .

C'est donc que dp est au dessus de d2(A+B).
C'est à dire que :

 Psupérieur ou égal2(A+B) 
La vitesse du vaisseau étant : V = D/P
Où D est la distance en nombre de déplacement d'un roi sur un échiquier, c'est à dire le plus grand de A et de B.
Donc Dinférieur ou égal à(A+B).
On obtient alors  : Vinférieur ou égal à(A+B)/ (2 (A+B)) = 1/2.

En notant c la vitesse d'une case par génération, le résultat se met sous la forme :

Vinférieur ou égal à c/2
Voilà.

Application : le remplisseur du plan

Le remplisseur du plan est la structure dont la vitesse de croissance est la plus élevée possible.

Image du remplisseur du plan.
Cliquez ici pour le voir évoluer (Applet Java de Paul Callahan) ou sur l'image pour télécharger le fichier correspondant.

Cette structure à la propriété de s'agrandir indéfiniment en remplissant le plan de Conway de lignes horizontales vivantes et mortes alternées. Celles-ci sont limitées par 4 lignes diagonales se déplaçant précisément à la vitesse c/2.

Cette structure remarquable réalise donc la vitesse de croissance la plus élevée possible.



Retourner aux propriétés remarquables.