Embed Size (px)
Citation preview
Math Semesterber (2013) 60:51–66DOI 10.1007/s00591-012-0107-4
M AT H E M AT I K I N F O R S C H U N G U N D A N W E N D U N G
Der Goldene Schnitt in Türmen aus Spielsteinen
Roland Schröder
Eingegangen: 10. August 2011 / Angenommen: 10. Mai 2012 / Online publiziert: 24. Mai 2012© Springer-Verlag 2012
Zusammenfassung Eine Folge natürlicher Zahlen wird in eine neue Folge natürli-cher Zahlen gleicher Summe transformiert, indem das erste Folgenglied a1 gestrichenwird und die angrenzenden a1 Folgenglieder jeweils um 1 erhöht werden. Wiederhol-te Durchführung dieser Transformation erzeugt eine Folge von Folgen. Wählt man alsStartfolge eine endliche Folge (Konstellation), so führen wiederholte Transformatio-nen in einen Zyklus von Konstellationen. Eigenschaften solcher Zyklen hängen vonder Summe der Folgenglieder ab, während Eigenschaften der Konstellationenfolgenim vorzyklischen Bereich in besonderer Weise von der Wahl der Startkonstellationabhängen. Die vorliegende Arbeit behandelt Eigenschaften von Zyklen und stellt füreine bestimmte Startkonstellation Gesetzmäßigkeiten im vorzyklischen Teil der Folgefest, deren Beziehung zum Goldenen Schnitt bewiesen wird.
1 Einleitung
Im Folgenden werden zwei Spiele vorgestellt, die eine Reihe von Gemeinsamkei-ten haben. Beide beginnen mit aufeinandergestapelten Spielsteinen und beide führenauf eine Gesetzmäßigkeit die in Beziehung zum Goldenen Schnitt steht. Im übrigensind die Spiele aber grundverschieden. Eines der beiden Spiele hat unter dem Namen„Wythoffs Game“ einen gewissen Bekanntheitsgrad erlangt. Es ist ein Strategiespielfür zwei Spieler, welches von Willem Abraham Wythoff im Jahre 1907 vollständiganalysiert wurde. Einzelheiten zum Spiel werden zu Beginn des Abschn. 4 genannt.
Das andere ist ein Solitärspiel, welches Hasemann u. a. [1] unter dem Namen„Türme bauen“ Grundschülern als Denkaufgabe anbieten. Es ist zu vermuten, dassHasemann und seine Mitautoren die Idee zu ihrem Spiel dem Spiel „Mancala“ ent-lehnt haben, ursprünglich einem Brettspiel, dessen älteste Spielbretter aus dem 6. bis
R. Schröder (�)Dehningstr. 26, 29223 Celle, Deutschlande-mail: [email protected]
52 R. Schröder
7. Jahrhundert n. Chr. im Grenzgebiet zwischen Äthiopien und Eritrea gefunden wur-den. Die Spielbretter enthalten Mulden, die mit Spielsteinen gefüllt werden können.Ein Spielzug besteht aus dem Leeren einer Mulde und der anschließenden Verteilungder entnommenen Steine einzeln auf die in Spielrichtung angrenzenden Mulden. DasSpiel hat vor allem in Asien und Afrika eine starke Verbreitung erfahren und existiertinzwischen in nahezu 1000 Varianten mit vielen unterschiedlichen Bezeichnungenweltweit. Hasemanns Variante verwendet stapelbare Spielsteine (Chips oder Dame-/Mühle-Steine), wodurch das Muldenbrett entbehrlich wird. Einzelheiten zum Spiel„Türme bauen“ in seiner allgemeinen Form und zu den Eigenschaften seiner Zyklenwerden in den Abschn. 2 und 3 genannt.
Der zweite Teil von Abschn. 4 sowie die folgenden Kapitel behandeln den vorzy-klischen Bereich beim Spiel „Türme bauen“ unter Vorgabe einer ganz spezifischenStartkonstellation. Hier lässt sich zunächst eine Beziehung zwischen der Anzahl k derSpielzüge und der Anzahl der im k-ten Zug zur Verteilung anstehenden Spielsteinebeweisen (Abschn. 5, 6 und 7) und auf dieser Basis gelingt der Beweis für die Anzahlder Spielzüge bis zur Spiegelung der Startkonstellation (Abschn. 8). Im Zentrum bei-der Beweise steht eine Zahlenfolge, die auch schon in Wythoffs Spiel von zentralerBedeutung war.
2 Das Spiel „Türme bauen“
Wie gesagt bieten Hasemann und Mitautoren unter dem Namen „Türme bauen“Grundschülern eine Denkaufgabe an, die hier im Hinblick auf das Folgende insprachlich veränderter Form wiedergegeben wird:
Zu Beginn des Spiels soll eine Anzahl von k Spielsteinen beliebig auf j neben-einander angeordnete Türme aufgeteilt werden (j ≤ k). Ein Spielzug besteht darin,dass der am weitesten links stehende Turm aufgenommen und Stein für Stein sowieTurm für Turm rechts davon verteilt wird. Wenn rechts keine Türme mehr stehen,sind Türme zu je einem Stein anzufügen. Ziel dieses Solitärspiels ist die Entde-ckung mathematisch beschreibbarer Eigenschaften der Entwicklung der Folge vonKonstellationen.
Beispiel für k = 14 und j = 4 (die Höhe der Türme sei durch Zahlen beschrieben):
5, 2, 3, 43, 4, 5, 1, 1
5, 6, 2, 17, 3, 2, 1, 1
4, 3, 2, 2, 1, 1, 14, 3, 3, 2, 1, 1
4, 4, 3, 2, 15, 4, 3, 2
5, 4, 3, 1, 15, 4, 2, 2, 1
5, 3, 3, 2, 14, 4, 3, 2, 1
5, 4, 3, 2
Der Goldene Schnitt in Türmen aus Spielsteinen 53
Eine Besonderheit des dargestellten Beispiels ist die zyklische Wiederholung derletzten fünf Konstellationen. Dies zieht Fragen nach sich, wie „Welche Vorgabe legtdie Anzahl der Konstellationen in einem Zyklus fest?“ oder „Gibt es zu dieser Vor-gabe noch weitere Zyklen, die aus anderen Konstellationen bestehen?“ Im Folgendenwerden derartige Fragestellungen untersucht. Antworten auf einen Teilaspekt dieserFragen können nach einigen Experimenten tatsächlich bereits Grundschüler entde-cken. In besonderen Fällen mündet das Spiel in einen Zyklus ein, der aus einer einzi-gen Konstellation besteht. Die Anzahlen der in diesen Fällen eingesetzten Spielsteinesind formal leicht zu beschreiben. Beweise dieser und weiterer Gesetzmäßigkeitenim Spiel „Türme bauen“ sind allerdings eher für Oberstufenschüler oder Studienan-fänger nachvollziehbar. Derartige Beweise sollen hier geführt werden und setzen imersten Schritt eine Analyse des Spiels und die Definition einiger Begriffe voraus.
Eine Aufteilung a1, a2, a3, . . . , aj einer Gesamtzahl von k Steinen (a1 +a2 +a3 +· · · + aj = k) auf j Türme soll „Konstellation“ heißen. Dabei heißt die zu Beginn desSpiels frei gewählte Aufteilung „Startkonstellation“. Eine Konstellation, die sich imLaufe des Spiels wiederholt, heißt „Zielkonstellation“. Nach Erreichen der Zielkon-stellation kann das Spiel abgebrochen werden, weil der weitere Verlauf nun zyklischwird. Ursache dafür ist die Eindeutigkeit des Übergangs von einer Konstellation in dieNachfolgerkonstellation, die Eindeutigkeit der „Transformation“ sowie die Tatsache,dass es für eine endliche Anzahl k von Spielsteinen nur endlich viele Konstellationengeben kann. Die Transformation τ ist eine injektive Abbildung der Konstellationenin sich.
Die Folge der Konstellationen von einer Zielkonstellation bis zu ihrer Wiederho-lung soll „Zyklus“ heißen. Für eine Konstellation c1, c2, c3, . . . , cj eines bestimm-ten Zyklus gibt es einen Exponenten m mit τm(c1, c2, c3, . . . , cj ) = c1, c2, c3, . . . , cj
und die Zahl m soll „Zykluslänge“ heißen. Zyklen und ihre Längen haben bestimmteEigenschaften, die in diesem Kapitel dargestellt werden.
Eigenschaft 1 Rechts von der Startkonstellation a1, a2, a3, . . . , aj , also für i ≥ j giltfür zwei benachbarte Türme #i und #i + 1 zu jedem Zeitpunkt des Spiels: ai ≥ ai+1.
Beweis zu Eigenschaft 1 Bei Verteilung eines Turms aus einer Startkonstellation mitj Türmen erhöht sich ein Turm #(i + 1) mit (i ≥ j) nur dann, wenn auch Turm #i
links davon erhöht wird.Das bedeutet, dass jede Startkonstellation mit j Türmen spätestens nach j Trans-
formationen in eine monoton fallende Konstellation übergeht, das heißt, benach-barte Türme sind gleich hoch oder der rechte ist kleiner. Eine monoton fallendeKonstellation bleibt im weiteren Spielverlauf monoton fallend. �
Eigenschaft 2 Insbesondere bestehen Zyklen ausschließlich aus monoton fallendenKonstellationen.
Beweis zu Eigenschaft 2 Angenommen, ein Zyklus enthielte eine nicht monoton fal-lende Konstellation, die wir als Startkonstellation auffassen. Dann muss diese gemäßEigenschaft 1 nach einer genügend großen Anzahl von Transformationen in eine fal-lende Konstellation übergehen, die im gleichen Zyklus liegt. Es gibt also innerhalb ei-
54 R. Schröder
nes Zyklus eine monoton fallende Konstellation. Da jede Konstellation in einem Zy-klus Nachfolger einer Konstellation aus demselben Zyklus ist, sind mit einer monotonfallenden Konstellation alle Konstellationen des gleichen Zyklus monoton fallend. �
Eigenschaft 3 Auf der Menge z der Konstellationen eines bestimmten Zyklus kanneine Umkehrfunktion τ−1
z definiert werden durch folgende Vorschrift: τ−1z (a1, a2, a3,
. . . , aj ) = j, a1 − 1, a2 − 1, a3 − 1, . . . , aj − 1.
Alle j Türme werden jeweils um 1 vermindert und die j eingesammelten Steinewerden links an die Konstellation als Turm der Höhe j angebaut.
Begründung zu Eigenschaft 3 τ−1z ist eine Funktion, da in einem Zyklus mit der
eindeutigen Festlegung von Nachfolgern auch jeder Vorgänger eindeutig festgelegtist.
Aus Eigenschaft 2 folgt, dass in jeder Konstellation a1, a2, a3, . . . , aj eines Zyklusganz links der höchste Turm der Höhe a1 steht. �
Eigenschaft 4 Für eine Konstellation a1, a2, a3, . . . , aj eines Zyklus gilt: a1 −1 ≤ j .
Beweis zu Eigenschaft 4 Die Umkehrfunktion τ−1z stellt der Konstellation a1, a2, a3,
. . . , aj einen Turm der Höhe j voran. Dieser muss mindestens die Höhe a1 −1 haben,damit die so erzeugte Konstellation monoton fallend bleibt. �
Eigenschaft 5 Innerhalb einer Konstellation eines Zyklus können nicht drei aufein-anderfolgende Türme die gleiche Anzahl von Steinen haben.
Beweis zu Eigenschaft 5 Angenommen, drei Türme einer Konstellation habendie gleiche Anzahl von Steinen. Dann führt die wiederholte Anwendung derTransformation τ−1
z schließlich zu einer Konstellation mit j Türmen der Art:b1, b2, . . . , bj−3,1,1,1. �
Dann ist: τ−1z (b1, b2, . . . , bj−3,1,1,1) = j, b1 − 1, b2 − 1, . . . , bj−3 − 1. (Die
transformierte Konstellation hat j − 2 Türme.)Und dann: τ−1
z (j, b1 − 1, b2 − 1, . . . , bj−3 − 1) = j − 2, j − 1, b1 − 2, b2 − 2,
. . . , bj−3 −2. Die letzte Konstellation ist in den ersten beiden Gliedern nicht monotonfallend. Daher ist die Annahme falsch und Eigenschaft 5 gegeben.
Eigenschaft 6 Für eine Konstellation a1, a2, a3, . . . , aj eines Zyklus gilt: j − 1 ≤a1 ≤ j + 1.
Beweis zu Eigenschaft 6 Nach Eigenschaft 4 reicht die Verteilung von a1 maximalum 1 über die j Türme der aktuellen Konstellation hinaus. Wir unterscheiden dreiFälle
(1) a1 > j , dann gilt nach Eigenschaft 4: a1 = j + 1,(2) a1 = j ,(3) a1 < j wird im Folgenden untersucht:
Der Goldene Schnitt in Türmen aus Spielsteinen 55
Die Annahme a1 sei um 2 kleiner als j führt zu einer Startkonstellation j − 2,
a2, a3, . . . , aj . Dann gilt: τ(j − 2, a2, a3, . . . , aj ) = a2 + 1, a3 + 1, . . . , aj . Umge-kehrt gilt τ−1
z (a2 + 1, a3 + 1, . . . , aj ) = j − 1, a2, a3, . . . , aj − 1. Das steht im Wi-derspruch zu der Tatsache, dass die Verknüpfung von τz und τ−1
z die Identität ergebenmüsste. Ein entsprechender Beweis gelingt erst recht für a1 = j −x mit x > 2. Damitgilt: (3) a1 < j ⇒ a1 = j − 1. �
Innerhalb eines Zyklus liegt a1 zwischen j −1 und j +1 sowie j zwischen a1 −1und a1 + 1.
Eigenschaft 7 Zwei benachbarte Türme innerhalb einer Konstellation aus einemZyklus können sich nicht um 3 (oder mehr als 3) Steine unterscheiden:
Beweis zu Eigenschaft 7 Angenommen, es gäbe diese zwei benachbarten Türme,die sich um 3 Steine (oder mehr) unterscheiden. Nach einer geeigneten Anzahlvon Transformationen stehen diese Türme ganz links (ihr Unterschied ist größergeworden oder gleich geblieben). Folgende Fälle werden zum Widerspruch geführt:
(1) a1 = j + 1 und a2 = j − 2,(2) a1 = j und a2 = j − 3,(3) a1 = j − 1 und a2 = j − 4.
Zu (1) τ(j + 1, j − 2, a3, . . . , aj ) = j − 1, a3 + 1, . . . , aj + 1,1,1. Diese trans-formierte Konstellation hat (i) j = j + 1 Türme und der erste Turm von linkshat (ii) a1 = j − 1 Steine. Aus (i) und (ii) folgt a1 = j − 2. Widerspruch zuEigenschaft 6.
Zu (2) τ(j, j − 3, a3, . . . , aj ) = j − 2, a3 + 1, . . . , aj + 1,1. Diese transformierteKonstellation hat (iii) j = j Türme und der erste Turm von links hat (iv) a1 = j − 2Steine. Aus (iii) und (iv) folgt a1 = j − 2. Widerspruch zu Eigenschaft 6.
Zu (3) τ(j − 1, j − 4, a3, . . . , aj ) = j − 3, a3 + 1, . . . , aj + 1. Diese transformierteKonstellation hat (v) j = j − 1 Türme und der erste Turm von links hat (vi) a1 =j − 3 Steine. Aus (v) und (vi) folgt a1 = j − 2. Widerspruch zu Eigenschaft 6.
�
3 Ein Konstruktionsprinzip für Zyklen
Die genannten Eigenschaften geben Anlass zu folgendem Konstruktionsprinzip fürZyklen: Für eine Gesamtzahl k von Spielsteinen mit d(n − 1) < k ≤ d(n) mitd(n) = 1 + 2 + 3 + · · · + n lässt sich jede Konstellation aus einem Zyklus folgen-dermaßen konstruieren: Eine Anzahl von i Türmen (mit i = k − d(n − 1)) aus den n
Türmen mit den Höhen n − 1, n − 2, n − 3, . . . ,3,2,1,0 wird jeweils um 1 Spiel-stein erhöht. Es gibt
( ni
)Möglichkeiten i Steine einzeln auf n Türme zu vertei-
len. Diese( n
i
)Möglichkeiten werden in geeigneten Zyklen zu maximal je n Kon-
stellationen zusammengestellt. Zum Beispiel sei n = 6, i = 2 und k = d(5) + 2 =(1 + 2 + 3 + 4 + 5) + 2 = 17:
56 R. Schröder
Zyklus 1: Die Abstände um 1 vergrößerter Türme sind 2 bzw. 4:
5, 4, 4, 2, 2, 05, 5, 3, 3, 1, 06, 4, 4, 2, 1, 05, 5, 3, 2, 1, 16, 4, 3, 2, 2, 05, 4, 3, 3, 1, 1
Zyklus 2: Die Abstände um 1 vergrößerter Türme sind 1 bzw. 5:
6, 5, 3, 2, 1, 06, 4, 3, 2, 1, 15, 4, 3, 2, 2, 15, 4, 3, 3, 2, 05, 4, 4, 3, 1, 05, 5, 4, 2, 1, 0
Zyklus 3: Die Abstände um 1 vergrößerter Türme sind in beiden Fällen 3:
6, 4, 3, 3, 1, 05, 4, 4, 2, 1, 15, 5, 3, 2, 2, 0
Die erhöhten Türme sind unterstrichen. Ihre Abstände werden über das Ende derjeweiligen Konstellation hinausgehend wieder von vorn gezählt. Die Unterstreichun-gen „wandern“ bei jeder Transformation um eine Position nach links. Nach dem Er-reichen der Position ganz links springt die Erhöhung ganz nach rechts. Dies ist mitder Definition der Transformation erklärbar. Die am Beispiel gezeigten Eigenschaftengelten auch allgemein.
Es bleibt noch zu klären, dass eine Erhöhung eines Turmes um mehr als 1 bzw.eine Verminderung einzelner Türme um 1 (oder mehr) nicht auf Zyklen führen kann.
Zur Subtraktion eines Steines von einem Turm der Konstellation n − 1, n −2, . . . ,2,1,0.
Es wird davon ausgegangen dass für die Gesamtzahl k der Steine gilt: k = d(n −1) + i(n ≥ i > 0). Um dies zu gewährleisten, muss jede Subtraktion eines Steinesdurch eine Addition zu einem anderen Turm kompensiert werden. Andernfalls gältefür die Gesamtzahl k der Steine d(n − 2) < k < d(n − 1) und die Subtraktion einesSteines von einem Turm der Konstellation n − 1, n − 2, . . . ,2,1,0 kann als Additionvon n − 2 Einsen zu Türmen der Konstellation n − 2, n − 3, . . . ,2,1,0 interpretiertwerden. Die Addition eines Steines kann nicht unmittelbar links von der Subtraktionstattfinden, da dann gegen Eigenschaft 7 verstoßen würde. Für weitere Betrachtungengehen wir von der Konstellation n,n−2, n − 4, n−4, n−5, . . . ,2,1,0 aus (um 1 er-höhter Turm doppelt unterstrichen, um 1 verminderter Turm einfach unterstrichen).Dann gilt: τ 3(n,n − 2, n − 4, n − 4, n − 5, . . . ,2,1,0) = n − 1, n − 2, . . . ,3,3,0.Dies ist ein Verstoß gegen Eigenschaft 7. Liegt zwischen erhöhtem und verminder-tem Turm mehr als ein Turm, würde dieser Abstand nach n Transformationen um 1vermindert. Der angenommene Fall stellt also keine Beschränkung der Allgemeinheitdar.
Der Goldene Schnitt in Türmen aus Spielsteinen 57
Zur Addition zweier Steine zu einem Turm der Konstellation n − 1, n − 2, . . . ,2,
1,0.Wir unterscheiden drei Fälle:
Fall 1 Der erste Turm von links wird um 2 erhöht. Dann gilt: τ−1z (n + 1, n − 2, n −
3, . . . ,2,1,0) = n − 1, n,n − 3, n − 4, . . . ,3,2,1. Die Addition von 2 zum erstenTurm widerspricht der Eigenschaft 2.
Fall 2 Der zweite Turm von links wird um 2 erhöht. Dann entsteht die Konstel-lation n − 1, n,n − 3, . . . ,2,1,0. Diese steht in Widerspruch zu Eigenschaft 2.Der Widerspruch ist auflösbar, wenn der erste Turm gleichzeitig um 1 erhöhtwird: n,n,n − 3, . . . ,2,1,0. Dann gilt allerdings τ−1
z (n,n,n − 3, . . . ,2,1,0) =n − 1, n − 1, n − 1, . . . ,2,1,0, was im Widerspruch zu Eigenschaft 5 steht.
Fall 3 Der i-te Turm (i > 2) wird um 2 erhöht. Dann entsteht eine Konstellation,die der Eigenschaft 2 widerspricht. Dieser Widerspruch ist dadurch kompensierbar,dass der linke Nachbar des um 2 erhöhten Turmes um 1 erhöht wird. Dann aberentsteht ein Widerspruch zu Eigenschaft 5.
Im Falle i = n ist jeder der Türme der Konstellation n − 1, n − 2, . . . ,2,1,0 um1 zu erhöhen. Einzige Konstellation des so entstehenden Zyklus ist n,n − 1, n −2, . . . ,2,1.
Satz 1 Für a1 +a2 +a3 +· · ·+aj = 1+2+3+· · ·+n = d(n) gilt: Die Konstellationa1, a2, a3, . . . , aj geht nach endlich vielen Spielzügen in einen Zyklus der Länge 1 mitder einzigen Konstellation n,n − 1, n − 2, . . . ,2,1 über.
Für d(n − 1) < a1 + a2 + a3 + · · · + aj = d(n − 1) + i < d(n) geht die Kon-stellation a1, a2, a3, . . . , aj nach endlich vielen Spielzügen in einen von
⌈( ni
) : n⌉
verschiedenen Zyklen der maximalen Länge n über. (�x� ist die nächste natürlicheZahl über x.)
4 Der Goldene Schnitt in Spielen mit Spielsteinen
Der Goldene Schnitt begegnet uns in vielfältigen Zusammenhängen – so zum Bei-spiel auch in Spielen mit Spielsteinen. Beutelspacher/Petri erwähnen hier WythoffsSpiel [2], benannt nach seinem Erfinder, Willem Abraham Wythoff. Dies sind dieRegeln:
Zwei verschieden hohe Stapel (= Türme) gleichartiger Spielsteine sind vorzwei Spielern aufgebaut und sollen von diesen abwechselnd dezimiert werdennach folgenden Vorschriften:
• Ein Spieler darf, wenn er am Zug ist, von beiden Stapeln gleich viele Steineentnehmen.
• Ein Spieler darf, wenn er am Zug ist, von einem Stapel so viele Steineentnehmen, wie er will.
• Gewonnen hat der Spieler, der insbesondere den letzten Stein nimmt.
58 R. Schröder
Wythoff selbst hat sein Spiel vollständig analysiert. Der Sieger muss ganz be-stimmte Zahlenpaare kennen, die jeweils beschreiben, auf welche Steinzahlen er dieTürme reduzieren muss, damit er sicher gewinnt. Als ein Beispiel sei das Paar (2;1)
genannt. Wenn es einem Spieler gelingt, dem Gegner zwei Türme mit den Steinzah-len 1 und 2 zu hinterlassen, kann er sich des Sieges gewiss sein. Wythoff [3] hat nichtnur die Zahlenpaare genannt, die sich der spätere Sieger merken muss, er hat auch ei-ne Formel dafür angegeben: ([nΦ], [n · (Φ +1)]). Zum Vertändnis der Formel: [x] ist
die nächste natürliche Zahl unter x, Φ =√
5+12 ist das größere Teilungsverhältnis des
Goldenen Schnittes und n durchläuft die natürlichen Zahlen. Seine Formel zog Wyt-hoff – nach seinen eigenen Worten – „out of a hat“ [4]; er beweist seine Vermutungnicht. Der Beweis gelingt Coxeter [5], der sich wiederum auf den Satz von Beatty [6]stützt. Man hat die Zahlenfolgen ([nΦ])n∈N und ([n · (Φ + 1)])n∈N „Lower WythoffSequence“ und „Upper Wythoff Sequence“ genannt.
In den Abschn. 2 und 3 wurde das Spiel „Türme bauen“ hinsichtlich seiner Zy-klen untersucht. Im Folgenden geht es um die Anzahl von Transformationen vor demErreichen eines Zyklus, wenn die Startkonstellation die Liste der ersten n natürlichenZahlen ist. Diese Fragestellung führt ebenfalls auf die „Lower Wythoff Sequence“.Eine Annäherung an die Antwort auf diese Fragestellung geschieht über die Betrach-tung der Entwicklung von Anfangsgliedern der zugehörigen Folge von Konstella-tionen. Die Startkonstellation wird wegen ihrer Bedeutung für alles Folgende durchAbb. 1 verdeutlicht.
Jeder Spielzug besteht darin, den am weitesten links stehenden Turm aufzuneh-men und einzeln Stein für Stein auf die folgenden Türme zu verteilen. Wird dieStartkonstellation gemäß obiger Abbildung kurz mit
1, 2, 3, 4, 5 beschrieben, entsteht daraus3, 3, 4, 5 nach dem ersten Spielzug und
4, 5, 6 nach dem zweiten Spielzug.
In dieser Konstellationenfolge wird jeweils derjenige Turm betrachtet, der als ers-ter von links eine positive Anzahl von Steinen aufweist. Die Höhen der betrachte-ten Türme bilden die Zahlenfolge 1, 3, 4, 6 usw. Man kann vermuten, dass hier die„Lower Wythoff Sequence“ entsteht.
Eine zweite Fragestellung befasst sich mit einer endlichen Anzahl von Türmen.
Abb. 1 Die Türme sind von links nach rechts mit den natürlichen Zahlen nummeriert und jeder Turmbesteht zu Beginn des Spiels aus so vielen Steinen, wie seine Nummer angibt. Für die anfänglichenBetrachtungen ist die Anzahl der Türme nach rechts fortlaufend theoretisch unbegrenzt
Der Goldene Schnitt in Türmen aus Spielsteinen 59
Ein Beispiel:
1, 2, 3, 43, 3, 4
4, 5, 16, 2, 1, 1
3, 2, 2, 1, 1, 13, 3, 2, 1, 1
4, 3, 2, 1
Die letzte Konstellation verschiebt sich von nun an zwar noch nach rechts, bleibtaber konstant. Insgesamt waren hier 6 Spielzüge erforderlich, um die Startkonstellati-on zu spiegeln. Bei Wiederholung des Spiels für verschiedene Anzahlen von Türmenerhalten wir folgende Wertetabelle:
Anzahl der Türme in der Startkonstellation 1 2 3 4 5Anzahl der Züge bis zur Spiegelung der Startkonstellation 1 3 4 6 8
Dies ist die Wertetabelle einer Zahlenfolge, die wiederum verdächtig ist, eine „LowerWythoff Sequence“ zu sein. Das Ziel des vorliegenden Aufsatzes ist der Beweis desfolgenden Satzes.
Satz Konstellationen – das sind Aufstellungen von Türmen in einer Reihe von linksnach rechts – werden durch folgende Transformationen (= Spielzüge) in neue Kon-stellationen überführt: Der am weitesten links stehende Turm mit einer positiven Zahla von Steinen wird abgeräumt und die nächsten nach rechts anschließenden a Türmeder Turmfolge werden jeweils um 1 Stein aufgestockt, wobei fehlende Türme von derHöhe Null auf die Höhe 1 gebracht werden müssen.
Fall 1 (unendlich viele Türme) Die Startfolge besteht aus einer Turmfolge mitden Turmhöhen 1,2,3,4,5, . . . Steine (von links nach rechts notiert). Betrachtenwir bei jeder Operation den abgeräumten Turm, so ist die Folge der Steinzahlender abgeräumten Türme in der Reihenfolge ihres Abräumens die Lower WythoffSequence.
Fall 2 (endlich viele Türme) Die Startfolge besteht aus einer Turmfolge mit denTurmhöhen 1,2,3,4,5, . . . , n Steine (von links nach rechts notiert).
k(n) sei die kleinste Anzahl von Operationen, die notwendig ist, um die Startfolgezu spiegeln. Dann gilt k(n) = [n · Φ], mit anderen Worten: Die Folge (k(n))n∈N istdie Lower Wythoff Sequence.
Der Beweis der Behauptung zu Fall 1 wird als Grundlage für den Beweis der Be-hauptung zu Fall 2 benötigt. Im ersten Beweis wird eine Funktion f aus den Trans-formationsvorschriften zwischen den Turmfolgen abgeleitet, die jeder Turmnummer#n der Startfolge eine Turmhöhe im Augenblick des Abräumens zuordnet. Zusätzlichmuss die Gültigkeit der Formel
f (n) = [n · Φ]für die so konstruierte Folge gezeigt werden.
60 R. Schröder
5 Lucas-Folgen
Die Konstruktion von Zahlenpaaren (n;f (n)) abgeleitet aus den Spielregeln beginntmit der Konstruktion einer Zahlenfolge kn, f (kn), kn+1, f (kn+1), . . . Dafür wird einTurm #kn frei gewählt oder durch hier noch nicht wesentliche Vorschriften festgelegt.Die Anzahl Spielsteine dieses Turmes nach kn − 1 Spielzügen, wenn also links vonTurm #kn alle Türme abgeräumt sind, werde mit f (kn) bezeichnet. Der Turm, aufwelchen der letzte Stein der f (kn) Steine des Turmes #kn im kn-ten Spielzug fällt,wird mit #kn+1 bezeichnet. Dann gelten die folgenden Gleichungen:
f (kn) + kn = kn+1 und (1)
f (kn) = kn+1 − kn. (1a)
Wie oben erwähnt, ordnet das Funktionssymbol f jeder Turmnummer eine AnzahlSteine im Moment der Verteilung zu. f (kn+1) bezeichnet demnach die Anzahl Steinedes Turmes #kn+1, wenn alle Türme links davon abgeräumt sind.
Hilfssatz 1 k1, f (k1), k2, f (k2), . . . ist eine Lucas-Folge.1
Beweis des Hilfssatzes 1 Nachdem sich (1) unmittelbar aus der Konstruktion derFolge kn, f (kn), kn+1, f (kn+1), . . . ergibt, bleibt zu zeigen
f (kn) + kn+1 = f (kn+1). (2)
Der letzte Stein des Turms #kn fällt bei seiner Verteilung (wenn also links von #kn
alle Türme abgeräumt sind) auf den Turm #kn+1. Wenn später dann auch alle Türmelinks von #kn+1 abgeräumt sind, liegen auf Turm #kn+1 sowohl die kn+1 Steine vomAnfang des Spiels als auch je ein Stein der Türme von #kn bis #kn+1 −1, also kn+1 −kn weitere. Insgesamt enthält der Turm also kn+1 + (kn+1 − kn) Steine, wenn linksvon ihm alles abgeräumt ist. Diese Anzahl bezeichnen wir mit f (kn+1) und es gilt
f (kn+1) = 2kn+1 − kn. (3)
Die Subtraktion von (3) und (1a) ergibt:
f (kn+1) − f (kn) = kn+1. (4)
(4) kann in (2) umgeformt werden. �
Nach dem Konstruktionsprinzip des Hilfssatzes 1 findet man eine unendliche An-zahl von Paaren (kn, f (kn)), wenn ein Startpaar (k1, f (k1)) gegeben ist. Da wir zum
1Die Definition von Lucas-Folgen ist in der Literatur nicht einheitlich. Hier wird eine Definition verwen-det, die bei A. Beutelspacher, B. Petri, „Der Goldene Schnitt“, Spektrum, Akad. Verlag, Heidelberg, Berlin,Oxford, 1996, auf Seite 92 gefunden wurde. Danach ist eine Lucas-Folge durch zwei frei gewählte An-fangsglieder sowie die Vorschrift festgelegt, dass jedes weitere Glied die Summe seiner beiden Vorgängerist.
Der Goldene Schnitt in Türmen aus Spielsteinen 61
Beispiel wissen, dass ganz am Anfang der Konstruktion (k1, f (k1)) = (1,1) gilt,können wir daraus die Paare (2,3), (5,8), (13,21), . . . entwickeln.
Mit anwachsenden Zahlen werden die Lücken in dieser Paarmenge immer größer.Zum Beispiel fehlen die Paare (3, f (3)) und (4, f (4)) in dieser Konstruktion. Wirbenötigen eine weitere Vorschrift zur Konstruktion von Paaren (k;f (k)).
Zuvor wird Hilfssatz 2 bewiesen:
Hilfssatz 2 Für Paare (n,f (n)) nach Hilfssatz 1 gilt f (n) = [n ·Φ] oder – gleichbe-deutend 0 < n ·Φ −f (n) < 1, wenn das erste Paar (r, s) der genannten Lucas-Folgedie Bedingung 0 < r · Φ − s < 1 erfüllt.
Beweis des Hilfssatzes 2 Wir zeigen zunächst, dass für Lucas-FolgengliederL(x)
gilt: Φ · L(2n − 1) − L(2n) = (Φ − 1)2n−2 · (r · Φ − s). Wir nutzen, dass für dieLucas-Folge mit den Startgliedern r und s ist eine explizite Formel bekannt ist:
L(n) = 1√5
·(
Φn−2 · (Φ · s + r) +(−1
Φ
)n−1
· (Φr − s)
).
Mit Hilfe dieser Formel gewinnen wir die Differenz Φ ·L(2n− 1)−L(2n), nämlich:
Φ · L(2n − 1) − L(2n) = (√
5 − 1)2n
22n+1· (2r(
√5 + 2) − s(
√5 + 3)
). (∗)
Die rechte Seite der (∗) formen wir um:
(√5 − 1)
2
)2n
· 2r(√
5 + 2) − s(√
5 + 3)
2
= (Φ − 1
)2n · (r(√5 + 2) − s · (Φ + 1))
= (Φ − 1)2n · (r(2Φ + 1) − s · (Φ + 1))
= (Φ − 1)2n−2 · (r(2Φ + 1)(Φ − 1)2 − s · (Φ + 1)(φ − 1)2)
= (Φ − 1)2n−2 · (rΦ − s).
Die Umformung der linken Seite der (∗) folgt aus der Entsprechung (kn, f (kn)) =(L(2n − 1),L(2n)) und es gilt
Φ · kn − f (kn) = (Φ − 1)2n−2 · (r · Φ − s).
Die linke Seite dieser Gleichung ist dann ein Term zwischen 0 und 1, wenn die rechteSeite ein solcher ist. Die rechte Seite dieser Gleichung ist ein Term zwischen 0 und1, wenn gilt
0 < r · Φ − s < 1
was laut Voraussetzung erfüllt ist. �
62 R. Schröder
6 Eine zweite Konstruktionsvorschrift
Die Konstruktion der Paare (n,f (n)) nach Hilfssatz 1 ist im Hinlick auf eine Voll-ständigkeit der Wertetabelle noch unbefriedigend. In den Lücken fehlen insbesonderePaare (m,f (m)) mit m = f (n). Zum Beispiel fehlt das Paar (3, f (3)) mit 3 = f (2).Solche Paare werden nach Hilfssatz 3 konstruiert:
Hilfssatz 3 Für Paare (n,m) nach Hilfssatz 1 gilt: f (m) = m + n − 1.
Im Beispiel: f (3) = 3 + 2 − 1 = 4
Beweis des Hilfssatzes 3 Für diesen Beweis definieren wir die Umkehrfunktion f −1
zur Funktion f des ersten Beweises. Während f die natürlichen Zahlen N auf eineTeilmenge M derselben abbildet, bildet f −1
M auf N ab. Implizit wird f −1 definiertdurch: m = f (n) ⇔ f −1(m) = n und explizit wird f −1 definiert durch f −1(m) =�m/Φ�; dabei ist �x� die nächste natürliche Zahl über x (Iverson-Klammer). DieGleichung f −1(f (n)) = n ist leicht zu zeigen.
Es sei m eine natürliche Zahl aus M, dann gilt:
[Φ · m] = �Φ · m� − 1,
[Φ · m] = ⌈(1/Φ + 1) · m⌉ − 1,
[Φ · m] = �m/Φ + m� − 1,
[Φ · m] = �m/Φ� + m − 1,
f (m) = f −1(m) + m − 1.
Da f −1 nur für Funktionswerte von f definiert ist und m aus M sein soll, setzenwir m = f (n). Dann gilt:
f(f (n)
) = f −1(f (n)) + f (n) − 1 oder
f(f (n)
) = n + f (n) − 1 (Verknüpfung von f −1 und f ),
oder wegen m = f (n) gilt f (m) = m + n − 1. �
Auch für die Konstruktionsvorschrift von Paaren nach Hilfssatz 3 muss gezeigtwerden, dass 0 < Φ ·m− f (m) < 1. Hierzu setzen wir voraus, dass [Φ · n] zwischenΦ · (n − 1) und Φ · n liegt:
Φ · (n − 1) < [Φ · n] < Φ · n,
n − 1 < 1/Φ · [Φ · n] < n,
0 < 1/Φ · [Φ · n] − n + 1 < 1,
0 < 1/Φ · [Φ · n] + [Φ · n] − [Φ · n] − n + 1 < 1,
0 < (1/Φ + 1) · [Φ · n] − [Φ · n] − n + 1 < 1,
Der Goldene Schnitt in Türmen aus Spielsteinen 63
0 < Φ · [Φ · n] − ([Φ · n] + n − 1) < 1,
0 < Φ · m − f (m) < 1.
7 Das Wythoff-Array
Wir konstruieren jetzt eine Wertetabelle, deren Zeilen Lucas-Folgen sind und derenZeilenanfänge ab Zeile 2 nach Hilfssatz 3 konstruiert wurden:
(1,1), (2,3), (5,8), (13,21), . . .
(3,4), (7,11), (18,29), . . .
(4,6), (10,16), (26,42), . . .
(6,9), (15,24), . . .
(8,12), (20,32), . . .
(9,14), (23,37), . . .
(11,17), . . .
Entfernen wir aus dieser Wertetabelle alle Klammern und dann die erste Spalte,so erhalten wir das Wythoff-Array2:
1 2 3 5 8 13 21 34 55 . . .
4 7 11 18 29 47 76 123 199 . . .
6 10 16 26 42 68 110 178 288 . . .
9 15 24 39 63 102 165 267 432 . . .
12 20 32 52 84 136 220 356 576 . . .
14 23 37 60 97 157 254 411 665 . . .
17 28 45 73 118 191 309 500 809 . . .
19 31 50 81 131 212 343 555 898 . . .
22 36 58 94 152 246 398 644 1042 . . .
Über das Wythoff-Array sind insbesondere folgende Charakteristika bekannt:
1. Die erste Spalte ist die Zahlenfolge ([Φ · n] + n − 1)n∈N und die zweite Spalte istder Zahlenfolge (2 · [Φ · n] + n − 1)n∈N.
2. Die Zeilen sind Lucas Folgen.3. Jede natürliche Zahl ist genau einmal enthalten.
Die Eigenschaften 1 und 2 gelten laut Konstruktion auch für die Wertetabelle derFunktion f nach Streichung der Klammern und der ersten Spalte. Die Eigenschaft 3nutzen wir für den Vollständigkeitsnachweis der Wertetabelle:
Die paarweise Klammerung der Zahlen des Wythoff-Array (ab Spalte 2) bewirkt,dass die Menge der im Wythoff-Array enthaltenen natürlichen Zahlen in den Defi-nitionsbereich und den Wertevorrat der Funktion f aufgeteilt wird. Deshalb fehlenin der durch die paarweise Klammerung entstehenden Wertetabelle alle Zahlen desDefinitionsbereichs, die gleichzeitig zum Wertevorrat gehören. Dies sind die Zahlenf (n) = [Φ · n] für n ∈ N. Genau diese werden dem Wythoff-Array als erste Spaltevorangestellt:
2http://mathworld.wolfram.com/WythoffArray.htm. Aufgerufen am 02.08.2011.
64 R. Schröder
1 1 2 3 5 8 13 21 34 55 . . .
3 4 7 11 18 29 47 76 123 199 . . .
4 6 10 16 26 42 68 110 178 288 . . .
6 9 15 24 39 63 102 165 267 432 . . .
8 12 20 32 52 84 136 220 356 576 . . .
9 14 23 37 60 97 157 254 411 665 . . .
11 17 28 45 73 118 191 309 500 809 . . .
12 19 31 50 81 131 212 343 555 898 . . .
14 22 36 58 94 152 246 398 644 1042 . . .
Durch paarweise Zusammenfassung der Zahlen im so ergänzten Wythoff Arrayerhält man die Zahlenpaare der hier konstruierten Wertetabelle:
(1,1), (2,3), (5,8), (13,21), (34,55), . . .
(3,4), (7,11), (18,29), (47,76), (123,199), . . .
(4,6), (10,16), (26,42), (68,110), (178,288), . . .
(6,9), (15,24), (39,63), (102,165), (267,432), . . .
(8,12), (20,32), (52,84), (136,220), (356,576), . . .
(9,14), (23,37), (60,97), (157,254), (411,665), . . .
(11,17), (28,45), (73,118), (191,309), (500,809), . . .
(12,19), (31,50), (81,131), (212,343), (555,898), . . .
(14,22), (36,58), (94,152), (246,398), (644,1042), . . .
8 Die zweite Vermutung
Nach dem Beweis zur ersten Vermutung gilt, dass nach x − 1 Spielzügen, also indem Moment, in dem der x-te Turm als nächster abgeräumt wird, dieser f (x) Steineenthält. Wir gehen weiterhin davon aus, dass die Startkonstellation aus n Türmenbestand und x > n gilt. Dann hat der x-te Turm nach x − 1 Spielzügen f (x) − x
Steine. Setzen wir jetzt x = f (n), erhalten wir:
(i) Nach f (n) − 1 Spielzügen hat der Turm #f (n) genau f (f (n)) − f (n) Steine.Hilfssatz 3 sagt, was für f (f (n)) einzusetzen ist, und wir erhalten:
(ii) Nach f (n) − 1 Spielzügen hat der Turm #f (n) genau n − 1 Steine.Ebenso viele Steine hat auch der unmittelbare rechte Nachbar des Turmes
#f (n), der Turm #(f (n) + 1).(iii) Nach f (n) − 1 Spielzügen hat der Turm #f ((n) + 1) genau n − 1 Steine. Das
wird folgendermaßen begründet:Der Turm #f (n) erhält einen Stein aus der Verteilung von Turm #k (mit f (k)
Steinen), wenn gilt
k + f (k) ≥ f (n).
Wählen wir k = f −1(n) (d.h. n = f (k)), dann gilt nach Hilfssatz 3
k + f (k) = f (n) + 1 mit(n = f (k)).
Das bedeutet: gleichzeitig mit Turm #f (n) erhält auch Turm #(f (n) + 1) einenStein. Beim Verteilen von Turm #(k − 1) ist f (k − 1) < f (k) und daher (k −
Der Goldene Schnitt in Türmen aus Spielsteinen 65
1)+f (k−1) mindestens um zwei Steine kleiner als f (n)+1. Also ist der Turm#k (mit k = f −1(n)) der erste Turm, dessen Verteilung bis Turm #f (n) reicht.Die Türme #f (n) und#(f (n) + 1) bleiben so lange gleichhoch, bis #f (n) zurVerteilung ansteht.
(iv) Nach f (n) Spielzügen liegen auf Turm #(f (n) + 1) genau n Steine.Denn: Im f (n)ten Zug wird Turm #f (n) abgeräumt und Turm #f (n) + 1
erhält einen Stein hinzu.
Hilfssatz 4 Die Türme rechts vom Turm #n seien zu Beginn des Spiels leer. Wir be-trachten zwei benachbarte Türme #i und #(i + 1) rechts von einem Turm #n, wobeilinks von Turm #i alles abgeräumt ist. Dann sind die Anzahlen der Steine auf denTürmen #i und #(i + 1) entweder gleich oder #(i + 1) enthält einen Stein wenigerals #i.
Beweis Aus Satz 1 lässt sich für nichtabbrechende Turmfolgen schließen, dass sichdie Turmhöhen f (i) und f (i + 1) um 1 oder maximal um 2 unterscheiden. Solange#i noch nicht abgeräumt ist, hat deshalb (im Fall nichtabbrechender Turmfolgen)#(i +1) einen oder keinen Stein mehr als #i. Laut Voraussetzung sind die Turmhöhender Türme #i und #(i + 1) bei Spielbeginn gleich Null. Daher sind die Anzahlen derSteine in den Türmen #i und #(i + 1) entweder gleich oder #(i + 1) enthält einenStein weniger als #i. �
Die betrachtete Turmfolge soll weiterhin aus n Türmen bestehen. Wenn die f (n)
Steine des Turms #n verteilt werden, fällt der letzte Stein auf Turm #(n + f (n)). Biszur Verteilung von Turm #f (n) fällt kein Stein über #(n + f (n)) hinaus. Daher hatnach f (n) Spielzügen das Spiel (n + f (n)) − f (n) = n Türme.
Nach f (n) Spielzügen liegen auf Turm #(f (n) + 1) genau n Steine und das Spielhat n Türme einer Höhe größer Null. Außerdem haben benachbarte Türme entwedergleichviele Steine oder der rechte Turm hat einen Stein weniger, als der linke. Esgibt d(n) = 1 + 2 + 3 + · · · + n Spielsteine. Dann ist die folgende Verteilung dieeinzig mögliche: n,n−1, n−2, . . . ,3,2,1. Nach f (n) Spielzügen ist die Turmfolge1,2,3, . . . , n − 2, n − 1, n also gespiegelt.
Die gewonnenen Ergebnisse fassen wir zusammen in folgendem
Satz 2 Gegeben ist eine endliche Turmfolge, das ist eine endliche mit den natürli-chen Zahlen nummerierte Aufstellungen von Türmen in einer Reihe von links nachrechts, deren Türme vor dem ersten Spielzug jeweils aus so vielen Steinen bestehen,wie ihre Nummer angibt. Turmfolgen werden durch folgende Spielzüge in neue Turm-folgen transformiert: Der am weitesten links stehende Turm mit einer positiven Zahla von Steinen wird abgeräumt und die nächsten nach rechts anschließenden a Türmeder Turmfolge werden jeweils um 1 Stein aufgestockt. Dabei fehlende Türme habendie Anfangshöhe Null. Dann sind f (n) Spielzüge erforderlich um die Turmfolge zuspiegeln. (f (n))n∈N ist die Lower Wythoff Sequence.
66 R. Schröder
Literatur
1. Hasemann, K., Leonhardt, U., Szambien, H.: Denkaufgaben Für die Erste und Zweite Klasse, S. 106.Cornelsen Verlag Scriptor, Berlin (2006). Das von Hasemann vorgeschlagene Spiel „Türme bauen“führt auf deutlich schwierigere Fragen und Antworten, als der Titel des Buches vermuten lässt
2. Beutelspacher, A., Petri, B.: Der Goldene Schnitt. Spektrum, Akad. Verlag, Heidelberg (1996)3. Wythoff, W.A.: A modification of the game of nim. Nieuw Arch. Wiskd. 7, 199–202 (1907)4. Coxeter, H.S.M.: The Golden Section, Phyllotaxis and Wythoffs Game, Scripta Mathematica, vol. XIX,
p. 142. Wiley, New York (1953)5. Coxeter, H.S.M.: The Golden Section, Phyllotaxis and Wythoffs Game, Scripta Mathematica, vol. XIX,
pp. 142–143. Wiley, New York (1953)6. “Almost Alternating Sums”, O’Bryant, Kevin, San Diego; Reznick, Bruce, Urbana-Champaign;
Serbinowska, Monika, Ogden, 2003, http://www.math.uiuc.edu/~reznick/ors.pdf. Aufgerufen am08.04.2011
