problème des gardiens de musée

Imaginez une salle dont le plan forme un polygone, avec des recoins qui peuvent masquer une partie du sol. Un gardien reste immobile, mais regarde dans toutes les directions. Il voit un point si une ligne droite peut relier ses yeux à ce point sans sortir de la salle.

Le problème consiste à placer le moins de gardiens possible sans laisser de zone cachée. Le nombre de côtés donne une garantie valable même pour les formes les plus défavorables.

Le problème des gardiens de musée est un problème de visibilité dans une salle modélisée par un polygone simple à parois rectilignes. Les gardiens occupent des positions fixes et voient dans toutes les directions. Un point est surveillé lorsque le segment qui le joint à au moins un gardien reste entièrement dans le polygone, bord compris. L'objectif est de couvrir ainsi toute la salle avec un nombre minimal de gardiens et de déterminer leurs positions.

Le nombre de côtés, noté n, commande une garantie universelle. Le théorème de la galerie d'art affirme qu'un nombre de gardiens égal à la partie entière de n divisé par 3 suffit toujours : $\lfloor n\mathrm{/}3\rfloor \backslash lfloor\; n/3\; \backslash rfloor$. Victor Klee a formulé le problème en 1973, puis Václav Chvátal a démontré ce théorème en 1975.

Cette quantité est une borne de pire cas, pas le minimum propre à chaque salle. Certaines formes demandent effectivement ⌊n/3⌋ gardiens, tandis qu'une salle convexe peut être entièrement visible depuis un seul point intérieur.

Considérons une salle convexe à huit côtés. Les données sont les suivantes :
• le nombre de côtés est n = 8 ;
• les murs forment un polygone convexe ;
• le gardien reste au centre de la salle.

1. On divise le nombre de côtés par trois : 8 ÷ 3 = 2, avec un reste de 2.
2. On prend la partie entière du quotient : ⌊8/3⌋ = 2.
3. Le théorème garantit donc qu'au plus deux gardiens suffisent, quelle que soit la forme simple de cette salle à huit côtés.

Ici, la convexité donne mieux que la garantie générale : un seul gardien suffit. Depuis le centre, chaque segment menant à un point de la salle reste dans le polygone. La figure matérialise cette visibilité par des segments allant du gardien aux huit sommets.

Le contrôle est refaisable : on compte huit côtés, puis on vérifie que chaque segment tracé reste dans la salle. Le minimum de cet exemple est donc 1, tandis que la borne de pire cas vaut 2.

Pour un plan polygonal simple, la borne ⌊n/3⌋ fournit d'abord un nombre de gardiens toujours suffisant. Elle est utile lorsqu'on veut une garantie avant de rechercher des positions plus économes.

Si la salle est convexe, on préfère le constat direct de visibilité : un seul point intérieur suffit. Le critère observable est l'absence de recoin qui ferait sortir de la salle un segment de visée.

Si le plan comporte des recoins, il faut tester les segments de visée depuis les positions envisagées. La borne répond à la question « combien suffisent toujours ? » ; l'étude de la forme répond à la question « combien faut-il ici ? ».

La borne universelle et le minimum d'une salle. La valeur ⌊n/3⌋ garantit un effectif suffisant dans le pire des cas. Pour l'octogone convexe de l'exemple, elle vaut 2, mais le minimum réel vaut 1.

Un gardien fixe et une patrouille mobile. Le modèle impose une position fixe et une vision dans toutes les directions. Une personne qui se déplace peut atteindre successivement des zones invisibles depuis un point unique, mais elle ne résout pas le même problème.

Le plan doit relever du modèle polygonal simple. Des murs courbes, des obstacles intérieurs ou des trous changent les hypothèses. Le symptôme est qu'un unique contour rectiligne ne décrit plus la zone à surveiller ; il faut alors employer un modèle adapté avant de chercher une borne.

La partie entière est indispensable. Pour huit côtés, 8/3 vaut 2 plus 2/3, mais ⌊8/3⌋ vaut exactement 2. Arrondir au nombre entier le plus proche donnerait 3 et ne reproduirait pas l'énoncé.

Une borne suffisante n'impose pas autant de gardiens. Le nombre ⌊n/3⌋ peut être nécessaire pour certaines salles, pas pour toutes. Si une position unique voit chaque point, comme dans l'octogone convexe, il faut retenir le minimum 1 plutôt que la borne 2.

La visibilité est géométrique. Tourner le regard ne contourne pas un mur : le segment reliant le gardien au point observé doit rester entièrement dans la salle. Dès qu'il franchit l'extérieur, il faut choisir une autre position ou ajouter un gardien.

Qu’est-ce qu’un polygone ? précise le vocabulaire géométrique du contour qui modélise la salle.

La fiche coloration d'un graphe ouvre sur l'outil combinatoire qui intervient dans une démonstration classique du théorème.