Epidémies en folie - Lycée la Versoie (Thonon les Bains) Institut Florimont (Petit Lancy, Suisse)

Titre du sujet
Epidémies en folie
Établissement
Lycée de la Versoie (Thonon les Bains)
Année
2015-2016
Etablissement(s) jumelé(s)
Institut Florimont (Petit Lancy - Suisse)
Résumé
Sur une grille de taille n*m certaines cases sont "infectées" et d'autres sont "saines".
L'infection se propage de la façon suivante :

Toutes les cases infectées restent infectées.
Toute case ayant deux cases voisines infectées qui la touche devient infectée.

A partir de cela nous devrons répondre à 2 problématiques :

- Quel est le plus petit nombre de cases infectées nécessaires pour infecter toute la grille ?
- Quel est le plus grand nombre de cases infectées qui n'infectera pas toute la grille ?

Nous pourrons ensuite développer le problème en supposant dans la grille, qu'une ou plusieurs cases sont "vaccinées" et ne pourront donc pas être infectées, en gardant bien sur les deux problématiques de départ.