Griechisch-lateinisches Quadrat

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Griechisch-lateinisches Quadrat der Größe 5

Ein griechisch-lateinisches Quadrat (GLQ) oder Eulersches Quadrat der Größe n ist ein quadratisches Schema mit n Zeilen und n Spalten, bei dem in jedem der n \cdot n Felder ein Zeichen aus einer Menge G und eines aus einer anderen Menge L eingetragen ist.

Dabei muss in jeder Zeile und auch in jeder Spalte jedes Element aus G und ebenso jedes Element aus L genau einmal vorkommen, und jedes Tupel (g,l) \in G \times L muss im gesamten Quadrat genau einmal vorkommen.

Ein GLQ ist eine Verallgemeinerung des sogenannten Lateinischen Quadrates. Während es beim lateinischen Quadrat um eine Menge geht, geht es beim GLQ um zwei Mengen. Das Konzept wurde von Leonhard Euler eingeführt, der für die Menge G Buchstaben des griechischen und für L Buchstaben des lateinischen Alphabets verwendete. Daraus entstand der Name.

In den 1780er Jahren fand Euler Methoden zur Konstruktion von GLQ mit ungerader oder durch vier teilbarer Größe n. Es gelang ihm jedoch nicht, auch für n \equiv 2 \; (\bmod \, 4) Lösungen zu finden. Der Fall n=6 ist als Problem der 36 Offiziere bekannt geworden: sechs Regimenter stellen je sechs Offiziere mit sechs verschiedenen Dienstgraden, und sie sollen sich so in einem 6x6-Quadrat aufstellen, dass in jeder Zeile und in jeder Spalte jedes Regiment und jeder Dienstgrad einmal vorkommt.

Euler vermutete entsprechend, dass es genau dann ein GLQ gibt, wenn n \not\equiv 2 \; (\bmod \, 4). Dass es für n=6 keine Lösung gibt, wurde 1901 von Gaston Tarry gezeigt, aber im Jahr 1959 konstruierten R. C. Bose und S. S. Shrikhande Gegenbeispiele mit n=22. Parker, Bose und Shrikhande bewiesen, dass für alle Größen außer n=2 und n=6 ein GLQ existiert.

Literatur[Bearbeiten]

  • Victor Bryant: Aspects of Combinatorics: A Wide-ranging Introduction. Cambridge University Press 1993, ISBN 0521429978

Weblinks[Bearbeiten]