Es geschah während der monatlichen Vorstandssitzung der Firma Schwätzer & Co. Der Chef, Schwätzer persönlich, rief mit unverkennbarer Befriedigung den letzten Tagesordnungspunkt auf: die Sammlung Wahrlos. Es war geplant, sie in einer supermodernen Gale-rie unterzubringen, die dem Gesamtwerk des unvergleichlichen Sandy Wahrlos gewidmet werden sollte. Schwätzer war stolzer Besitzer sämtlicher Werke dieses Künstlers (siehe Illustration unten).

"Die Sicherheit ist ein wichtiger Faktor", meinte der Finanzchef.

"Selbstverständlich werden wir die Sammlung Wahrlos mit den allerneuesten Überwachungsanlagen ausstatten", entgegnete Siegfried Köter, der Leiter der Sicherheitsabteilung. "Jedes Bild wird mit einer eigenen Mini-Kamera überwacht."

"Nein, ich möchte etwas Ausgefallenes für die Wahrlos-Sammlung ", unterbrach ihn Schwätzer.

"Aha, wie ausgefallen?"

"Sehr ausgefallen. Ich will Wächter haben, lebende Wächter."

"Aber Chef, ist das nicht zu anspruchsvoll? Bedenken Sie allein die Kosten für die Sicherheitsüberprüfung der Leute und die Uniformen – und den Kantinenzuschuß erst! Echte Leute kosten echtes Geld. Nein, ich empfehle die neuesten Schnüffel-Roboter von der renommierten Firma ..."

"Ich möchte Wächter, Herr Köter."

"Jawohl, Chef. Wie viele denn?"

"So viele, daß jeder Quadratzentimeter des Gebäudes für mindestens einen Wächter im Blickfeld liegt. Ich will, daß jeder von ihnen auf einem Drehstuhl sitzt, so daß sie alle einen Rundumblick haben. Stellen Sie so viele ein, wie dafür nötig sind, aber nicht einen mehr, ist das klar? Echte Leute kosten echtes Geld, Sie wissen ja..."

"Jawohl, Herr Direktor. Sind die Pläne für das Gebäude schon fertiggestellt?"

"Noch nicht."

"Wie soll ich dann wissen, wieviele Wächter gebraucht werden?"

"Der Architekt hat beschlossen, daß das Gebäude ebenerdig sein und 24 Wände haben wird, das bedeutet eine für jede von Wahrlos' Schaffensperioden. Wir machen das so: Weil Sie mit unvollständigen Informationen arbeiten müssen, ermächtige ich Sie, so viele Wächter einzustellen, wie erforderlich sind, um einen beliebigen Raum, der von 24 Wänden begrenzt wird, vollständig überwachen zu können. Dabei muß jeder Wächter eine feste Position einnehmen und einen Rundumblick haben. Ich will aber keinesfalls, daß Sie mehr einstellen als nötig. Sollte sich herausstellen, daß weniger Wächter benötigt werden als das theoretische Maximum, so übernehme ich die Verantwortung. Für den Fall, daß kein denkbarer Grundriß der Galerie so viele Wächter benötigt, wie Sie einstellen, – tja, dann hoffe ich sehr, daß Sie jemanden finden, der Sie einstellt, Herr Köter. "

Wenn Mathematiker mit Sternen spielen

Ein leitender Angestellter, dessen Job in Gefahr ist, fackelt nicht lange. Er engagiert auf Firmenkosten den besten und teuersten Berater, den er finden kann, und gibt das Problem an ihn weiter. Köter suchte im Branchenfernsprechbuch und stieß auf die Mathematik-Service Rainer Zufall und Anna Lühse GmbH .

"Das ist eine harte Nuß, Herr Köter", meinte Zufall.

"Wirklich hart", sagte Anna Lühse, die bereits die Lösung kannte. Aber es ist kaufmännisch ungeschickt, das dem Kunden allzufrüh zu erzählen.

"Es gibt nämlich", sagte Zufall, "unheimlich viele Möglichkeiten, 24 Geraden anzuordnen."

Die beiden hatten die Angewohnheit, abwechselnd zu sprechen.

"Und die Anzahl der Wächter, die Sie benötigen, hängt von der gewählten Anordnung ab."

"Glücklicherweise gibt es ein paar gute Lösungsverfahren. Unter Fachleuten spricht man dabei von Kunstmuseumstheoremen."

"Ja, genau. Wenn etwa für einen Raum ein Wächter ausreicht, nennen wir den Raum sternförmig."

"Das bedeutet, es gibt einen Punkt im Inneren oder auf dem Rande des Raumes, so daß jeder andere Punkt im Raum mit ihm durch eine Gerade verbunden werden kann, die innerhalb des Raumes verläuft."

"Nun stellen Sie sich vor, es sind etliche Wächter irgendwie im Raum verteilt. Dann sitzt jeder von ihnen in einem sternförmigen Gebiet – nämlich dem Teil des Raumes, den er überblicken kann. Ihre Frage lautet nun..."

"Wie hoch ist die minimale Anzahl sternförmiger Gebiete, in die man einen Raum mit 24 Wänden zerlegen kann?", murmelte Zufall, während er auf seinen Notizblock krakelte (Bild 1 links).

"Zeichnen Sie Grundrisse?" fragte Köter und betrachtete Zufalls Skizze.

"Gewiß. Wir reden zwar von Räumen, aber auf die dritte Dimension kommt es hier nicht an. Für diesen speziellen Raum mit einer bestimmten Anordnung von drei Wächtern", fuhr Zufall fort, "sieht man, daß er bis auf sechs verschiedene Gebiete einsehbar ist."

"Und diese Gebiete sind konvex, also sternförmig", bemerkte Anna.

"Plaziert man also in jedes dieser Gebiete einen weiteren Wächter, kann man den Raum vollständig überwachen."

"Großartig", sagte Köter. "Ich benötige also neun Wächter?"

Die Mathematiker schüttelten mit wissendem Blick den Kopf.

"Keineswegs. Zum einen reicht eventuell eine Anordnung mit weniger Wächtern für diesen speziellen Raum aus."

"Zum anderen braucht man für einen anderen Raum vielleicht doch mehr."

"Heißt das, ich brauche neun, es können aber auch mehr sein oder weniger?"

"Genau."

"Sagen Sie mal, wie hoch ist eigentlich Ihr Honorar?"

"Ach wissen Sie, wir wollten Ihnen nur erst einmal ein Gefühl für die Problematik vermitteln", sagte Zufall mit charmantem Lächeln.

"Selbstverständlich müssen wir hier systematisch vorgehen", beeilte sich An-na Lühse hinzuzufügen.

"Wir müssen den Raum in einfachere Teile zerlegen und diese dann möglichst effizient zu sternförmigen Gebieten zusammensetzen."

"Triangulieren heißt das Zauberwort. Dreiecke sind das Natürlichste."

"Schon, aber es gibt sehr viele verschiedene Möglichkeiten, einen Raum in Dreiecke zu zerlegen."

"Klar. Ich schlage vor, wir machen es, ohne neue Ecken einzuführen."

"Du meinst, wir nehmen nur die Ecken, die der Raum ohnehin schon hat?" fragte Zufall.

"Sicher."

"Geht denn das immer?"

"Ich kann es dir beweisen."

"Nein, mach weiter."

"Als nächstes färbt man alle Eckpunkte des Raumes mit drei verschiedenen Farben – etwa Rot, Gelb und Blau –, und zwar so, daß in jedem Dreieck jede Farbe genau einmal vorkommt."

"Man färbt zunächst die Ecken irgendeines Dreiecks mit verschiedenen Farben. Für jedes angrenzende Dreieck sind die Farben dann eindeutig bestimmt, denn es ist genau eine Ecke eines solchen Dreiecks noch nicht gefärbt. Auf diese Weise arbeitet man sich systematisch durch alle Dreiecke durch."

"Ach so." Köter nickte eifrig. "Und was passiert, wenn wir dieses Verfahren auf Herrn Zufalls Beispiel anwenden?"

"Man erhält sechs rote Ecken, neun blaue und neun gelbe. Setzt man nun in jede rote Ecke einen Wächter, dann haben die insgesamt den totalen Überblick, denn wenn man in der Ecke eines Dreiecks sitzt, überblickt man zumindest das ganze Dreieck" (Bild 1 rechts).

"Und jedes Dreieck hat genau eine rote Ecke. Natürlich. Das ist hübsch." Köter war überglücklich, daß endlich wieder sein Problem zur Sprache kam. "Wir brauchen also nur sechs Wächter für diesen Raum. Und wir setzen sie in die roten Ecken."

Anna Lühse zeigte nur den Anflug eines spöttischen Lächelns und wandte sich an ihren Kollegen: "Ich hoffe, du siehst, wie man diese Idee verallgemeinern kann?"

"Sicher. Ein Raum mit 24 Wänden hat 24 Ecken. Wir teilen ihn in Dreiecke auf, färben die Ecken nach deinen Regeln und wählen die Farbe aus, die am seltensten auftritt. Die Wächter setzen wir in die Ecken mit dieser Farbe."

"Ganz recht. Die Gesamtanzahl aller roten, blauen und gelben Ecken beträgt 24. Unabhängig davon, wie die Farben den Ecken zugeordnet sind, tritt mindestens eine höchstens achtmal auf."

"Du meinst, wenn die Summe dreier Zahlen 24 ergibt, dann kann nicht jede von ihnen gleich oder größer als neun sein? Ja, das verstehe ich."

Anna Lühse deutete eine Verbeugung an. "Damit habe ich bewiesen, daß jeder beliebige Raum mit 24 Wänden von acht Wächtern überwacht werden kann."

"Moment mal", sagte Köter, welcher aufmerksam zugehört hatte und dem Schwätzers Drohung nicht aus dem Kopf ging. "Gerade haben Sie gesagt, daß für diesen speziellen Raum nur sechs Wächter gebraucht würden und nicht acht."

"Das ist korrekt, Herr Köter. Aber wir suchen die kleinste Anzahl von Wächtern, die für einen beliebigen Raum mit 24 Wänden benötigt werden. Und wir haben soeben bewiesen, daß es höchstens acht sein müssen."

"Und wie soll ich meinem Chef begründen, daß es auch im allgemeinen Fall nicht mit weniger geht?"

"Das ist ganz einfach", meinte Zufall und griff zum Notizblock. "Wir geben ein Beispiel an, bei dem genau acht Wächter benötigt werden" (Bild 2). "Die Wächter müssen so plaziert werden, daß sie die acht dreieckigen Alkoven überblicken können. Das ergibt acht sich nicht überschneidende Gebiete. Also muß jedes von ihnen mit einem anderen Wächter besetzt sein. Andererseits zeigt die Anordnung, daß acht Wächter ausreichend sind."

"Aber Sie haben sie nicht in die Ecken gesetzt", protestierte Köter.

"Wir könnten, und das ist für den allgemeinen Beweis sehr hilfreich", sagte Zufall. "Aber wir müssen nicht, und in diesem Falle ist es anders einfacher."


Die allgemeine Lösung des Problems

"Sehr schön", meinte Köter. "Acht Wächter. Ich werde dem Chef sagen, daß das Problem gelöst..." Das Telephon läutete. Köter hob den Hörer ab, sagte einige Male sehr beherrscht "Jawohl, Chef" und legte sorgfältig auf. Dann nahm er sich unvermittelt die nächste greifbare Blumenvase, schleuderte sie durchs Zimmer und brüllte unzusammenhängendes Zeug.

"Ist irgend etwas nicht in Ordnung, Herr Köter?" fragte Anna Lühse mit einem Unterton, den sie für taktvoll hielt.

"Dieser dämliche Architekt hat die Pläne geändert!" schrie Köter. "Die Galerie soll jetzt 173 Wände haben, damit die Bilder nach Themen und nicht nach Stilperioden geordnet werden können."

"Kein Problem, Herr Köter." Zufall faßte ihn beruhigend am Arm. "Da unsere Methode allgemein gilt, kann man sie auch in diesem Falle anwenden. Sie färben die Ecken des Raumes nach Anna Lühses Regel und postieren die Wächter an den Ecken, deren Farbe am seltensten vorkommt. Beträgt nun die Summe dreier Zahlen 173, so kann eine von ihnen allenfalls 173/3=57 2/3 sein."

"Soll das heißen, ich brauche 57 2/3 Wächter? Teilzeitarbeit schätzt der Chef nicht besonders."

"Nein, es bedeutet nur, daß eine der Farben höchstens 57mal auftaucht. Sie kommen also mit 57 Wächtern aus – aber im allgemeinen nicht mit weniger. Das sieht man an einem Beispiel mit entsprechend mehr Alkoven."

"Wir haben folgendes bewiesen", sagte Anna Lühse. "Für einen Raum mit n Ecken braucht man [n/3] Wächter. Die eckigen Klammern stehen für das Abrunden nach unten: [n/3] ist die größte ganze Zahl, die kleiner ist als n/3. Die- se Lösung des Problems stammt von dem tschechischen Mathematiker Václav Chvátal aus dem Jahr 1973. Der Beweis, den ich vorgeführt habe, ist eine Vereinfachung des ursprünglichen, den Steve Fisk vom Bowdoin-College in Brunswick (Maine) 1978 gefunden hat, und -"

Das Telephon läutete erneut. Nach dem Gespräch sank Köter hilflos grinsend in seinen Sessel. "Sie werden es mir nicht glauben, aber schließlich hat der Architekt sich doch für den Raum mit 24 Wänden entschieden. Man konnte sich über die Zuordnung der Bilder zu den verschiedenen Themen nicht einigen. Gut, Sie schicken mir die Rechnung und bis nächsten Donnerstag einen vollständigen Bericht mit einer Zusammenfassung für den Vorstand. Ich habe einen Termin mit Herrn Schwätzer."

"Können wir auch dabei sein?" fragte Anna Lühse. "Wir würden den großen Schwätzer gerne kennenlernen. Wer weiß, wann sich noch einmal so eine Gelegenheit bietet."

Köter dachte einen Augenblick nach und stimmte dann zu. Es würde nichts schaden, die beiden Experten als moralische Unterstützung dabei zu haben. Es konnte ja doch noch heikle Rückfragen geben.

"Acht Wächter, sagen Sie? Gute Arbeit, Herr Köter." Schwätzer war hocherfreut. "Das trifft sich gut. Der Architekt hat nämlich soeben den endgültigen Grundriß der Galerie vorgelegt. Sie können mir jetzt zeigen, wo die Wächter plaziert werden müssen." Er breitete die Pläne auf dem Tisch aus (Bild 3).


Und was tut man mit den Löchern?

Köter warf einen kurzen Blick darauf, schluckte trocken und wandte sich dann mit verzweifelter Miene an die Mathematiker. Zufall flüsterte seiner Kollegin zu: "Au weia, Pfeiler. Kein Mensch hat etwas von tragenden Systemen in dem Raum gesagt. Das bedeutet, die entsprechende zweidimensionale Skizze ist mit Löchern durchsetzt. Acht Wächter werden dafür nicht reichen, das sehe ich schon mit bloßem Auge."

"Nein. Hm. Es gibt da eine Vermutung über das Flächenproblem, daß im Falle von n Seiten und l Löchern – "

"Sind da auch die Seiten der auftretenden Löcher mitgezählt?"

"Was? Ja, natürlich – daß die maximale Anzahl von benötigten Wächtern [(n+l)/3] beträgt. Nach diesen Plänen ist n=24 und l=3, also müßten auf jeden Fall neun Wächter -"

"Was haben Sie denn da zu flüstern?" unterbrach Schwätzer die Diskussion der Mathematiker mißtrauisch.

"Oh entschuldigen Sie, Herr Direktor. Wir – äh – bewundern die Pläne des Architekten."

Anna Lühse gab Köter einen verstohlenen Wink. "Nun, wie Herr Köter ganz richtig sagte, können Sie bei 24 Wän-den mit acht Wächtern auskommen. Plus einem Vorsteher, selbstverständlich: Irgend jemand muß ja schließlich die Verantwortung tragen und schauen, daß die Aufsicht nicht nachlässig geführt wird. Nicht wahr, Herr Köter?"

Der Sicherheitsabteilungsleiter, dem mittlerweile der Schweiß auf der Stirn stand, riß sich noch einmal zusammen. "Aber klar, Frau Lühse, an den Vorsteher hatte ich selbstverständlich schon gedacht – allein schon wegen der Bedeutung der Sammlung."

"Sie brauchen also insgesamt neun Wächter, Herr Direktor", bekräftigte Rainer Zufall. Genauso, wie Herr Köter es Ihnen gesagt hat."

"Sie können das alles in der Zusammenfassung nachlesen, Chef", sagte Köter, der sich wieder gefangen hatte.

Er warf den Mathematikern einen Seitenblick zu und wurde mit fast unmerklicher Zustimmung belohnt. Neun Wächter. War das nicht die Zahl, mit der sie angefangen hatten? Egal, das Problem bestand nun darin, die Wächter richtig zu plazieren. Die Mathematiker würden sicher wissen, wohin.

Indes beschlich Köter das Gefühl, daß in diesem Moment der Stundensatz um einiges angehoben wurde. Aber das war ein anderes Problem – nicht seins, sondern das des Finanzchefs.

Literaturhinweise

- Mathematical Gems II. Von Ross Honsberger. Mathematical Asssociation of America, 1976.

– Old and New Unsolved Problems in Plane Geometry and Number Theory. Von V. Klee und S. Wagon. Mathematical Association of America, 1991.

– Unsolved Problems in Geometry. Von Hallard T. Croft, Kenneth J. Falconer und Richard K. Guy. Springer, 1991.


Aus: Spektrum der Wissenschaft 9 / 1994, Seite 12
© Spektrum der Wissenschaft Verlagsgesellschaft mbH