Le problème des gardiens de musée

[sujet proposé par Pierre Duchet]

énoncé du sujet

pistes

documents disponibles, échos

On veut surveiller un musée. Combien de gardiens seront nécessaires, au minimum ?

 

Pour simplifier :

 

- La surface à surveiller sera délimitée par un polygone (ou plusieurs, s'il y a des obstacles)

- La position d'un gardien est indiquées par un point, intérieur à la surface du musée.

- Les gardiens peuvent voir tout autour d'eux mais ne se déplacent pas.

Exemple

 

Pour ce musée 4 gardiens suffisent.

Mais peut-être peut-on faire mieux : surveiller ce musée avec 3 gardiens seulement ou même 2 ?

Qu'en pensez vous ?

Les musées modernes ont des forme de plus en plus originales : peut-on trouver une méthode systématique (par exemple un algorithme) qui donne une solution satisfaisante pour des formes quelconques?

Quelques exemples de pistes ou d'approfondissements possibles sur le problème des gardiens de musée

(Document présenté lors de l'Atelier MATh.en.JEANS à CINE-MATH-LILLE - 30 mars 2001)

_______________________________

Le problème initial peut donner lieu à des variantes tout aussi intéressantes. Il peut également donner lieu à des sous-problèmes, c'est-à-dire des questions dont la résolution préalable semble nécessaire. Enfin, des cas particuliers peuvent sembler très intéressants : les résoudre peut être aussi difficile que de résoudre le problème initial, donc peut permettre la découverte de bonnes méthodes. Des variantes supplémentaires s'obtiennent en combinant les idées proposées.

  1. Partitionner une aire polygonale en un nombre minimum de régions convexes.
  2. Trouver pour une aire polygonale un recouvrement en un nombre minimum de régions, chacune pouvant être surveillée par un seul gardien.
  3. Etudier le cas des zones polygonales sans obstacle intérieur.
  4. Cas des musées à murs perpendiculaires.
  5. Etude en fonction du nombre de côtés. ( cf. piste 15)
  6. Un polygone (ou polyèdre) a-t-il toujours deux sommets qui se voient mutuellement ? (cf. article des collège Molière et Romain Rolland d'Ivry sur Seine)
  7. Quelles sont les performances de l'heuristique "gloutonne" ? On place un gardien à l'endroit d'où l'on voit un maximum de côtés (ou de coins, ou aire maximum...), on supprime la région surveillée et on recommence sur les morceaux restants...
  8. Comment calculer l'aire d'une figure polygonale, le volume d'un polyèdre ?
  9. Quel type de preuve peut-on imaginer pour établir que  k gardiens ne suffisent pas pour une forme donnée ?
  10. Comment résoudre une combinaison logique de plusieurs inéquations ?
  11. Décomposer la forme en pièces et reformuler le problème en termes de carte plane.
  12. Classifier les formes où  kgardiens suffisent pour  k= 1,2,...
  13. Trouver les formes les plus "complexes" au sens où elles nécessitent un grand nombre de surveillants.

    Autres pistes suggérées lors des ateliers.
  14. Peut-on trouver un système de valuation des points et une méthode de type "variationnel" pour trouver une solution ?
  15. p(n)¾[n/3], ™ pour n=5 (formes sans trou) cf. contribution du lycée La Fontaine
  16. Cas ou formes quasi-convexes avec 1 seul trou. (cf. article du collège Molière)
  17. Notion de "forme" comme classe d'équivalence de géométries "angulaires" (importance des situations des coins par rapport aux droites).
  18. Obstacles au lieu de trous.
  19. Étudier le problème suivant le nombre "d'anses rentrantes" (= les parties à rajouter pour rendre la forme convexe)

Documentation disponible sur le problème des gardiens de musée.

Articles, publications

Contributions, échos.