Exercice 3 — Le jeu de la vie

Sujet

Séries L, ES, STM G

Le mathématicien américain John Conway a imaginé vers 1970 un jeu, appelé "Jeu de la vie" qui met en scène des cellules susceptibles de se reproduire, de disparaître ou de survivre.
Les cellules vivantes sont représentées dans ce qui suit par des cases foncées sur un quadrillage supposé illimité.
Chaque cellule est entourée de huit cases, dites adjacentes, susceptibles d'accueillir d'autres cellules ; elles sont représentées en gris clair sur la figure ci-contre.
Les règles d'évolution des cellules sont les suivantes :

• La survie : chaque cellule vivante ayant deux ou trois cellules adjacentes vivantes survit.
• La mort :

• par surpopulation : chaque cellule vivante ayant quatre cellules adjacentes vivantes ou plus disparaît.
• par isolement : chaque cellule n'ayant qu'une ou aucune cellule voisine vivante meurt d'isolement.

• La naissance : chaque emplacement adjacent ayant exactement trois cellules vivantes fait naître une nouvelle cellule vivante pour la génération suivante.
  Toutes les naissances et toutes les morts ont lieu en même temps au cours d'une génération.
  Un exemple d'évolution : (M pour mort, N pour naissance et S pour survie)

N

N

S

S

M

S

S

M

devient

N

M

M

N

qui devient

qui n'évolue pas

N

N

S

S

On appellera « motif » un ensemble de cellules « regroupées». Ainsi la figure 2 est composée d'un seul motif alors que la figure 1 est composée de deux motifs :

1 - Quel est le destin à long terme des motifs composés d'une ou deux cellules vivantes ? Expliquer.

2 - A une symétrie ou une rotation près, les motifs à trois cellules vivantes sont les suivants : Représenter l'évolution de chacun de ces motifs.

On utilisera désormais le vocabulaire suivant :

• un motif « stable» s'il est inchangé d'une génération à la suivante,
• un motif « presque stable» s'il se transforme en un motif stable en un nombre fini d'étapes,
• un motif est « à durée de vie limitée» s'il disparaît en un nombre fini d'étapes.

3 - Trouver, parmi les motifs à quatre cellules vivantes, deux motifs stables, deux motifs à durée de vie limitée et deux motifs presque stables.
4 - Déterminer tous les motifs se transformant en une seule étape en :