Au début (étape 0), avant de lancer un programme informatique, on « contamine » un certain nombre de cases d'une grille 5×7.
Ensuite, l’ordinateur simule une contagion.
Étape après étape, chaque case non contaminée adjacente par un côté à exactement deux cases contaminées est
contaminée à son tour (les contaminées le restent, malheureusement !).
Il existe une jolie démonstration* du fait qu’il faut « contaminer » au minimum 6 cases non adjacentes deux à
deux au début pour que les 35 cases de la grille puissent être contaminées après un certain nombre d’étapes.
Dans ce cas, une contamination totale – si elle se produit – a nécessairement lieu en au plus 29 étapes.
Exemple
La grille ci-dessus permet une contamination totale en 10 étapes.
Soit N(k) le nombre de grilles de départ ayant exactement 6 cases non adjacentes contaminées, et amenant à une
contamination totale en k étapes.
Que vaut la somme des k x N(k), pour k = 1, ..., 29 ?
* On peut facilement se convaincre que durant le processus de contamination, le périmètre total de la zone contaminée est invariant. Le périmètre de la grille étant de 24 et celui d’une case de 4, il faut donc au moins 24/4 = 6 cases (non adjacentes) pour aboutir à une contamination complète.
