Exercice 1 — Les lampadaires

Sujet

Le plan d'un lotissement de maisons est donné sous la forme d'un quadrillage composé de cinq lignes et cinq colonnes numérotées de 1 à 5 . Les maisons de ce lotissement sont représentées par des carrés grisés.

Figure 1

On souhaite éclairer l'ensemble du lotissement à l'aide de lampadaires.
Un lampadaire éclaire toute la ligne et toute la colonne à partir de la case sur laquelle il est positionné (tant que la lumière qu'il émet ne rencontre pas de maison ou la frontière du lotissement).
Par exemple, sur la figure 1 , un lampadaire positionné en ( \(2 ; 3\) ) ( \(2^{\mathrm{e}}\) ligne et \(3^{\mathrm{e}}\) colonne) éclairera les cases \((2 ; 1),(2 ; 2),(2 ; 3),(3 ; 3)\) et \((4 ; 3)\).

1. Combien de lampadaires faut-il placer au minimum pour éclairer l'ensemble du lotissement de la figure 1 ? À quelles positions les placer?
2. Si le lotissement ne contient aucune maison, combien de lampadaires faut-il placer au minimum pour l'éclairer entièrement? À quelles positions les placer?
3. Dessiner le plan d'un lotissement pour lequel il faut placer sept lampadaires au minimum pour l'éclairer entièrement.
4. Combien de lampadaires faut-il utiliser au minimum pour éclairer l'ensemble des lotissements suivants?

Figure 2

Figure 3