Wie viele Versuche sind erforderlich, um in einer einzigen Ziehung der klassischen Lotterie (»6 aus 49«) mit Sicherheit einen Hauptgewinn zu erzielen? Die Antwort ist ebenso einfach berechenbar wie ernüchternd: Es sind ungefähr 14 Millionen. Genauer: Es handelt sich um die Anzahl der Möglichkeiten, aus 49 Gegenständen sechs auszuwählen. Da derartige Fragestellungen häufig vorkommen, gibt es dafür einen eigenen Namen (Binomialkoeffizient), ein Symbol – die zwei Zahlen übereinander in Klammern, aber ohne Bruchstrich – und eine Berechnungsformel, die in diesem Fall lautet:

\[\binom{49}{6} = \frac{49\cdot48\cdot47\cdot46\cdot45\cdot44}{1\cdot2\cdot3\cdot4\cdot5\cdot6} = 13\ 983\ 816 \]

Erstaunlicherweise lässt sich eine ganz ähnliche Frage bei einer Lotterie, die auf den ersten Blick nur geringfügig anders aussieht, überhaupt nicht einfach beantworten: Aus einem Sack mit elf Kugeln, die mit 1 bis 11 nummeriert sind, werden Kugeln gezogen, es bleibt aber unbekannt, wie viele. Es können alle elf sein oder auch gar keine. Die Aufgabe besteht darin, zu erraten, welche Kugeln gezogen wurden. Anders ausgedrückt: Zu jeder der elf Nummern muss man das Votum 0 (»Kugel im Sack«) oder 1 (»Kugel draußen«) abgeben, und eine bessere Strategie als schlichtes Raten gibt es nicht.

Dann braucht man 2¹¹ = 2048 Versuche, um mit Sicherheit elf Richtige zu erzielen; so weit nicht schwer. Aber variieren wir das Problem ein bisschen. Angenommen, in einer Multiple-Choice-Klausur sind elf Fragen mit Ja oder Nein zu beantworten, und ich habe nicht die geringste Ahnung von dem Stoff, der abgefragt wird. Raten ist die einzig mögliche Strategie. Immerhin gilt die Klausur als bestanden, wenn acht der elf Fragen richtig beantwortet sind.

Rainer Rosenthal, Ingenieur aus Überlingen am Bodensee, hat dasselbe Problem in einer Newsgroup, in der er gern interessante mathematische Fragen zur allgemeinen Diskussion stellt, noch ein bisschen abstruser formuliert: »Ich habe hier eine Liste mit elf Fragen, die mit Ja oder Nein zu beantworten sind, die ich aber niemandem zeige. Wer wenigstens acht davon richtig beantwortet, bekommt einen Preis. Welche Mathelehrerin kann es schaffen, dass jemand aus ihrer Klasse sicher einen Preis gewinnt? Wie groß muss die Klasse mindestens sein, und welche Lösungsvorschläge führen zum Ziel?«

Alle Möglichkeiten durchprobieren

Die naive Methode, alle Kombinationen von elf Ziffern 0 oder 1 durchzuprobieren, führt mit Sicherheit zum Ziel, erfordert allerdings eine Klasse von 2048 Schulkindern. Das ist definitiv zu viel des Guten, denn acht Richtige reichen ja bereits aus. Ein bisschen Herumrechnen mit Binomialkoeffizienten liefert folgendes Ergebnis: Unter sämtlichen 2048 möglichen Kombinationen gibt es genau einmal elf Richtige, elfmal zehn, 55-mal neun und 165-mal acht Richtige. Alle übrigen 1816 Lösungen bekommen keinen Preis. Es genügen also 1817 Schulkinder, die nach wie vor lauter verschiedene Lösungen einreichen müssen, um auf jeden Fall einen Treffer zu landen.

Auch dieser Ansatz ist noch nicht besonders ergiebig. Aber es reicht ja, sicherzustellen, dass beispielsweise die ersten acht Fragen richtig beantwortet werden. Auf die letzten drei kommt es dann nicht mehr an. Also bittet die Lehrerin die Kinder, alle möglichen Kombinationen der acht ersten Ziffern anzukreuzen und die letzten drei nach Belieben zu wählen. Offensichtlich ist dann mindestens ein Kind dabei, das zumindest knapp bestanden hat. Nur braucht das immer noch 2⁸ =256 Kinder, ein bisschen viel für eine Schulklasse.

Ein Teilnehmer der Diskussionsgruppe namens Fritz Feldhase hat eine bessere Strategie gefunden, indem er eine erleichterte Version des Problems studierte. Statt acht sollen schon sechs richtige Antworten für einen Erfolg genügen. Dann genügen nämlich bereits zwei Kinder. Wie das? Eins kreuzt zu jeder Frage irgendeine Antwort an und das andere jedes Mal das genaue Gegenteil. Das reicht! Nehmen wir an, Kind A hat drei Richtige und entsprechend acht Falsche, dann muss Kind B drei Falsche und acht Richtige haben. Einerlei, wie Richtig und Falsch im Einzelfall verteilt sind, ein Kind hat auf jeden Fall mindestens sechs Richtige. Im allgemeinen Fall sind das halb so viele, wie es Fragen gibt, und bei ungeraden Fragenzahlen wird aufgerundet. Es kann nämlich nicht sein, dass beide Kinder weniger als die Hälfte der Fragen richtig beantwortet haben.

Zurück zum ursprünglichen Problem. Wir wenden die Feldhase-Strategie auf die letzten sieben Fragen an, indem jeweils zwei Kinder sie genau entgegengesetzt beantworten. Das gibt auf jeden Fall vier Richtige aus diesen sieben. Für die ersten vier Fragen greifen wir wie oben zu dem Mittel der erschöpfenden Suche. Wir bilden also 16 Kinderpaare, die sich jeweils nach dem Feldhase-Prinzip ergänzen. Jedes Paar kreuzt eine der 2⁴ = 16 Möglichkeiten an. Dann hat auf jeden Fall eines von ihnen die vier ersten Fragen sämtlich richtig beantwortet, und aus diesem Paar hat ein Partner mindestens weitere vier Richtige, womit das Ziel erreicht ist. Eine Klasse mit 32 Kindern hat demnach einen garantierten Erfolg.

Damit sind wir schon bei realistischen Klassengrößen angelangt. Aber geht es noch besser?

Ein Ausflug ins Elfdimensionale

Ein brauchbarer Hinweis kommt aus der Geometrie. Allerdings muss man sich dafür in den elfdimensionalen Raum begeben, und der wirkt zumindest beim ersten Besuch etwas unübersichtlich. Ein Punkt in diesem Raum ist nichts weiter als eine Folge von Zahlen (ein »Vektor«) der Länge 11. So ist auch jeder Lösungsversuch für unsere seltsame Klausur ein solcher Elfervektor, mit Komponenten, von denen jede entweder 0 oder 1 ist.

In unserem vertrauten dreidimensionalen Raum bilden die acht Vektoren, deren Komponenten 0 oder 1 sind, einen Würfel. Entsprechend sind die denkbaren Klausurlösungen die 2048 Ecken des »Einheitswürfels im elfdimensionalen Raum«. Wenn zwei Ecken des gewöhnlichen Würfels sich nur in einer Koordinate unterscheiden, dann sind sie durch eine Kante verbunden. Das soll auch für den elfdimensionalen Einheitswürfel gelten. Nur gehen hier von jeder Ecke elf Kanten aus.

Um sich in diesem Raum besser zurechtzufinden, führt man so etwas wie eine Entfernungsmessung (»Metrik«) ein. Die Entfernung zwischen zwei Ecken des Einheitswürfels wird definiert als die Anzahl der Kanten, die man durchlaufen muss, um von der einen Ecke zur anderen zu gelangen – auf kürzestem Wege, versteht sich. Sie ist gleich der Anzahl der Koordinaten, in denen sich die beiden Elfervektoren unterscheiden. Man nennt sie auch »Hamming-Distanz« nach dem Mathematiker Richard Wesley Hamming (1915–1998), der diesen Abstandsbegriff für die Konstruktion fehlerkorrigierender Codierungen verwendete. In vertrauterem Gelände, genauer gesagt in der schachbrettförmig angelegten Innenstadt von Manhattan, kennt man eine derartige Entfernungsmessung als die »Taxifahrer-Metrik«: Die Entfernung von A nach B ist nicht etwa der Abstand in Luftlinie, sondern die Anzahl der Wege von Kreuzung zu Kreuzung, die man im Straßennetz zurücklegen muss.

Haben wir eine Metrik, können wir auch von Kugeln sprechen. Wie in der vertrauten Geometrie ist die Kugel mit Mittelpunkt M und Radius r die Menge aller Punkte, die von M die Entfernung höchstens r haben. Man darf sich nicht daran stören, dass in der Taxifahrer-Metrik die Kugeln sehr eckig aussehen. Und im elfdimensionalen Einheitswürfel kann man sich eine Kugel ohnehin nicht vorstellen. Selbst wenn man ihn in den dreidimensionalen Raum abbildet, wird die Sache wegen der schieren Anzahl der Punkte äußerst unübersichtlich. Um wenigstens einen gewissen Eindruck zu vermitteln, habe ich mich bei der Abbildung auf sieben statt elf Dimensionen beschränkt:

Wozu das ganze Gerede über eckige Kugeln im elfdimensionalen Raum? Um die Aufgabe, eine minimale Menge von Lösungsversuchen zu finden, die garantiert acht Richtige enthält, aus einem neuen Blickwinkel anzusehen. Es geht nämlich darum, den elfdimensionalen Einheitswürfel mit möglichst wenigen Kugeln mit Radius 3 zu überdecken. Warum Radius 3? Wenn die unbekannte Würfelecke, die der richtigen Lösung entspricht, in einer solchen Kugel liegt, dann weicht der Mittelpunkt der Kugel an höchstens drei Stellen von dieser Ecke ab, wird also als Lösung akzeptiert. Da wir aber die richtige Lösung nicht kennen, müssen wir sicherstellen, dass jede Ecke des Einheitswürfels in einer solchen Dreierkugel liegt.

In der Taxifahrer-Metrik ist die Aufgabe, ganz Manhattan mit Kugeln zu überdecken, überraschend einfach. Man könnte daher auf die Idee kommen, Kugeln in irgendeiner Weise symmetrisch auf dem Einheitswürfel anzuordnen. Das misslingt.

Der Einheitswürfel ist zwar in geradezu vorbildlicher Weise symmetrisch: Alle Ecken sehen mitsamt ihrer Umgebung gleich aus, und eine geeignete Drehung bildet den ganzen Würfel auf sich selbst ab sowie eine beliebig vorgegebene Ecke auf eine andere, ebenfalls beliebig vorgegebene. Aber das hilft nicht. Anscheinend ist jede Kugel mit Radius 3 nicht nur eckig, sondern auch irgendwie stachelig, so dass zwei von ihnen nicht gutwillig aneinanderpassen.

Immerhin: Eine unserer Kugeln enthält \[ \binom{11}{0} + \binom{11}{1} + \binom{11}{2} + \binom{11}{3} = 1 + 11 + 55 + 165 = 232\] Punkte (einen für den Mittelpunkt; elf, um genau eine abweichende Koordinate auszuwählen; und so weiter). Wenn es also gelänge, sie so anzuordnen, dass keine zwei Kugeln einen Punkt gemeinsam haben, dann bräuchte man immer noch 2048/232 = 8,83 oder aufgerundet neun Kugeln. Weniger als neun Kinder darf die Schulklasse also mit Sicherheit nicht haben.

Der Computer liefert zunächst nur uninteressante Lösungen

An dieser Stelle kommt die Strategie »wildes Herumprobieren« ins Spiel, und damit der Computer. Der arbeitet nach folgendem Algorithmus: Wähle per Zufall eine Ecke auf dem Einheitswürfel, streiche alle Ecken, die zu der Dreierkugel um diese Ecke gehören, wähle per Zufall eine noch vorhandene Ecke und so weiter, bis die Menge aller 2048 Punkte erschöpft ist. Das funktioniert theoretisch, liefert aber in der Praxis zunächst – bei den ersten paar Millionen Versuche – nur uninteressante Lösungen: Eine, die 32 oder mehr Kugeln braucht, findet man auch ohne Computersuche. Man muss also das Probieren strukturierter gestalten.

Für Kugeln mit Radius 1 ist das Problem intensiv studiert worden, und zwar nicht nur für einen hochdimensionalen Einheitswürfel, sondern ganz allgemein für einen Graphen, das heißt eine Menge von Punkten (»Knoten«), die durch Kanten miteinander verbunden sind. Dabei interessiert überhaupt nicht, wo in irgendeinem Raum die Knoten liegen, sondern nur, welcher Knoten mit welchem eine Kante teilt.

Dieses Problem der minimalen Knotenüberdeckung (»minimum vertex cover«, MVC) ist von großer praktischer Bedeutung. So stehen zum Beispiel die Knoten für einzelne Dörfer und die Kanten für Telefonleitungen zwischen den Gemeinden. In gewissen Dörfern sollen Vermittlungsstellen eingerichtet werden mit der Eigenschaft, dass jedes Dorf über eine Kante unmittelbar an eine Vermittlungsstelle angebunden ist. Gesucht ist ein Netz mit möglichst wenig Vermittlungsstellen.

Das MVC-Problem gehört zur Klasse NP-vollständig, was ungefähr so viel bedeutet wie schwer, oder genauer, dass der Aufwand zur Lösung exponentiell mit der Problemgröße (Anzahl der Knoten) ansteigt. So weit die Theorie. In der Praxis gibt es Verfahren, die für so ziemlich alle Graphen wesentlich schneller eine Lösung finden. Dabei besteht die Kunst darin, bei der Auswahl der Kugelmittelpunkte nicht allein den Zufall, sondern eine sogenannte Heuristik walten zu lassen: eine Faustregel, deren Nützlichkeit man nicht beweisen kann – es gibt immer exotische Fälle, in denen sie in die Irre führt –, die aber eine gewisse Plausibilität für sich hat.

Die erste Faustregel lautet: Nimm bevorzugt die reichen Knoten. Dabei ist unter dem »Reichtum« eines Knotens die Anzahl der Kanten zu verstehen, die zu ihm gehören. Das scheint vernünftig, weil man auf diese Weise mit einem Kugelmittelpunkt die zahlreichen Knoten an den Enden der Kanten mit erledigt. Die zweite Faustregel erscheint weniger einleuchtend, ist aber am Ende sogar wichtiger: Bediene bevorzugt die armen Knoten. Das heißt, wähle als Kugelmittelpunkt einen der wenigen Knoten, die mit dem Ärmsten der Armen durch eine Kante verbunden sind. Unter jenen wenigen Knoten wähle den reichsten. Dieses Prinzip kennt man von den Pflasterungsaufgaben, bei denen eine merkwürdig geformte Fläche durch Bausteine aus einem vorgegebenen Sortiment auszufüllen ist. Auch da bedient man zuerst die problematischen Stellen, die wenig Auswahlmöglichkeiten bieten, um sich nicht aus Versehen einen der wenigen überhaupt möglichen Lösungswege zu verbauen.

Ein ausgeklügelter Algorithmus

Für unser Problem »acht Richtige aus elf« erweist sich eine ganz ähnliche Heuristik als zielführend. Der Mathematiker und Computerenthusiast Martin Väth, der bei Google in Zürich arbeitet, setzt die erste Kugel irgendwohin, zum Beispiel in den Punkt (0, 0, …, 0). Wegen der Symmetrie des Einheitswürfels kommt es auf diese Wahl nicht an. Alle weiteren Kugeln setzt er möglichst nah an den bereits etablierten Kugelhaufen, denn wer dazwischen eine Lücke aus nur wenigen Punkten lässt, kommt später in die Verlegenheit, für deren Füllung eine ganze Kugel zu investieren, also volle 232 Punkte zu verschwenden, wo vielleicht nur fünf wirklich gebraucht wurden. Andererseits darf er die neue Kugel nicht zu dicht an die alten setzen, sonst gibt es bereits dort Verschwendung durch doppelt bedeckte Punkte. Ein gewisser Überlapp lässt sich allerdings nicht vermeiden, weil die Kugeln so stachelig sind. Es gilt also wie beim Zusammenleben der Stachelschweine ein diffiziles Gleichgewicht zwischen Nähe und Distanz aufrechtzuerhalten.

Im Übrigen verwendet Väths Algorithmus die übliche Technik des »Backtracking«: Er verwirft nicht einfach einen Kugelhaufen, der sich als ungünstig herausgestellt hat, sondern wirft nur die letzte Kugel heraus und legt an ihrer Stelle eine neue, erst wenn das alles nicht hilft, entfernt er die zwei letzten Kugeln und setzt die Suche von dieser Konfiguration aus fort, und so weiter.

Auf diese Weise fanden Väth und andere Lösungen mit 16 Kugeln. Väth ließ daraufhin seinen Algorithmus ein paar Tage laufen und erhielt dabei 186 190 Lösungen derselben Größe. Die Anzahl wird allerdings weniger eindrucksvoll, wenn man bedenkt, dass ohnehin aus jeder Lösung durch Symmetrieoperationen – vertausche zum Beispiel die Reihenfolge der Antworten, oder ersetze in einer beliebigen Koordinate alle Nullen durch Einsen und umgekehr – sehr viele entstehen. Es ist auch nicht ohne Weiteres zu erkennen, ob zwei Lösungen aus dem umfangreichen Sortiment durch irgendwelche Symmetrieoperationen auseinander hervorgehen. Deswegen bleibt vorläufig die Frage offen, wie viele wesentlich verschiedene Sechzehner-Lösungen es gibt.

Wir wissen auch nicht, ob die Anzahl 16 der Kugeln vielleicht doch noch zu unterbieten ist. Der Anschein spricht dagegen; es ist äußerst unplausibel, dass zwischen fast 200 000 Sechzehner-Lösungen keine einzige Fünfzehner zu finden ist, wenn es überhaupt welche gibt. Und natürlich lässt die Tatsache, dass 16 eine Zweierpotenz und damit ein Teiler der Gesamteckenzahl 2048 ist, die Vermutung aufkommen, die Anordnung der 16 Punkte sei in irgendeiner Weise regulär, die einem aber nicht ins Auge springt. Hier wartet ein Problem noch auf seine endgültige Lösung.