Les Cases Malades

Probleme

On part d'un quadrillage de n cases de cote (il y a donc n^2 cases). Au depart, certaines cases sont malades, les autres sont saines. Chaque jour, les cases saines qui touchent (par un cote) au moins 2 cases malades devienent malades, les cases malades restent malades.

Quel est le nombre minimum de cases initialement malades suffisant a rendre tout le damier malade (apres plusieurs jours)?

Questions supplémentaires:

• Quelle sont les positions contaminantes minimales (i.e. telles que tout devienne malade et que ce ne soit plus le cas si on enlève une case) ? Combien y en a t-il ?
• Quelles sont les positions contaminantes avec n cases ? Combien y en a t'il ?
• Quel est le temps minimal de contamination avec n cases malades initialement ? Le temps maximal ?

Solution

Ben n, sur la diagonale du damier

• ? y'en a beaucoup...
• ? y'en a beacoup mais moins qu'à la première question.
• moins que n-1 (valeur obtenue pour la configuration diagonale) et asymptotiquement plus que 7/12n. moins que n(n-1) (car on contamine au moins une case à chaque étape).