Exercice 2 — Colorier la grille

Sujet

Une grille \(a \times b\) est un quadrillage d'un rectangle qui comporte \(a\) cases sur une dimension et \(b\) cases sur l'autre.

Une grille \(3 \times 3\)

Dans une telle grille deux cases sont dites voisines si elles se touchent par un côté ou par un sommet. On appelle case intérieure, toute case qui n'est pas en contact avec un bord de la grille.
On veut colorier les cases de telles grilles en noir ou blanc en utilisant la règle suivante :

• toute case noire intérieure doit avoir exactement cinq cases voisines blanches,
• et toute case blanche intérieure doit avoir exactement quatre cases voisines noires.

1. Réaliser un tel coloriage sur une grille \(3 \times 3\) avec une case noire au centre, puis avec une case blanche au centre.
2. Montrer qu'une grille \(3 \times 3\) coloriée en utilisant la règle comporte exactement 4 cases noires.
3. Réaliser un tel coloriage avec un nombre minimal de cases noires

• sur une grille \(3 \times 4\).
• sur une grille \(3 \times 5\).
• sur une grille \(9 \times 9\).
• sur une grille \(8 \times 9\).

Justifier dans chacun des cas pourquoi le nombre de cases noires trouvé est minimal.
4. Réaliser un tel coloriage avec un nombre maximal de cases noires

• sur une grille \(3 \times 4\).
• sur une grille \(3 \times 5\).
• sur une grille \(9 \times 9\).
• sur une grille \(8 \times 9\).

Justifier dans chacun des cas pourquoi le nombre de cases noires trouvé est maximal.