© HONGQI ZHANG, 123RF

Manche mathematischen Spielereien klingen zunächst, als wären sie kinderleicht zu lösen. Doch wer das tatsächlich versucht, merkt, wie schnell er sich daran die Zähne ausbeißen kann.

Es war vor fast 20 Jahren, im lauen Sommer 1996. Ich verdiente gerade mein Geld als Entwickler bei einer bekannten Softwareschmiede im Münchner Osten, als ein Arbeitskollege aufgeregt von einem einfach klingenden, aber offenbar schwer zu lösenden Problem berichtete:

Der Rektor einer Schule sieht sich mit der Aufgabe konfrontiert, neun Lehrer, 27 Schülerinnen und 18 Schüler derart in neun täglich wechselnde Gruppen einzuteilen, dass die Schüler an jedem Tag mit anderen Lehrern und anderen Mitschülern in der Klasse sitzen. Jede Gruppe soll aus genau einem Lehrer, zwei Buben und drei Mädchen bestehen, und pro Tag finden neun Gruppensitzungen in verschiedenen Klassenräumen statt, jeweils geführt von einem der insgesamt neun Lehrer. Wie viele Tage lang könnte die Schule nun den Unterricht durchziehen, ohne dass sich die Besetzung der Gruppen überlappt? Vielleicht fünf?

“Nichts leichter als das!” riefen meine Kollegen und ich sofort, legten die Projektarbeit kurzfristig auf Eis und begannen, die ersten Programme in unsere Workstations zu klopfen. Abbildung 1 zeigt den ersten Versuch mit einem einfachen Algorithmus, der pro Tag neun Gruppen mit immer den gleichen Lehrern und noch nicht eingeteilten Schülern auffüllt. Dabei führt er Buch darüber, wer schon mit wem zusammen war, und nimmt für eine Gruppe im Überlappungsfall einfach den nächsten Schüler aus dem noch nicht eingeteilten Kontingent.

Abbildung 1: Wer die Gruppen der Reihe nach mit Schülern auffüllt, schafft nicht mal zwei Tage ohne Überlappungen.

Die Lehrer sind mit dem Buchstaben »i« (für Instructor) von 1 bis 9 durchnummeriert, die Buben von »b1« bis »b18« (Boy) und die Mädchen mit »g1« bis »g27« (Girl). So leitet zum Beispiel Lehrer »i1« am ersten Tag die Klasse im Gruppenraum 1, und zwar mit den Schülern »b1« und »b2« und den Schülerinnen »g1« , »g2« und »g3« :

day1 group1: i1 b1 b2 g1 g2 g3

Am zweiten Tag stellt der Algorithmus in Gruppe 1 fest, dass die Buben »b1« und »b2« am Vortag schon mit Lehrer »i1« zusammen waren, und teilt Letzterem deswegen »b3« und »b5« zu. So geht das eine Weile.

Allerdings ist schon gegen Ende des zweiten Schultags Schicht im Schacht, denn für Gruppe 7 finden sich keine Schülerinnen mehr: »g19« , »g20« und »g21« waren schon am ersten Tag mit »i7« in Gruppe 7. »g22« , »g23« und »g24« waren mit »b15« in Gruppe 8. Und »g25« , »g26« und »g27« waren mit »b17« in Gruppe 9, also steckt das Verfahren fest!

Schwer verschätzt

Nach einigen Fehlversuchen begann uns langsam zu dämmern, dass dies wohl etwas mehr Hirnschmalz und Rechenleistung erfordert, als zunächst angenommen. Also begannen die ersten Informatiker damit, unsere damals brandheißen HPUX-Workstations mit Backtracking-Algorithmen zu traktieren.

Zur allgemeinen Überraschung stellte sich jedoch nach einigen Stunden gnadenloser Brute-Force-Attacken kein Erfolg, sondern allgemeine Ernüchterung ein. Es gab einfach viel zu viele Kombinationen, die alle durchzuprobieren von vornherein zum Scheitern verurteilt war. Keiner, weder ein Jungfuchs noch ein alter Hase, hatte eine Lösung für auch nur mehr als zweieinhalb Tage.

Wo Hilfe suchen? Das Internet steckte 1996 noch in den Kinderschuhen, insbesondere das Web war völlig unbrauchbar, weil es hauptsächlich aus “Homepages” bestand, die aufgeregt mit »BLINK« -Tags und den schaufelnden Bauarbeitern des “Under Construction”-Zeichens warben. Google kam erst zwei Jahre später, also hätte ich etwaige Lösungen, selbst wenn es sie gegeben hätte, in Bergen von Spam- Seiten nie gefunden. Aber das Usenet gab es schon und wurde hauptsächlich von Universitätsangestellten frequentiert, also machte ich mich daran, das Problem auf der Newsgroup »rec.puzzles« zu schildern und die Gemeinde dort um Hilfe zu bitten ([2], Abbildung 2).

Abbildung 2: Der Usenet-Artikel von 1996, mit dem alles anfing.

Antikes Internet hilft

Ein paar Tage später kam die Antwort eines Mathematikers namens Barry Wolk von der Universität Manitoba in Kanada. Er hatte das Problem mit schweren Geschützen diskreter Mathematik gelöst: einem Galoiskörper mit neun Elementen und neun daraus generierten, zueinander orthogonalen Lateinischen Quadraten (Latin Squares, [3], [4]). Ich fabrizierte aus seinen glasklaren und selbst für Laien verständlichen Instruktionen schnell ein Perl-Skript, das im Bruchteil einer Sekunde eine Lösung für nicht nur fünf, sondern neun Tage ausspuckte (Abbildung 3). Ich war der Held!

Abbildung 3: In Sekundenschnelle druckt der diskret-mathematische Ansatz eine Lösung für insgesamt neun Tage aus.

Der kanadische Mathematiker schlug vor, eine Sammlung von Lateinischen Quadraten zu konstruieren. Diese matrixförmigen, an Soduko-Rätsel erinnernden Gebilde, an denen schon der kauzige Mathematiker Leonhard Euler im 18. Jahrhundert seine Freude fand, enthalten die Zahlen von 1 bis n pro Spalte oder Reihe genau einmal.

Abbildung 4 zeigt ein Lateinisches Quadrat der Dimension 9×9 mit den Zahlen 1 bis 9. Wer durch die Spalten und Reihen fährt, kann leicht feststellen, dass sich keine einzige Zahl – weder auf der Senkrechten noch auf der Waagrechten – jemals wiederholt. Euler füllte seine Quadrate damals übrigens statt mit Zahlen mit lateinischen Großbuchstaben A, B, …, so kam der “lateinische” Namenszusatz zustande.

Abbildung 4: Beispiel für ein Lateinisches Quadrat, hier in der Größe 9×9.

Monsterquadrate

Für das Zusammenwürfeln von Schülern zu Gruppen an mehreren Tagen fehlt bei den Quadraten aber noch eine weitere Dimension: Hierzu benötigt man insgesamt n-1 dieser Lateinischen Quadrate, die zueinander orthogonal sind, was heißt, dass, wenn man ein Monsterquadrat aus der Überlagerung der x-/y-Werte aller Quadrate erzeugt, die erzeugten Kombinationen alle eindeutig sind.

Abbildung 5 zum Beispiel zeigt vier zueinander orthogonale Lateinische Quadrate (Mutually Orthogonal Latin Squares, MOLS) der Dimension 5×5 [5]. Von Bedeutung sind aber jetzt nur die blau eingezeichneten Werte, die schwarzen Werte am Rand kommen erst später zum Zuge.

Abbildung 5: Da 5 eine Primzahl ist, sind vier zueinander orthogonale Lateinische Quadrate (MOLS) schnell generiert.

Alle vier Quadrate elementweise zusammengefasst ergeben das Megaquadrat in Abbildung 6, dessen Einträge jeweils aus den entsprechenden Werten der vier Originalquadrate an der gleichen Position bestehen. In den Originalen stehen zum Beispiel in der vierten Reihe der ersten Spalte die Werte 5, 4, 3 und 2, weshalb im überlagerten Quadrat an derselben Stelle der Wert 5432 steht.

Abbildung 5 zusammengefasst ergeben lauter eindeutige Kombinationen.” width=”300″ height=”143″ /> Abbildung 6: Die vier MOLS aus der Abbildung 5 zusammengefasst ergeben lauter eindeutige Kombinationen.

Testlauf mit 5×5

Aus diesem Megaquadrat lassen sich die gesuchten Gruppen sehr einfach so zusammenstellen, dass es an mehreren aufeinanderfolgenden Tagen zwischen den Teilnehmern zu keinerlei Überlappungen kommt. Da es sich nur um 5×5-Quadrate handelt, kann das Verfahren nur fünf Tage lang jeweils fünf Gruppen mit jeweils vier (n-1) Teilnehmern erzeugen, also etwa einem Lehrer (von insgesamt fünf), einem Schüler (von ebenfalls fünf) und zwei Schülerinnen (von insgesamt zehn). Abbildung 7 zeigt das Ergebnis, das praktisch nur eine simple Transformation der Einträge des Megaquadrats in Abbildung 6 ist.

Abbildung 7: Gruppen aus je einem Lehrer, einem Schüler und zwei Schülerinnen aus vier 5×5 MOLS.

Das Skript in Listing 1 wandert von links nach rechts und von oben nach unten durch die Einträge und münzt sie auf die Personen um. Der Eintrag »1111« wird so zu »i1 b1 g1 g6« , denn es handelt sich um den ersten Lehrer, den ersten Buben, die erste Schülerin aus der ersten Gruppe und die erste Schülerin aus der zweiten Gruppe. Der Eintrag »3524« wird entsprechend zu »i3 b5 g2 g9« und so weiter.

#!/usr/bin/perl -w
use strict;
my @lineup  = qw( 0 2 3 4 1 );
my $size    = scalar @lineup;
my @as      = qw( 1 2 3 4 );
my @squares = ();
for my $aidx ( 0..$#as ) {
  for my $ridx ( 0..$#lineup ) {
    for my $cidx ( 0..$#lineup ) {
      my $row = $lineup[ $ridx ];
      my $col = $lineup[ $cidx ];
      my $a = $as[ $aidx ];
      my $v = ( $a * $row + $col ) % $size;
      $squares[ $aidx ]->[ $ridx ]->[ $cidx ]
        = $v + 1;
    }
  }
}
for my $day ( 1..$size ) {
  for my $group ( 1..$size ) {
    my @v = ();
    for my $sidx ( 0..$size-2 ) {
      push @v, $squares[ $sidx ]->
         [ $day - 1]->[ $group - 1 ];
    }
    my( $i, $b, $g1, $g2 ) = @v;
    $g2 = $g2 + $size;
    print "day$day group$group:",
     " i$i b$b g$g1 g$g2\n";
  }
  print "\n";
}

Wie die Wurst gemacht wird

Wie aber erzeugt das Skript anfangs die vier zueinander orthogonalen Lateinischen Quadrate, aus denen sich dann mühelos die Gruppeneinteilung ableiten lässt? Da es sich um Quadrate der Dimension 5×5 handelt und 5 eine Primzahl ist, ist das Verfahren ganz einfach.

Vertrauen ist gut

In Abbildung 5 stehen am Rand der Quadrate jeweils in Schwarz die x- und y-Werte von 0 bis 4 in durchgewürfelter Reihenfolge, da diese keine Rolle spielt. Jedes Element der Matrix berechnet sich nach der einfachen Formel »(a*y + x) % 5 + 1« , wobei »a« beim ersten Quadrat auf 1 gesetzt wird, beim zweiten auf 2 und so weiter.

So ergibt sich zum Beispiel für das Element, das in der zweiten Spalte der dritten Reihe des vierten Quadrats liegt, folgender Wert: Da der y-Wert der dritten Reihe des vierten Quadrats auf »3« steht, der x-Wert der zweiten Spalte auf »2« und der Wert für »a« im vierten Quadrat »4« beträgt, ergibt sich »4 * 3 + 2 = 14« . Auf Modulo 5 reduziert bleiben 4 übrig, dann 1 dazugezählt, weil die Werte von 1 bis 5 laufen und nicht von 0 bis 4, als Ergebnis bleibt 5.

Listing 1 implementiert diese Formel in den beiden »for« -Schleifen ab Zeile 9 und macht sich dann im abschließenden Teil ab Zeile 22 daran, die Kombinationen auszugeben. Das Ganze läuft rasend schnell, da es sich um simple Arithmetik und kein Probierverfahren handelt.

Kontrolle ist besser

Aber natürlich gilt “Vertrauen ist gut, Kontrolle ist besser”, also liest Listing 2 die formatierte Ausgabe von Listing 1 und prüft mit Hilfe der Hashreferenz »$met« , ob die Teilnehmer tatsächlich jedes Mal mit anderen Leuten zusammensitzen. Kehrt das Skript ohne Ausgabe zurück, stimmt alles.

01 #!/usr/bin/perl -w
02 use strict;
03
04 my $met = {};
05
06 while( <> ) {
07     # day9 group1: i9 b9 b18 g9 g18 g27
08   if( my( $day, $group, $rest ) =
09     /day(\d+)\s
10      group(\d+):\s
11      (.*)
12     /x ) {
13     my @participants = split / /, $rest;
14
15     for my $i ( 0 .. $#participants ) {
16       for my $j (
17           $i+1 .. $#participants ) {
18         my $a = $participants[ $i ];
19         my $b = $participants[ $j ];
20
21         if( exists $met->{ $a }->{ $b } or
22           exists $met->{ $b }->{ $a } ) {
23           die "$day:$group: Whoops, $a ",
24               "and $b have met already ",
25               "on $met->{ $a }->{ $b }";
26         }
27
28         $met->{ $a }->{ $b } =
29         $met->{ $b }->{ $a } =
30           "$day:$group";
31       }
32     }
33   }
34 }

Ist die Felddimension jedoch keine Primzahl, wie bei den eingangs geforderten Quadraten der Größe 9×9, wird die Sache schon schwieriger. Für eine Anordnung der Dimension 6×6 gibt es sogar überhaupt keine Lösung, was Euler herausfand, als er 36 Offiziere aus sechs verschiedenen Regimentern mit jeweils sechs unterschiedlichen Diensträngen so für eine Parade aufmarschieren lassen wollte, dass sich weder Dienstränge noch Regimentszugehörigkeit innerhalb einer Reihe oder Rotte wiederholen [6].

Er schloss richtig, dass das theoretisch unmöglich sei, ließ sich aber auch gleich leichtsinnigerweise und voreilig zu der Vermutung hinreißen, dass es für Dimensionen 4n+2 generell keine Lösung gäbe. Riesenfehler! Mehr als 150 Jahre später, genau 1959, stellte sich heraus, dass es auch Lösungen für 10×10 und sogar 14×14 gibt. Dass das Problem der 36 Offiziere aber garantiert unlösbar ist, das ist mittlerweile ebenfalls wasserdicht bewiesen.

9-elementiger Galoiskörper

Ist die Dimension allerdings eine Primzahlpotenz (also zum Beispiel 9, der zweiten Potenz der Primzahl 3), dann bedient sich der Fachmann bei der Konstruktion der Quadrate eines so genannten Galoiskörpers F. Der ist eine Ansammlung von n Zahlen, für die die Rechenoperationen Addition (+) und Multiplikation (*) definiert sind, die wiederum ein Ergebnis in F liefern.

Bezogen auf das Problem mit den neun Lehrern, 18 Schülern und 27 Schülerinnen schlug der kanadische Mathematiker vor, diese in insgesamt sechs Gruppen mit je neun Teilnehmern einzuteilen: die Lehrer, die A- und die B-Schüler und die C-, D- und E-Schülerinnen. Diesen rückte er dann mit dem neun-elementigen, aus komplexen Zahlen (i2 = -1) bestehenden Körper

F = {0, 1, 2, i, 1+i, 2+i, 2i, 1+2i, 2+2i}

zu Leibe, der Addition und Multiplikation mit Hilfe von Modulo 3 reduziert und damit sicherstellt, dass eine Verknüpfung zweier Elemente aus F wieder ein Element aus F zum Ergebnis hat. So zum Beispiel

(1 + 2i) * (1 + i) **= -1 + 3i

was sich Modulo 3 zu »2 + 0i« reduzieren lässt, also zu »2« , was wiederum in F liegt. Wer mit »+« und »*« die an den Körper angepassten Operationen Modulo 3 bezeichnet, kann sich die Nummern der Teilnehmer in den Gruppen mit den Formeln in Abbildung 8 erzeugen. Die Variable »d« bezeichnet in dieser Darstellung jeweils die Nummer des Tages (1 bis 9) und »g« die Nummer der Gruppe (ebenfalls 1 bis 9). Heraus kommt jeweils die Nummer des Teilnehmers aus den sechs verschiedenen Teilklassen, der zu dem angegebenen Tag in der jeweiligen Gruppe sitzt.

Abbildung 8: Diese Formeln bestimmen, welcher Lehrer und welche Schüler und Schülerinnen am Tag »d« in Gruppe »g« sitzen.

Listing 3 implementiert diese Formeln lediglich und spuckt das Ergebnis für neun Tage aus, wie eingangs in Abbildung 3 gezeigt. Die komplexen Zahlen im Galoiskörper definiert das Array »@field« in den Zeilen 5 bis 9, und die ab Zeile 17 stehende Funktion »mapback()« sucht zu einer Zahl (zum Beispiel dem Ergebnis einer Multiplikation) wieder die Nummer des Elements in F heraus.

01 #!/usr/local/bin/perl -w
02 use strict;
03 use warnings;
04
05 my @field = (
06     [ 0, 0 ], [ 1, 0 ], [ 2, 0 ],
07     [ 0, 1 ], [ 1, 1 ], [ 2, 1 ],
08     [ 0, 2 ], [ 1, 2 ], [ 2, 2 ],
09 );
10
11   # map re/im => field element number
12 my $lookup = { };
13 for my $idx (1 .. scalar @field ) {
14   my( $re, $im ) = @{ $field[ $idx - 1 ] };
15   $lookup->{ $re }->{ $im } = $idx;
16 }
17 sub mapback {
18   my( $re, $im ) = @_;
19   return $lookup->{ $re }->{ $im };
20 }
21
22 foreach my $day (1..9) {
23   foreach my $group (1..9) {
24     print "day$day group$group: ";
25     print "i", fadd( $day,
26          fmult( 2, $group ) ),      " ";
27     print "b", fadd( $day,
28          fmult( 3, $group ) ),      " ";
29     print "b", fadd( $day,
30          fmult( 4, $group ) ) +  9, " ";
31     print "g", fadd( $day,
32          fmult( 5, $group ) ),      " ";
33     print "g", fadd( $day,
34          fmult( 6, $group ) ) +  9, " ";
35     print "g", fadd( $day,
36          fmult( 7, $group ) ) + 18, "\n";
37   }
38   print "\n";
39 }
40
41 sub fadd {
42   my( $f1, $f2 ) = @_;
43
44   my( $r1, $i1 ) = @{ $field[ $f1 - 1 ] };
45   my( $r2, $i2 ) = @{ $field[ $f2 - 1 ] };
46
47   return mapback(
48     ( $r1 + $r2 ) % 3,
49     ( $i1 + $i2 ) % 3 );
50 }
51
52 sub fmult {
53   my( $f1, $f2 ) = @_;
54
55   my( $r1, $i1 ) = @{ $field[ $f1 - 1 ] };
56   my( $r2, $i2 ) = @{ $field[ $f2 - 1 ] };
57
58   return mapback(
59     ( $r1 * $r2 - $i1 * $i2 ) % 3,
60     ( $r1 * $i2 + $r2 * $i1 ) % 3 );
61 }

Die Funktionen »fadd()« und »fmult()« (Zeilen 41 und 52) implementieren die per Modulo 3 reduzierte Addition beziehungsweise Multiplikation zweier Feldelemente aus F. Sie nehmen die Feldnummern der Elemente entgegen, suchen die zugehörigen komplexen Zahlen aus F heraus, wenden die jeweilige Operation auf den Real- und den Imaginärteil der Operanden an und führen das Ergebnis wieder mit »mapback« auf die Nummer eines Elements aus F zurück.

Der Galoiskörper ist nach dem französischen Mathematiker Èariste Galois benannt, der den wesentlichen Durchbruch schon im zarten Alter von 18 Jahren errang. Was er noch alles hätte erreichen können, muss Spekulation bleiben, denn mit 20 ließ er sich zu einem Pistolenduell hinreißen, bei dem er den Kürzeren zog und am Tag darauf seiner Schussverletzung erlag.

So ging’s zu im 19. Jahrhundert: Heute Meilensteine der diskreten Mathematik setzen und am nächsten Morgen mit der Steinschlosspistole in der Hand raustreten, um Beleidiger zu erschießen. Damals wurde noch was geboten!

Der Autor

Michael Schilli arbeitet als Software-Engineer in der San Francisco Bay Area in Kalifornien. In seiner seit 1997 laufenden Kolumne forscht er jeden Monat nach praktischen Anwendungen der Skriptsprache Perl. Unter mailto:mschilli@perlmeister.com beantwortet er gerne Fragen.