Museumswächter: Warum n/3 Wachen reichen
Über diese App
Ein Museumsgrundriss zerfällt in Dreiecke, die Ecken bekommen drei Farben, und Wächter auf der seltensten Farbe sehen alles. So wird Fisks Beweis sichtbar, dass ⌊n/3⌋ Wächter immer reichen. Im freien Modus ziehst du Ecken, stellst Wächter selbst auf und siehst exakt, was noch niemand sieht.
Mit Erklärmodus: Ein KI-Tutor führt dich durch die App, zeigt in der Szene, worauf es ankommt, und beantwortet deine Fragen.
Der Satz von Chvátal und Fisks Beweis
Ein Museum hat einen Grundriss mit n Ecken, dessen Wände sich nicht kreuzen. Wächter stehen still und sehen in gerader Linie, nur Wände versperren die Sicht. Václav Chvátal bewies 1975: ⌊n/3⌋ Wächter reichen immer. Steve Fisk fand 1978 einen Beweis in wenigen Zeilen. Man zerlegt den Grundriss mit Diagonalen in Dreiecke und färbt die Ecken mit drei Farben, sodass jedes Dreieck alle drei trägt. Die seltenste Farbe kommt höchstens ⌊n/3⌋-mal vor. Stellt man auf jede ihrer Ecken einen Wächter, steht in jedem Dreieck einer und sieht es ganz.
Was die App zeigt
Ein Museum mit Wänden, Boden und Bildern zerfällt Schritt für Schritt: Diagonalen schneiden Ohr für Ohr Dreiecke ab, dann bekommen die Ecken rückwärts ihre Farben, zusätzlich als Kreis, Quadrat und Dreieck. Eine Zählkarte stapelt die Ecken je Farbe und zeigt die Linie bei n/3. Wächter erscheinen auf der seltensten Farbe, ihr Licht flutet Dreieck für Dreieck den Raum, eine Schraffur zeigt, was noch niemand sieht. Der Kamm beweist, dass die Schranke scharf ist: Jede Zinkenspitze sieht man nur aus dem eigenen Zinken.
Selbst ausprobieren
Im freien Modus ziehst du Ecken, fügst neue auf einer Wand ein oder löschst sie; die App lässt keine sich kreuzenden Wände zu und färbt live neu. Wächter setzt und verschiebst du selbst, ihr Sichtbereich wird exakt berechnet, die Anzeige nennt den eingesehenen Anteil in Prozent. Vorlagen sind Galerie, Kamm, Stern, L-Halle mit Nische, Spirale und Zufall. Im Stern und in der L-Halle genügt ein einziger Wächter, beim Kamm braucht jede Zinke ihren eigenen.
Häufige Fragen
- Was ist das Museumsproblem?
- Das Museumsproblem (englisch art gallery problem) fragt, wie viele fest stehende Wächter ein Raum mit n Ecken braucht, damit jeder Punkt von mindestens einem Wächter gesehen wird. Victor Klee stellte die Frage 1973, Václav Chvátal beantwortete sie 1975: ⌊n/3⌋ Wächter reichen immer, und manche Grundrisse brauchen so viele.
- Wie funktioniert der Beweis von Fisk?
- Der Grundriss wird mit Diagonalen in n − 2 Dreiecke zerlegt. Die Ecken lassen sich mit drei Farben färben, sodass jedes Dreieck alle drei Farben hat. Eine der drei Farben kommt höchstens ⌊n/3⌋-mal vor. Wächter auf diesen Ecken sehen jedes Dreieck ganz, weil jedes Dreieck eine Ecke dieser Farbe hat.
- Braucht man immer n/3 Wächter?
- Nein. ⌊n/3⌋ ist der schlimmste Fall. Ein konvexer Raum oder ein Stern kommt mit einem Wächter aus, und auch Nischen brauchen nicht je einen eigenen. Erreicht wird die Schranke etwa beim Kamm: Jede Zinkenspitze ist nur aus dem eigenen Zinken sichtbar, k Zinken brauchen k Wächter.
- Was kann ich in der App ausprobieren?
- Fisks Beweis in acht Schritten ansehen, Grundrisse wie Galerie, Kamm, Stern oder Spirale laden, Ecken ziehen, einfügen und löschen, Wächter selbst aufstellen und am Prozentwert und an der Schraffur ablesen, ob alles bewacht ist.
Fach: Aus Erdős' BUCH
Mehr aus Aus Erdős' BUCH
Eine VisuApp von heyprof: interaktiv, kostenlos im Browser, ohne Anmeldung. Was ist eine VisuApp? · Alle Apps