Ein Museumsdirektor ist sehr um die Sicherheit seiner Exponate besorgt. Er möchte schwenkbare Videokameras so installieren, dass jeder Punkt des Museums im Blickfeld von mindestens einer Kamera liegt. Wie viele Kameras sind nötig?

Das hängt natürlich vom Grundriss des Museums ab. Für viele Gebäude wird eine Kamera pro Ausstellungsraum genügen. Nicht aber für verwinkelte Museen wie etwa das Jüdische Museum in Berlin. Die Behauptung ist: Für jedes Museum mit n geraden Wänden genügen [n/3] Kameras. [n/3] steht dabei für den ganzzahligen Anteil von n/3, bei n = 11 zum Beispiel für 3, bei n = 301 für 100. Dass es tatsächlich Fälle gibt, in denen man nicht mit weniger Kameras auskommt, zeigt der kammförmige Grundriss eines (hypothetischen) Museums. Für jeden Zacken des Kamms braucht man eine eigene Kamera, da von keinem Punkt aus zwei Zackenspitzen einsehbar sind. Aber genügen [n/3] Kameras in jedem Fall?

Um das zu beweisen, stellte sich Steve Fisk vom Bowdoin College in Brunswick, Maine, vor rund 25 Jahren einen beliebigen Grundriss (mit geraden Wänden) vor. Dann verband er dessen Ecken so lange über sich nicht kreuzende Diagonalen miteinander, bis der Innenraum in Dreiecke aufgeteilt war (siehe Zeichnung rechts) und stellte eine neue Behauptung auf: Die Eckpunkte dieses Dreiecknetzes lassen sich so mit den Farben Rot, Blau und Grün färben, dass zwei Ecken, die durch eine Wand oder eine Diagonale miteinander verbunden sind, niemals dieselbe Farbe haben. In der Zeichnung sind die Ecken entsprechend koloriert. Gelingt es, die Dreifarbenaussage zu beweisen, ist der Rest einfach: Da es insgesamt n Ecken gibt, muss es eine Farbe geben, in der höchstens [n/3] Ecken angemalt sind (in diesem Fall die grünen). In jeder dieser Ecken wird eine Videokamera postiert, die das ganze Dreieck überblickt. Da jedes Dreieck eine Ecke in dieser Farbe enthält, ist jeder Punkt des Museums einsehbar.

Die Dreifarbenbehauptung bewies Fisk mit einem so genannten Induktionsbeweis - einem raffinierten mathematischen Trick, sich von Aussagen für kleine Zahlen zu solchen über große hochzuhangeln. Fisk begann mit dem einfachsten Fall: Ist n gleich 3, lässt sich natürlich jede der (drei) Ecken mit einer anderen Farbe kennzeichnen. Anschließend nahm er an, der Satz sei für alle Anzahlen von Ecken bis n-1 bereits bewiesen, und folgerte daraus seine Richtigkeit für n Ecken (n ist jetzt größer als 3). In dem Gebilde aus lauter Dreiecken wählte Fisk dazu zwei beliebige Ecken aus, nennen wir sie u und v, die über eine Diagonale miteinander verbunden sind. Diese Diagonale zerlegt das Gebilde in zwei kleinere Figuren aus lauter Dreiecken. Da diese weniger als n Ecken haben, können wir sie nach der Induktionsannahme so mit drei Farben anmalen, dass miteinander verbundene Ecken verschiedene Farben haben. Sollte nun die Ecke u in den Färbungen der beiden Teilgebilde verschiedene Farben erhalten, etwa in einem Fall Rot, im anderen Blau, wird umgefärbt: In einem der beiden Teilgebilde werden die roten Ecken zu blauen und die blauen zu roten. Genauso verfahren wir mit der Ecke v. Die Kombination der beiden Färbungen ergibt eine zulässige Färbung für das Gesamtgebilde mit n Ecken. Damit ist die Dreifarbenbehauptung bewiesen und das Museumsproblem gelöst.