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:
-
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),
-
das Feld Fo, das in der obersten Reihe und in der Spalte von
F liegt,
-
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.
-
Die ersten v-2 Ebenen werden mit je (v-1)2 Karten belegt, wobei
alle Felder bis auf die Spalte ganz rechts sowie die Reihe ganz unten belegt
werden.
-
In der (v-1)-ten Ebene wird die gesamte oberste Reihe und die gesamte linke
Spalte belegt, das Schnittfeld links oben wird jedoch freigelassen.
-
In der v-ten Ebene werden (v-2)2 Karten belegt, wobei die oberste
und unterste Reihe sowie die Spalten ganz links und ganz rechts freigelassen
werden.
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.