CultureMath

Vous pouvez retrouver cette question au format pdf.

Question du jeudi #20 : Dans un damier $n \times n$, les cases peuvent être allumées ou éteintes. Ensuite, le damier évolue selon la règle suivante : les cases ne s'éteignent jamais, et une case s'allume à une étape donnée si au moins deux de des voisines sont allumées. (On appelle voisines deux cases qui ont un côté en commun. Ainsi, une case a, suivant sa position sur le damier, deux, trois ou quatre voisines).

Voici un exemple de disposition initiale qui aboutit, après un nombre fini d'étapes, en un damier complètement allumé :

Quel est le nombre de cases minimal qu'il faut allumer au début du processus pour aboutir à un damier complètement allumé ?

La réponse est qu'il faut allumer au minimum $n$ cases pour aboutir à un damier complètement allumé.

Les configurations initiales à $n$ cases qui conviennent sont nombreuses, mais le plus simple est probablement d'allumer une diagonale du damier. On vérifie aisément qu'après $n-1$ étapes, le damier est totalement allumé.

L'autre sens est plus délicat : il s'agit de montrer que si le damier comporte initalement moins de $n$ cases allumées, le processus n'aboutira pas au damier totalement allumé.

Pour cela, nous allons montrer qu'étape après étape, le périmètre de la zone allumée (en comptant les côtés qui sont au bord du damier) ne peut que décroître.

En effet, imaginons qu'à chaque étape, on allume les nouvelles cases une par une plutôt que toutes ensemble. Quand on allume une nouvelle case, le périmètre de la zone allumée croît de $(4-v) - v = 4 - 2v$, où $v$ est le nombre de voisines de la case qui étaient allumées.

Par définition, $v \geq 2$ (c'est la condition pour qu'une case soit allumée1). On a donc $4- 2v \leq 0$, ce qui montre que le périmètre décroît au sens large.

Si on aboutit à un damier complètement allumé, le périmètre de la zone allumée au début de l'évolution doit donc valoir au moins $4n$ (le périmètre du damier tout entier). Ainsi, chaque case ayant quatre côtés, il faut au moins $n$ cases allumées sur le damier initial.

• 1. Remarquons que $v$ n'est pas le nombre $v_0$ de voisines de notre case qui sont allumées à l'étape précédente. Puisque dans ce raisonnement, on allume les cases les unes après les autres, il est possible que $v > v_0$. Mais on a simplement besoin de l'inégalité $v \geq 2$, donc cette subtilité ne nous gêne pas dans la preuve.