| |
Dieser Shift tritt nur nach einer bestimmten Spielsituation auf: Befindet sich auf einer
gemischten Diagonalen die Null ganz oben und die Eins auf der darunter liegenden
Diagonalen
ganz
unten,
stehen
diese
nach
Durchführung
eines
Spielschritts
nebeneinander. Hierbei steht die Null links neben der Eins. Dies hat einen Shift II zur
Folge.
Durch einen Shift II wird die betroffene Eins auf eine niedrigere Diagonale zurückgeholt.
Rück-Richtung des Beweises von Lemma 3.1:
Sei É die zyklische Verteilung mit É = (1, 2,
, k) = (k, (k-1),
, 2, 1) und die Anzahl der
Kartenstapel s = k. Wird nun ein Schritt des Spiels durchgeführt, so erhält man die
Verteilung É' = (s, (k-1), (k-2),
, 1, 0) = (s, (k-1), (k-2),
, 1). Da die Anzahl der
Kartenstapel s = k, ist É' = (k, (k-1),
, 2, 1) = É.
Damit ist É ein einfach-zyklischer Zustand.
Hin-Richtung des Beweises von Lemma 3.1:
Ist die Anzahl der Karten n eine Dreieckszahl und der zyklische Zustand (É = (1, 2,
, (k-
1), k) erreicht, so gibt es in der Matrix keine gemischte Diagonale. Alle Einsen befinden
sich im oberen Dreieck der Matrix.
Ist der zyklische Zustand noch nicht erreicht, so gibt es mindestens eine gemischte
Diagonale und es befindet sich mindestens eine Eins unterhalb der ersten gemischten
Diagonalen. Dann entsteht durch das wiederholte Durchführen von Spielschritten
irgendwann die Situation, dass eine Null der gemischten Diagonalen ganz oben steht.
Nun muss die einzelne Eins auf der darunter liegenden Diagonalen auf die unterste
Position der entsprechenden Diagonalen gebracht werden, damit ein Shift II auftritt und
die Eins zurück auf eine Diagonale mit niedrigerem Index geholt wird. Dies ist leicht
möglich, da sich die Längen der Diagonalen genau um Eins unterscheiden. Führen wir
'Anzahl der Länge der gemischten Diagonalen' - Shift I Operationen durch, befindet sich
die Null der gemischten Diagonalen auf der ursprünglichen Position. Die Eins der darunter
liegenden Diagonalen ist hingegen um eine Position verschoben worden, da sich diese
beiden Diagonalen um einen Eintrag in der Länge unterscheiden. Dies führen wie solange
durch, bis sich die Eins ganz unten auf der Diagonalen befindet.
Nun wird ein weiteres Mal der Shift I durchgeführt. Im nächsten Schritt holen wir die Eins
mittels Shift II auf eine Diagonale mit niedrigerem Index zurück.
Diese Prozedur wird so oft durchgeführt, bis alle Einsen unterhalb der ersten gemischten
Diagonalen zurückgeholt worden sind. In diesem Fall existiert keine gemischte Diagonale
mehr. Damit haben wir den zyklischen Zustand erreicht.
Weiterhin ist der zyklische Zustand eindeutig, da durch wiederholtes Anwenden des Shift I
die Einsen zurück geholt werden müssen, da sich die Länge der benachbarten Diagonalen
jeweils um eins unterscheidet. Dadurch werden alle Einsen in das obere linke Dreieck der
Matrix geholt.
Damit ist die Richtigkeit des Lemmas gezeigt.
|  |
|
| |
|
|