Défi Turing

Accueil - Enoncés -


Problème 180

La contagion

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.

précédent
suivant