8 Überlegungen für zwei und drei Eigenschaften

8.1 Maximalzahl für zwei Eigenschaften

Bei zwei Eigenschaften und v Varianten lassen sich höchstens (v-1)2 Karten so auslegen, daß kein Set entsteht.
Beweis: In der geometrischen Darstellung liegt ein Quadrat der Seitenlänge v vor. Belegt werden alle Felder mit Ausnahme der untersten Reihe und der Spalte ganz rechts (siehe Abbildung 10). Da also keine Karten ausgewählt werden, die in mindestens einer der beiden Eigenschaften die letzte Variante aufweisen, ist sichergestellt, daß kein Set entsteht (siehe 2.6). Die belegten Felder bilden ein Quadrat, das (v-1)² Karten ohne Set beinhaltet.
 
X X X X -
X X X X -
X X X X -
X X X X -
- - - - -
Abbildung 10: Beispiel für eine Maximallösung bei fünf Varianten

Der Beweis, daß dies die Maximalzahl ist, wird mit vollständiger Induktion geführt.
1. Induktionsanfang: Die Maximalzahl für v=1 ist 0, für v=2 ist sie 1 (siehe 6.1). Dies erfüllt die Bedingung.
2. Induktionsschluß (gilt nur, wenn man auf Werte für v>=3 schließt): Der Satz sei für v-1 Varianten bewiesen. Bei v Varianten müssen nun sowohl in einer Reihe als auch in einer Spalte je v-1 Karten liegen. Lägen nämlich in jeder Reihe höchstens v-2 Karten, so sind insgesamt höchstens (v-2)v=v2-2v, also weniger als (v-1)2=v2-2v+1 Karten belegt, analog lassen sich die Spalten betrachten.
Die Varianten der beiden Eigenschaften können aufgrund ihrer beliebigen Bezeichnung (vgl. 2.2) so umnumeriert werden, daß die Reihe mit v-1 Karten ganz oben und die Spalte mit v-1 Karten ganz links liegen. Das verbleibende Quadrat (Seitenlänge v-1) heiße A. Die Reihe und die Spalte schneiden sich demnach im Feld links oben (00). Dieses Feld ist entweder frei oder belegt.
 
- X X X X X X X X -
X
 A X A
X
 X
X
 X
X
 -
Abbildung 11: Mögliche Kartenbelegungen der Ebene am Beispiel v=5; linke Ebene siehe a), rechte Ebene siehe b)

a)  Ist dieses Feld nicht belegt, so müssen auf jeder Diagonalen von A zwei Felder frei sein, damit kein Set vorhanden sein kann.
Beweis: Ist nämlich auf einer Diagonalen nur ein Feld F nicht belegt (sollte gar kein Feld frei sein, wird ein beliebiges belegtes Feld im folgenden nicht betrachtet), so existiert ein Set. Dieses läßt sich finden, indem man folgende Karten auswählt:

  1. alle belegten Felder der Diagonalen von A (insgesamt v-2 Karten, da auf jeder Diagonale von A v-1 Karten liegen, vgl. 2.7, A ist ein Quadrat mit der Seitenlänge v-1),
  2. das Feld Fo, das in der obersten Reihe und in der Spalte von F liegt,
  3. das Feld Fl, das in der Spalte ganz links und in der Reihe von F liegt.
Die Felder Fo und Fl sind beide belegt, da das eine in der obersten Reihe und das andere in der Reihe ganz links liegt, und beide nicht auf dem frei gelassenen Schnittfeld liegen.
Die gewählten Felder bilden nun eine Diagonale im Gesamtquadrat: Einerseits sind insgesamt v Karten ausgewählt, andererseits ist in jeder Reihe und in jeder Spalte ein Feld belegt: Eine Diagonale belegt jede Spalte und jede Zeile genau einmal; die auf der Diagonalen von A belegten Felder belegen dementsprechend alle Reihen bis auf die Reihe vom einzigen nicht belegten Feld F und die oberste Reihe des Gesamtquadrates - nur diese gehört nicht zu A - sowie alle Spalten bis auf die Spalte von F und die Spalte ganz links - auch hier gehört nur diese nicht zu A. Fo belegt nun die oberste Reihe und die Spalte von F; Fl belegt die Spalte ganz links und die Reihe von F. In jeder Reihe und jeder Spalte ist also genau ein Feld belegt; die Karten bilden eine Diagonale und somit ein Set.
Zu jeder Diagonalen von A existieren v-2 parallele Diagonalen in A (analog dazu, daß zu jeder Spalte in A v-2 parallele Spalten existieren), die sich paarweise nicht schneiden. In A sind also 2(v-1) Felder frei. Hinzu kommt das freie Schnittfeld links oben, im Gesamtquadrat sind demnach mindestens 2(v-1)+1=2v-1 Felder nicht belegt. Insgesamt gibt es v2 Felder; dementsprechend können höchstens v2-(2v-1)=v2-2v+1=(v-1)2 Felder belegt sein, wenn das Feld links oben frei ist.
b) Ist das Feld links oben belegt, kann man die Spalten bzw. die Reihen wie bereits weiter oben begründet so vertauschen, daß das freie Feld der obersten Reihe ganz rechts und das der linken Spalte ganz unten liegt. In A darf in einerseits keine Diagonale vollständig belegt sein, weil sie sonst mit dem Feld links oben im Gesamtquadrat ein Set bilden würde, andererseits würde eine vollständig belegte Reihe in A mit dem Feld ganz links in dieser Reihe und eine vollständig belegte Spalte in A mit dem Feld ganz oben in dieser Spalte ein Set bilden. Also darf man nur die Reihe ganz unten sowie die Spalte ganz rechts in A vollständig belegen. Liegt einer dieser beiden Fälle vor, so ist dies eine Drehung um 90° vom Fall a) der Fallunterscheidung: diesmal schneidet sich die mit v-1 Karten belegte Reihe mit der mit v-1 Karten belegten Spalte in dem leeren Feld oben rechts bzw. unten links.
 Ansonsten darf in A keine Reihe, keine Spalte, keine Diagonale vollständig belegt sein, also kein Set vorliegen. Für die Seitenlänge v-1 ist die Maximalzahl (v-2)2 bereits bewiesen, in A sind also höchstens (v-2)2=v2-4v+4 Felder belegt. Außerhalb von A gibt es eine Spalte mit v-1 Karten und eine Reihe mit v-1 Karten. Da diese beiden die Karte links oben gemeinsam haben, liegen außerhalb von A insgesamt 2(v-1)-1=2v-3 Karten.
 Im Gesamtquadrat liegen also höchstens (v2-4v+4)+(2v-3)=v2-2v+1=(v-1)2 Karten.
In beiden Fällen liegen höchstens (v-1)2 Karten vor, wenn man voraussetzt, daß die Formel für v-1 bereits bewiesen ist. Da die Formel für v=1 und v=2 richtig ist und man von v-1 immer auf v schließen kann, ist sie allgemeingültig.

8.2 Untergrenze für die Maximalzahl bei drei Eigenschaften

Laut 6.2 ergibt sich für v=3 und n=3 die Maximalzahl 9. Für v=4 liefert das Programm zumindest in akzeptabler Rechenzeit keinen größeren Wert als 28. Beide Zahlen erfüllen die Formel (v-1)3+1. Wir konnten ein Konstruktionsprinzip für alle v>=3 entwickeln, bei dessen Anwendung die auftretenden Kartenkonstellationen tatsächlich (v-1)3+1 Karten ohne Set enthalten. Damit haben wir eine Untergrenze für die Maximalzahl bei n=3 gefunden.
Bei der Konstruktion orientieren wir uns an der geometrischen Darstellung in der Ebene, die einzelnen Ebenen seien von links nach rechts durchnumeriert. Die drei Eigenschaften heißen n1, n2 und n3, wobei in der geometrischen Darstellung zwischen den Varianten von n1 durch unterschiedliche Spalten, den Varianten von n2 durch unterschiedliche Reihen und den Varianten von n3 durch unterschiedliche Ebenen differenziert wird.
Ebene 1 Ebene 2 Ebene 3 (=v-2) Ebene 4 (=v-1) Ebene 5 (=v)
X X X X - X X X X - X X X X - - X X X X - - - - -
X X X X - X X X X - X X X X - X - - - - - X X X -
X X X X - X X X X - X X X X - X - - - - - X X X -
X X X X - X X X X - X X X X - X - - - - - X X X -
- - - - - - - - - - - - - - - X - - - - - - - - -
Abbildung 12: Konstruktionsvorschrift für n=3 und v=5

In diesen Karten ist kein Set enthalten: Erstens existiert innerhalb einer Ebene (Karten, die in n3 gleich sind) kein Set; innerhalb der ersten v-2 Ebenen nicht (siehe 8.1) und in der v-ten Ebene auch nicht, da die gleichen Karten wie in Ebene 1 belegt wurden. In der (v-1)-ten Ebene liegen in keiner Reihe und keiner Spalte v Karten, das heißt die Karten eines potentiellen Sets müßten auf einer Diagonalen der Ebene liegen. Da aber für v>=3 sowohl die einzige Karte der letzten als auch die einzige Karte der vorletzten Spalte in der obersten Reihe liegen und auf einer Diagonalen eine Karte jeder Spalte liegen muß, müßten diese beiden oberen Karten auf einer Diagonalen liegen. Das ist aber nicht der Fall, da sie beide in der gleichen Reihe liegen.
Zweitens existiert aber auch ebenenübergreifend kein Set: Einerseits ist kein Feld in allen Ebenen belegt, denn sämtliche Felder, die in der (v-1)-ten Ebene belegt sind, sind in der v-ten Ebene nicht belegt. Also kann kein Set aus Karten vorhanden sein, die sich nur in n3 unterscheiden. Andererseits kann auch kein Set aus Karten vorhanden sein, die sich nur in n3 und entweder n1 oder n2 unterscheiden: Wenn sie sich nämlich nur in bezug auf Ebenen und Spalten unterscheiden, müßten sie in der obersten Reihe liegen, da nur dort ein Feld ganz rechts belegt ist, diese Reihe ist jedoch in der v-ten Ebene überhaupt nicht belegt. Für den Fall, daß sie sich nur in bezug auf Ebenen und Reihen unterscheiden, läßt sich analog argumentieren, da alle Ebenen zur Diagonalen von links oben nach rechts unten symmetrisch sind.
Nun bleibt nur noch der Fall, daß sich die Karten in n1, n2, und n3 unterscheiden. In diesem Fall müßte sowohl eine Karte aus der Spalte ganz rechts als auch eine Karte aus der Reihe ganz unten vorhanden sein. Jede dieser Bedingungen wird jedoch nur von jeweils einer Karte erfüllt, und beide liegen in der (v-1)-ten Ebene. Diese Karten unterscheiden sich jedoch nicht in n3; es existiert also auch kein Set aus Karten, die sich in allen drei Eigenschaften unterscheiden und demnach überhaupt kein Set - alle möglichen Sets wurden ausgeschlossen.
Insgesamt wurden in den ersten v-2 Ebenen je (v-1)2 Karten und in der (v-1)-ten Ebene eine Reihe und eine Spaltemit je v-1 Karten ausgewählt. In der v-ten Ebene wurden (v-2)2 Karten belegt.
Alles in allem berechnet sich die Kartenzahl also wie folgt:
(v-2)(v-1)2+2(v-1)+(v-2)2
=(v-2)(v2-2v+1)+2v-2+v2-4v+4
=v3-2v2+v-2v2+4v-2+2v-2+v2-4v+4
=v3-3v2+3v
=(v-1)3+1

Damit ist gezeigt:
Man kann bei n=3 und jedem v>=3 eine Menge von (v-1)3+1 Karten auswählen, ohne daß ein Set entsteht.
 
vorheriges Kapitelnächstes Kapitel

Anregungen, Fragen, Kritik an: Wolf Behrenhoff, Felix Krahmer und Andreas Sorge; Impressum, Datenschutz