Es gibt ein absolut sicheres Verfahren, im Lotto sechs Richtige zu tippen: Man gebe für jede sechs-elementige Teilmenge der Zahlen von 1 bis 49 einen Tip ab. Das sind freilich 13983816 Kombinationen. Und selbst wenn man bedenkt, daß außer dem Hauptgewinn 43×6= 258 mal fünf Richtige, erheblich häufiger vier und noch mehr drei Richtige anfallen, kosten die Lottoscheine insgesamt mehr, als man gewinnt; dafür sorgen die Spielregeln der Lottogesellschaft.

Wenn man es nun aber – bescheidener – nur auf fünf Richtige anlegt? Ein einziger Tip deckt ja bereits sechs Chancen auf fünf Richtige ab; also müßte man statt 1906884 Tips (so viele Fünferkombinationen aus 49 gibt es) nur ein Sechstel dieser Anzahl abgeben und hätte mit bescheidenen 317814 Versuchen trotzdem fünf Treffer garantiert – vorausgesetzt, in all diesen Sechserkombinationen ist keine Fünferkombination doppelt enthalten. Dazu wäre die richtige Auswahl aus dem riesigen Sortiment aller Tips zu treffen: Wenn ein Tip 1, 2, 3, 4, 5, 6 lautet, darf kein weiterer die Zahlen 1, 2, 3, 4, 5 oder 1, 2, 3, 4, 6 enthalten, und so weiter.

Es stellt sich heraus, daß diese Forderung nicht erfüllbar ist: Man kann nicht alle Kombinationen abdecken, ohne einige davon mehrfach zu verwenden. Läßt sich denn aus der Not eine Tugend machen und eine Auswahl finden, die jede Fünferkombination – beispielsweise – genau elfmal enthält? Für den Lottospieler liefe das auf den elffachen garantierten Gewinn bei elffachem Einsatz hinaus (wenn man davon absieht, daß dann die Quote entsprechend absinkt).

Formalisiert lautet die Aufgabe: Zu einer vorgegebenen Menge mit v (im Beispiel 49) Elementen finde man ein Sortiment von k-elementigen Teilmengen, sogenannten Blöcken, mit der Eigenschaft, daß jede t-elementige Teilmenge in genau l Blöcken enthalten ist. Im Beispiel ist ein Block gerade ein Tip, k=6, t=5 und l=11.

Ein solches Sortiment heißt in der Mathematik ein Design; es wird charakterisiert durch die vier genannten Parameter. Man spricht von t-(v,k,l)-Designs; im Beispiel ist also ein 5-(49,6,11)-Design gesucht.

Wenn jede Fünferkombination schon mehrfach vorkommen darf, könnte es auch zweckmäßig sein, ganze (Sechser-) Blöcke mehrfach zu verwenden; aber das gilt unter Fachleuten als unsportlich. Die (schwerer zu findenden) Sortimente, in denen jeder Block nur einmal vorkommen darf, heißen einfache Designs.

Der Name Design bezieht sich auf die Planung großer Experimente (design of experiments). Zum Beispiel könnte man die Qualität von sieben verschiedenen Weizensorten vergleichen wollen; für die Aussaat stehen sieben Felder zur Verfügung, die sich in Bodenqualität, Sonneneinstrahlung oder ähnlichen Merkmalen unterscheiden. Jedes bietet Platz für drei Sorten. Damit die Qualitätsunterschiede der Felder das Ergebnis nicht verfälschen, sollte man eine möglichst bunte Verteilung der Sorten anstreben. Möglicherweise wird auch das Gedeihen einer Sorte dadurch beeinträchtigt, daß sich ein Schädling auf der nebenan gepflanzten besonders gut vermehrt; um Verfälschungen dieser Art auszuschließen, sollte jedes Paar von Weizensorten genau einmal gemeinsam auf einem Feld vorkommen. Gesucht ist also ein 2-(7,3,1)-Design (Bild 2).

Die ersten systematischen Untersuchungen zu Designs ergaben sich jedoch – Mitte des letzten Jahrhunderts – nicht aus Fragen der Versuchsplanung; Auslöser war vielmehr eine Denksportaufgabe, das Schulmädchenproblem des englischen Pfarrers Thomas Penyngton Kirkman (1806 bis 1895): Fünfzehn junge Damen einer Schule sollen sieben Tage lang in Dreiergruppen spazieren gehen, die täglich neu so einzuteilen sind, daß sich keine zwei Mädchen öfter als einmal in der gleichen Gruppe befinden – was auf die Frage nach einem 2-(15,3,1)-Design hinausläuft. (Die Forderung ist bestenfalls sieben Tage lang erfüllbar; denn nach sieben Spaziergängen war jede der Damen mit jeder ihrer 14 Kameradinnen einmal zusammen.)

Während Aufgaben dieser Größenordnung zur Not noch durch Probieren zu lösen sind, würde bei dem Lottoproblem das sture Durchtesten aller Möglichkeiten selbst die größten und schnellsten Computer der Welt überfordern. Die Theorie liefert immerhin gewisse einschränkende Bedingungen; zum Beispiel ist die Anzahl der Blöcke eines zu findenden Designs durch die Parameter vorab festgelegt. Beim Lottoproblem liefert ein Design mit n Sechserblöcken 6n Fünferkombinationen; dieser Wert muß – für l=11 – gleich elfmal der Anzahl der überhaupt möglichen Fünferkombinationen sein. Wenn also diese Anzahl nicht durch 6 teilbar ist, kann es kein Design mit der Überdeckung l=11 (oder einer anderen zu 6 teilerfremden Zahl) geben. Aber selbst für Parameterwerte, die derartigen Einschränkungen genügen, gibt es kein Konstruktionsverfahren für Designs; man weiß noch nicht einmal genau, zu welchen zulässigen Parameterkombinationen überhaupt Designs existieren.

Nun haben die Mathematiker Anton Betten, Adalbert Kerber, Axel Kohnert, Reinhard Laue und Alfred Wassermann von der Universität Bayreuth einfache Designs zu den Parametern 7-(33,8,10) und 7-(33,8,16) gefunden. Das ist deswegen bemerkenswert, weil die Aufgabe zu gegebenem t um so realitätsnäher und zugleich schwieriger ist, je kleiner die übrigen Parameter sind; denn damit schrumpft das Sortiment, das man zur Verfügung hat, um sämtliche Bedingungen zu erfüllen. Vor dieser Entdeckung hatten die kleinsten Parameter, für welche die Existenz eines 7-Designs bekannt war, astronomische Werte, nämlich v=4032015+7, k=8 und l=4032015; ein Design dieser Größe ist ohnehin kaum explizit anzugeben.

Wie findet man ein Design?

Das Problem läßt sich sehr übersichtlich in einer großen Tabelle aufschreiben. Man beschriftet die Zeilen mit allen t-elementigen und die Spalten mit allen k-elementigen Teilmengen (den potentiellen Blöcken) und schreibt eine Eins überall dorthin, wo die Zeilenmenge in der Spaltenmenge enthalten ist. Alle anderen Felder erhalten eine Null (Bild 1 links). Eine solche Tabelle heißt Inzidenzmatrix. Theoretisch ist die Lösung sehr einfach: Man greife aus der Inzidenzmatrix Spalten gerade so heraus, daß die Summe der Einsen über die ausgewählten Spalten in jeder Zeile dieselbe ist, und zwar gleich l. Nur hat diese Matrix 13884156 Spalten mit jeweils 4272048 Zeilen zur Auswahl. Schlichtes Probieren ist also aussichtslos, die Theorie nicht mächtig genug. Deswegen mußten die Bayreuther Forscher theoriegestütztes Probieren zu Hilfe nehmen. Paradoxerweise reduzierten sie das Problem in einem ersten Schritt zu erträglicher Größe, indem sie es durch Zusatzforderungen schwerer machten: Sie verkleinerten gewissermaßen den Heuhaufen, in dem sie wühlen mußten, um den beträchtlichen Faktor 2×10¹⁰ – und fanden in den beiden genannten Fällen trotzdem noch eine Stecknadel. Solches Glück ist nicht selbstverständlich, denn bei ungeschickter Wahl der Zusatzforderungen läuft man leicht Gefahr, mit dem störenden Heu auch gleich alle Stecknadeln wegzuwerfen. Was aber ist eine geschickte Wahl? Eine Zusatzforderung bewirkt, daß jeweils mehrere Spalten der Inzidenzmatrix zu einer zusammengefaßt werden, entsprechend auch Zeilen (Bild 1 rechts). Es gilt also festzulegen, was die zusammenzufassenden Spalten – und Zeilen – gemeinsam haben sollen.

Permutationen und Gruppen

Lottozahlen sind untereinander gleichberechtigt – ebenso Schulmädchen und Weizensorten. Es ändert nichts am Problem, wenn man ihre Reihenfolge verändert. Eine solche Umstellung nennt man Permutation. Man könnte also zum Beispiel fordern, ein zu findendes Design sollte alle Lottozahlen gleich behandeln in dem Sinne, daß eine beliebige Permutation es unverändert läßt.

Damit hätte man allerdings des Guten zuviel getan; denn die Lösungsmenge des so verschärften Problems wird dadurch nicht nur sehr viel kleiner, sondern leer. Bei freier Wahl der Permutationen läßt sich nämlich jeder Block in jeden anderen verwandeln. Also ist jede Spal-te der Inzidenzmatrix mit jeder anderen zusammenzufassen, desgleichen die Zeilen, und von der riesigen Tabelle bleibt nur ein einziger Eintrag übrig – zu wenig, um noch Spalten auszuwählen.

Andererseits ist ein Block – im Lottobeispiel – eine Auswahl von sechs Zahlen aus 49. In welcher Reihenfolge sie gezogen werden ist gleichgültig. Es liegt also nahe, nur solche Permutationen als belanglos anzusehen, die genau die sechs gezogenen und die 43 restlichen Elemente jeweils unter sich vertauschen, wobei aber beide Mengen sauber voneinander getrennt bleiben. Es genügt sogar, wenn die beiden Teilmengen die Zahlen von 1 bis 6 einerseits und von 7 bis 49 andererseits sind. Den Rest erledigt eine weitere Permutation. Alle Blöcke, die sich voneinander nur um eine in diesem Sinne belanglose Permutation unterscheiden, wären dann zusammenzufassen.

Das mathematische Werkzeug dafür entstammt der Gruppentheorie; deren Konzepte lassen sich hier nur mit einigen – unvermeidlich etwas gewaltsamen – Metaphern erläutern. Man identifiziere jede Permutation mit einem Tierchen, beispielsweise einem Floh. Fern jeder biologischen Realität kann man zwei beliebige Flöhe miteinander kreuzen (jeder kann sowohl Vater- als auch Mutterrolle einnehmen), wodurch wieder ein Floh entsteht. Dem entspricht, daß zwei Permutationen, hintereinander ausgeführt, wieder eine Permutation ergeben. Flöhe tragen Farben, und diese werden gesetzmäßig (aber nicht nach biologischen Gesetzen) vererbt. Es gibt einen weißen (neutralen) Floh, der nichts zur Farbe seiner Kinder beiträgt, und zu jedem Floh einen komplementären (inversen), das heißt einen, mit dem er ein weißes Kind hat. Eine Menge von Flöhen, Permutationen oder anderen mathematischen Objekten, unter denen eine Verknüpfung mit diesen Eigenschaften existiert, nennt man eine Gruppe; die Bedingungen heißen die Gruppenaxiome.


Klassenbildung

Gewisse Flöhe (Permutationen), nicht nur den weißen, möchte man nun als belanglos ansehen, das heißt, einen Floh und ein Kind, das er mit einem belanglosen Partner hat, nicht voneinander unterscheiden. Also steckt man einen Floh mitsamt allen derartigen Abkömmlingen in einen Sack. Verfährt man so mit allen Flöhen aus der Menge, so finden sie sich am Ende familienweise sortiert in Säcken wieder – vorausgesetzt, die Kinder zweier belangloser Flöhe sind stets belanglos. In der Gruppentheorie spricht man statt von Säcken von Nebenklassen.

Aus den Gruppenaxiomen folgt nun, daß die Flöhe in ihrem Reproduktionsverhalten die Sackordnung einhalten: Wenn das Kind eines Flohs aus Sack A mit einem Partner aus Sack B in Sack C gehört, dann gilt das für jede Paarung eines A-Flohs mit einem B-Floh. Wenn man wissen will, was das Ergebnis einer Kreuzung zweier Säcke ist, entnimmt man jedem einen stellvertretenden Floh und paart die beiden. Der Sack, in den das Kind gehört, ist der richtige.

Ganze Säcke verhalten sich also wieder wie Flöhe: Die Menge der Säcke bildet eine Gruppe. Insbesondere kann man unter geeigneten Bedingungen mehrere Säcke in einen Supersack (eine sogenannte Doppelnebenklasse) stecken.

Offensichtlich ist ein Sack Flöhe einfacher zu hüten, als es lauter einzelne sind. Nur die Einsortierung in die richtigen – bislang nur abstrakt definierten – Säcke ist mitunter sehr schwierig. Man muß dazu schrittweise vorgehen. Zum Beispiel hält man am Anfang nicht die ersten sechs von den letzten 43 Zahlen getrennt, sondern zunächst nur die Eins von den restlichen 48. Durch Variation dieser Umverteilung arbeitet man sich durch ein weitverzweigtes Netz von Permutationsgruppen bis zu der gewünschten vor. Das erfordert ein gehöriges Maß an Erfahrung, zumal man auf dem Weg zum Ziel immer wieder auch scheinbare Rückschritte in Kauf nehmen muß.


Spaltenauswahl

Wenn man nun Spalten und Zeilen der Inzidenzmatrix in dieselben Säcke stopft, die bei den Flöhen so gute Dienste geleistet hatten, schrumpft diese auf die erträgliche Größe von 32×97 (Bild 3). Damit ist das ursprüngliche Problem aber erst zur Hälfte gelöst; denn durch bloßes unsystematisches Probieren die richtigen Spalten auszuwählen wäre immer noch hoffnungslos aufwendig. Statt dessen nahmen die Bayreuther Forscher ein anderes Teilgebiet der Mathematik zu Hilfe: die lineare Algebra (vergleiche Spektrum der Wissenschaft, November 1995, Seite 20).

Man kann das verbleibende Problem nämlich als lineares Gleichungssystem auffassen. Dessen rechte Seite besteht aus lauter Zahlen, die gleich l sind. Es gibt nur 32 Gleichungen für 97 Unbekannte; also wäre das System eigentlich hochgradig unterbestimmt und hätte eine Fülle von Lösungen. Weil aber alle Unbekannten entweder 1 oder 0 sein müssen, je nachdem, ob die zugehörige Spalte ausgewählt ist oder nicht, wird die Menge der potentiellen Lösungen stark eingeschränkt. Man muß also in einem abstrakten Raum von 97-32=65 Dimensionen einen Punkt finden; aber alle denkbaren Punkte sind unübersichtlich verteilt und weit verstreut.

Sie systematisch abzusuchen würde zwar unerträglich lange Zeit in Anspruch nehmen; aber das Problem hat eine gutartige innere Struktur, so daß oft ein geeignetes Probierverfahren schneller zum Ziele führt. In diesem Falle erwies es sich als günstig, in dem 65dimensionalen Raum vorrangig in der Nähe des Nullpunktes nach Lösungen zu suchen. Nach allen theoretischen Vorarbeiten benötigte ein handelsüblicher Personal Computer für den letzten Schritt zum 7-(33,8,10)-Design nur noch neun Minuten.

Für den Fachmann sind diese Designs schon wegen ihrer Eleganz faszinierend; aber sind sie auch zu etwas nutze? Zunächst ist die Bayreuther Arbeit von theoretischem Interesse; denn aus Designs lassen sich andere mathematische Strukturen konstruieren, über die man bisher ebenfalls wenig weiß. Praktische Anwendungen gibt es beispielsweise beim Entwerfen fehlerkorrigierender Binärcodes für die Nachrichtenübertragung und beim Verbessern der Auflösung von Meßgeräten.

Außerdem wissen wir nun, daß man in einer Lotterie "8 aus 33" mit 5340000 Tips mit Sicherheit zehnmal sieben Richtige erzielen würde.


Aus: Spektrum der Wissenschaft 5 / 1996, Seite 18
© Spektrum der Wissenschaft Verlagsgesellschaft mbH