All groups

Navigation

edit SideBar

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).
Edit - Attach - History - Print - Recent Changes - Search - Login - Logout
This page is part of the group Énigmes
Page last modified on 2010-07-23 at 18h16