Forum de mathématiques - Bibm@th.net

Le jeu de la vie de Conway peut être modélisé à l'aide d'une suite de matrices binaires.

À chaque instant (t), on considère une matrice :

[
A_t = \left(a_{i,j}^{(t)}\right)
]

où :

[
a_{i,j}^{(t)} =
\begin{cases}
1 & \text{si la cellule } (i,j) \text{ est vivante à l'instant } t, \
0 & \text{si la cellule } (i,j) \text{ est morte à l'instant } t.
\end{cases}
]

On obtient donc une suite de matrices :

[
A_0,\ A_1,\ A_2,\ A_3,\dots
]

Le but est de déterminer la matrice (A_{t+1}) à partir de la matrice (A_t).

\section*{Nombre de voisins vivants}

Pour chaque cellule ((i,j)), on note (N_{i,j}^{(t)}) le nombre de voisins vivants à l'instant (t).

Une cellule possède au maximum 8 voisins : les cellules situées au-dessus, en dessous, à gauche, à droite et sur les quatre diagonales.

Ainsi, on a :

[
N_{i,j}^{(t)}
=============

a_{i-1,j-1}^{(t)}
+a_{i-1,j}^{(t)}
+a_{i-1,j+1}^{(t)}
+a_{i,j-1}^{(t)}
+a_{i,j+1}^{(t)}
+a_{i+1,j-1}^{(t)}
+a_{i+1,j}^{(t)}
+a_{i+1,j+1}^{(t)}.
]

Comme chaque cellule vaut soit (0), soit (1), on a :

[
N_{i,j}^{(t)} \in {0,1,2,3,4,5,6,7,8}.
]

\section*{Règle d'évolution}

Les règles du jeu de la vie sont les suivantes :

\begin{itemize}
\item une cellule vivante reste vivante si elle possède 2 ou 3 voisines vivantes ;
\item une cellule vivante meurt sinon ;
\item une cellule morte devient vivante si elle possède exactement 3 voisines vivantes ;
\item une cellule morte reste morte sinon.
\end{itemize}

Mathématiquement, on peut écrire :

[
a_{i,j}^{(t+1)} =
\begin{cases}
1 & \text{si } N_{i,j}^{(t)} = 3, \
1 & \text{si } a_{i,j}^{(t)} = 1 \text{ et } N_{i,j}^{(t)} = 2, \
0 & \text{sinon.}
\end{cases}
]

On peut aussi l'écrire sous la forme logique suivante :

[
a_{i,j}^{(t+1)} = 1
\Longleftrightarrow
\left(N_{i,j}^{(t)} = 3\right)
\text{ ou }
\left(a_{i,j}^{(t)} = 1 \text{ et } N_{i,j}^{(t)} = 2\right).
]

Ainsi, l'évolution du système peut être vue comme une relation de récurrence :

[
A_{t+1} = f(A_t),
]

où (f) est une fonction qui transforme une matrice binaire en une autre matrice binaire.

Cette évolution n'est pas linéaire. En effet, elle ne s'écrit pas sous la forme :

[
A_{t+1} = M A_t,
]

où (M) serait une matrice fixe. La règle dépend de conditions comme (N_{i,j}^{(t)}=2) ou (N_{i,j}^{(t)}=3), ce qui rend le système non linéaire.

\section*{Structures stables}

Une structure stable est un motif qui ne change pas au cours du temps.

Mathématiquement, cela signifie que :

[
A_{t+1}=A_t.
]

Plus généralement, si le motif est stable dès l'instant initial, alors :

[
A_t = A_0 \quad \text{pour tout } t \in \mathbb{N}.
]

Un exemple simple est le carré (2 \times 2) :

[
\begin{pmatrix}
1 & 1 \
1 & 1
\end{pmatrix}.
]

Chaque cellule vivante du carré possède exactement 3 voisines vivantes. D'après les règles du jeu, elle reste donc vivante.

Les cellules mortes autour du carré n'ont pas exactement 3 voisines vivantes, donc elles restent mortes.

Ainsi, ce motif vérifie :

[
A_{t+1}=A_t.
]

C'est donc une structure stable.

\section*{Oscillateurs}

Un oscillateur est un motif qui revient à sa forme initiale après un certain nombre d'étapes.

Mathématiquement, un oscillateur de période (p) vérifie :

[
A_{t+p}=A_t,
]

avec :

[
p \geq 2.
]

Un exemple classique est le clignotant, aussi appelé \emph{blinker}.

À l'instant (t), on peut avoir trois cellules vivantes alignées horizontalement :

[
\begin{pmatrix}
0 & 0 & 0 \
1 & 1 & 1 \
0 & 0 & 0
\end{pmatrix}.
]

À l'instant (t+1), ce motif devient :

[
\begin{pmatrix}
0 & 1 & 0 \
0 & 1 & 0 \
0 & 1 & 0
\end{pmatrix}.
]

Puis, à l'instant (t+2), le motif redevient :

[
\begin{pmatrix}
0 & 0 & 0 \
1 & 1 & 1 \
0 & 0 & 0
\end{pmatrix}.
]

On a donc :

[
A_{t+2}=A_t.
]

Le clignotant est donc un oscillateur de période 2.

\section*{Glisseurs}

Un glisseur est un motif qui retrouve sa forme initiale après plusieurs étapes, mais déplacée dans la grille.

Contrairement à un oscillateur classique, on n'a pas exactement :

[
A_{t+p}=A_t.
]

On a plutôt :

[
A_{t+p}=T(A_t),
]

où (T) désigne une translation du motif dans la grille.

Pour le glisseur classique du jeu de la vie, le motif retrouve sa forme après 4 étapes, mais déplacé d'une case en diagonale. On peut donc écrire :

[
A_{t+4}=T(A_t).
]

Ce type de motif montre que des règles locales simples peuvent produire un déplacement global dans la grille.

\section*{Problématique possible}

Une problématique possible serait :

[
\text{Comment une suite de matrices binaires permet-elle de modéliser le jeu de la vie de Conway ?}
]

On peut aussi choisir une formulation plus complète :

[
\text{Comment une suite de matrices binaires permet-elle de modéliser le jeu de la vie de Conway}
]
[
\text{et d'expliquer l'apparition de motifs stables ou périodiques ?}
]

\section*{Plan possible}

\subsection*{I. Modéliser le jeu par une suite de matrices}

On définit une matrice binaire :

[
A_t = \left(a_{i,j}^{(t)}\right),
]

avec :

[
a_{i,j}^{(t)} \in {0,1}.
]

Chaque matrice (A_t) représente l'état de la grille à l'instant (t).

\subsection*{II. Définir la règle de récurrence}

On calcule d'abord le nombre de voisins vivants :

[
N_{i,j}^{(t)}
=============

a_{i-1,j-1}^{(t)}
+a_{i-1,j}^{(t)}
+a_{i-1,j+1}^{(t)}
+a_{i,j-1}^{(t)}
+a_{i,j+1}^{(t)}
+a_{i+1,j-1}^{(t)}
+a_{i+1,j}^{(t)}
+a_{i+1,j+1}^{(t)}.
]

Puis on applique la règle :

[
a_{i,j}^{(t+1)} =
\begin{cases}
1 & \text{si } N_{i,j}^{(t)} = 3, \
1 & \text{si } a_{i,j}^{(t)} = 1 \text{ et } N_{i,j}^{(t)} = 2, \
0 & \text{sinon.}
\end{cases}
]

\subsection*{III. Étudier quelques motifs particuliers}

Une structure stable vérifie :

[
A_{t+1}=A_t.
]

Un oscillateur de période (p) vérifie :

[
A_{t+p}=A_t.
]

Un glisseur vérifie plutôt :

[
A_{t+p}=T(A_t),
]

où (T) est une translation du motif.

Bonjour, merci pour votre réponse !
En effet c'est cela qui me pose le plus problème... Je ne suis pas dans un lycée très exigeant mais pour ce qui est des notions, je les ai toutes vues en cours (spé et maths expertes). Peut-être que mes explications par écrit ne sont pas très claires, si vous voulez je peux vous envoyer ce que j'ai fait en Latex pour que ce soit plus clair

Bonjour à tous,
Je suis élève en Terminale et j'aimerais savoir s'il est possible que je réalise mon sujet de Grand Oral sur le jeu de la vie de John Conway, en le modélisant mathématiquement. J'ai trouvé plusieurs sites qui conseillaient de le construire en Python mais je voulais essayer de le représenter avec de réelles notions mathématiques.
J'en suis pour l'instant à une suite matricielle supposément infinie, qui peut, pour chaque cellule, prendre 0 ou 1 comme valeur en fonction du nombre de voisins et de sa valeur précédente (cf règles du jeu de la vie). J'ai donc aussi créé une deuxième suite comptant le nombre de voisins vivants parmi les 8.
A présent, j'hésite à essayer de modéliser les motifs se répétant (structures stables, oscillateurs périodiques, voire glisseurs).
J'aimerais donc avoir votre avis, car j'ai peur que mon sujet soit incomplet et/ou trop complexe pour le jury non-spécialiste....
Merci d'avance pour vos réponses et désolé pour la longueur du message !