Mathematik und Spiele

Tag der offenen T¨ur
Fachbereich 2
Informatik, Technik und Wirtschaft
Mathematik und Spiele
Prof. Dr. Dieter Kilsch
9. Mai 2015
Inhaltsverzeichnis
1 Das K¨
onigsberger Bru
¨ ckenproblem und Eulersche Wege
1.1 Das K¨
onigsberger Br¨
uckenproblem . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Das (Doppel-)haus des Nikolaus . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
2
4
2 Die
2.1
2.2
2.3
Euler-Charakterisitk (Fl¨
achen-Kanten-Ecken-Formel)
Grafen, Fl¨
achen, Kanten und Ecken (Knoten) . . . . . . . . . . . . . . . . . . . .
Lege-Spiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Platonische K¨
orper . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
4
5
5
3 Induktion und R¨
atsel
3.1 Induktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Die Blau¨
augigen auf der Insel des grausamer K¨
onig . . . . . . . . . . . . . . . . .
6
6
7
4 Das Nimmspiel
4.1 Gewinnsituationen am Ende des Spiels . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Dualzahlen, Gewinn- und Verliersituationen . . . . . . . . . . . . . . . . . . . . .
8
9
9
5 Geometrie und Kombinatorik
5.1 Zehn Punkte und f¨
unf Geraden . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Erweiterung des R¨
atsels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
10
10
Literaturverzeichnis
11
In diesem Artikel stelle ich einige Spiele und R¨
atsel vor. Zu den Spielen gebe ich GewinnStrategien aus der Mathematik an, die R¨
atsel werden mit Hilfe mathematischer Ideen gel¨
ost.
Das Literaturverzeichnis enth¨
alt einige popul¨
arwissenschaftliche und unterhaltsame Mathematikb¨
ucher.
Prof. Dr. Dieter Kilsch
1
Mathematik und Spiele
2
Das K¨
onigsberger Bru
¨ ckenproblem und Eulersche Wege
1.1
Das K¨
onigsberger Bru
¨ ckenproblem
Leonhard Euler1 l¨
oste 1735 das K¨
onigsberger Br¨
uckenproblem: In K¨
onigsberg gab es zu jener
Zeit sieben Br¨
ucken, die die Insel Kneiphof in der Pregel mit dem Umland verband. Die B¨
urger
K¨
onigsbergs hatten sich lange gefragt, ob es m¨
oglich sei, einen Sonntagsspaziergang zu machen,
der genau einmal u
ucke f¨
uhrt, s. Abb. 1, vgl. [14].
¨ ber jede Br¨
Euler l¨
oste dieses Problem mit einer Methode aus der Topologie, der Grafentheorie.
Definition 1.1 Ein Graf ist eine Menge von Knoten (Punkten) und Kanten (Linien), wobei
eine Kante immer zwei Knoten verbindet.
F¨
ur seine L¨
osung ersetzte Euler eine zusammenh¨
angende Landmassen durch einen Knoten
und f¨
ur jede Br¨
ucke u
ucke
¨ ber die Pregel verband er diejenigen Knoten, die zu den durch diese Br¨
verbundenen Landmassen geh¨
oren, durch eine Kante, s. Abb. 2. Die wichtigste Idee der L¨
osung
ist die Untersuchung folgender Eigenschaft eines Knotens:
Definition 1.2 Der Grad eines Knotens ist die Anzahl der in diesen Knoten m¨
undenden Kanten.
Wenn es den geforderten Sonntagsspaziergang gibt und man den zur¨
uckgelegten Weg als
Grafen betrachtet, dann wird der Grad eines Knotens beim Durchlaufen um zwei erh¨
oht. Damit
ist der Grad jedes Knoten eine gerade Zahl; vielleicht außer dem ersten und letzten, wenn Startund Endpunkt verschieden sind.
Ein solcher Weg in einem Grafen ist nach Euler benannt:
Definition 1.3 Ein Weg in einem Grafen, der alle Kanten genau einmal durchl¨
auft, heiß Eulerscher Weg.
Die obige Beobachtung beweist den entscheidenden Satz:
Satz 1.4 Ein Graf besitzt genau dann einen Eulerschen Weg, wenn die Anzahl der Knoten
ungeraden Grades null oder zwei ist.
Ist diese Anzahl null, so kann der Eulersche Weg in jedem Knoten begonnen werden. Andernfalls muss der Eulersche Weg in einem der beiden Knoten ungeraden Grades starten und endet
in dem anderen.
onigsberger
Aufgrund der in Abb. 3 notierten Grade aller Knoten ist damit klar, dass das K¨
Br¨
uckenproblem nicht l¨
osbar ist.
Man kann weiter interessante Mathematik treiben, wenn man die Geschichte des K¨
onigsberger
Br¨
uckenproblems unwahr erg¨
anzt, vgl. [14]:
Aufgrund des hohen Verkehrsaufkommens bei den Versuchen, einen Eulerschen Weg mit den
Pferdekutschen zu finden, beschloss die Stadtverwaltung den Bau einer weiteren Br¨
ucke zur
Kneiphof-Insel, s. Abb. 4. Nach Abb. 5 haben jetzt nur zwei Knoten ungeraden Grad und der
Graf enth¨
alt mehrere Eulersche Wege, die im oberen Knoten starten und im unteren enden, oder
umgekehrt. Jetzt konnten die oberen Schichten jeden Sonntag mit Ihren Pferdekutschen einen
der Eulerschen Wege abfahren.
Aufgrund des dadurch immer st¨
arker werdenden Verkehrs sahen sich die Stadtoberen gezwungen, auf den Br¨
ucken ein Einbahnstraßensystem einzuf¨
uhren. Dies ist in Abb. 6 dargestellt.
L¨
asst es einen Eulerschen Weg zu, der die Fahrtrichtung auf den Br¨
ucken beachtet?
Auch hierzu hat Euler die passende Theorie:
1
Leonhard Euler, schweizer Mathematiker(Berlin, St. Petersburg), 1707 (Basel) - 1783 (St. Petersburg)
Prof. Dr. Dieter Kilsch
Mathematik und Spiele
3
Abb. 1: Die Kneiphofbr¨ucken in K¨o-
Abb. 2: Das Br¨uckenploblem als
Abb. 3: Die negative L¨o-
nigsberg
Graf
sung des Br¨
uckenploblems
Abb. 4: Die Kneiphof-Entla-
Abb. 5: Die L¨osung des
stungsbr¨
ucke
Br¨
uckenploblems
Abb. 6: Einbahnstraßensy- Abb. 7: Knotengrade Abb.
stem 1
System 1
system 2
8:
Einbahnstraßen- Abb. 9: Knotengrade
System 2
Definition 1.5 Ein gerichteter Graf ist ein Graf, bei dem jede Kante eine Richtung besitzt.
Ein Eulerscher Wegin einem gerichteten Grafen ist ein Weg, der jede Kante einmal in Richtung
ihrer Orientierung durchl¨
auft.
Der Grad eines Knotens in einem gerichteten Grafen ist gleich der Differenz der Anzahl der
in den Knoten eingehenden Kanten und der aus dem Knoten ausgehenden Kanten.
In Abb. 7 sind die Knotengrade berechnet. Offensichtlich gilt der folgende Satz, nach dem
das Einbahnstraßensystem keinen Eulerschen Weg zul¨
asst:
Satz 1.6 Ein gerichteter Graf besitzt genau dann einen Eulerschen Weg, wenn alle oder alle
außer zwei Knoten den Grad null besitzen. Besitzen zwei Knoten nicht den Grad null, so muss
einer den Grad -1 haben und der andere den Grad 1. Der Erste muss als Startknoten genommen
werden.
Prof. Dr. Dieter Kilsch
Mathematik und Spiele
4
Die Eulersche Fangemeinde fuhr weiterhin den alten Eulerschen weg ab, was zu vielen Strafzetteln an der Nordostbr¨
ucke f¨
uhrte. Sie reichte eine Petition an den K¨
onigsberger Stadtrat ein,
die Fahrtrichtung der Nordostbr¨
ucke m¨
oge ge¨
andert werden. Nachdem dieser Petition stattgegeben wurde, war eine Eulerscher Weg wieder strafzettelfrei befahrbar. Diese L¨
osung ist in den
Abbildungen Abb. 8 und 9 dargestellt.
1.2
Das (Doppel-)haus des Nikolaus
Ein altes Spiel besteht in der Aufgabe das Haus des Nikolaus“, s. Abb. 10 in einem Zug zu
”
zeichnen. Damit fragt man in dem Grafen des Hauses nach einem Eulerschen Weg. Die Antwort
liefert Satz 1.4: Die in Abb. 11 eingetragenen Grade der Knoten machen klar, dass man in einem
der unteren Hausecken mit dem Zeichnen beginnen muss.
Abb. 10: Das Haus
Abb.
des Nikolaus
Haus
11:
Knotengrade
Abb. 12: Knotengrade Doppelhaus des Nikolaus
Im Doppelhaus des Nikolaus gibt es nach Abb. 12 vier Knoten ungeraden Grades. Damit
kann es nicht in einem Zug gezeichnet werden.
Nat¨
urlich k¨
onnen weitere Variationen des Hauses des Nikolaus untersucht werden: zweist¨
ockiges Haus, (einseitig)unterkellertes Doppelhaus, . . . .
2
Die Euler-Charakterisitk (Fl¨
achen-Kanten-Ecken-Formel)
2.1
Grafen, Fl¨
achen, Kanten und Ecken (Knoten)
Definition 2.1 Ein Graf ist eine Menge von Knoten (Punkten, Ecken) und Kanten (Linien),
wobei eine Kante immer zwei Knoten verbindet. e bezeichne die Anzahl der Ecken oder Knoten,
k die Anzahl der Kanten und f die Anzahl der durch den Grafen begrenzten Fl¨
achen einschließlich
der ¨
außeren Fl¨
ache.
Ich gehe n¨
aher auf diese Anzahlen ein:
(a) F¨
ur ein Dreieck gilt f − k + e = 2 − 3 + 3 = 2 .
(b) F¨
ur einen W¨
urfel gilt f − k + e = 6 − 12 + 8 = 2 .
(c) Zeichnet man in einer Ebene (oder auf eine Kugel) eine Kante mit ihren beiden Endknoten,
so gilt
f −k+e = 1−1+2 = 2.
(d) Gilt in einem Grafen die Formel f − k + e = 2 und erg¨
anzt man den Grafen um eine weitere
Kante, so k¨
onnen mehrere F¨
alle auftreten (Die Anzahl der Fl¨
achen, Kanten und Ecken im
neuen Grafen wird mit f ′ , k′ und e′ bezeichnet):
Prof. Dr. Dieter Kilsch
Mathematik und Spiele
5
• Die Kante ist nicht mit dem bisherigen Grafen verbunden:
f ′ − k′ + e′ = f − (k + 1) + (e + 2) = f − k + e + 1 = 3 .
• Die Kante ist in einem Knoten mit dem bisherigen Grafen verbunden:
f ′ − k′ + e′ = f − (k + 1) + (e + 1) = f − k + e = 2 .
• Die Kante verbindet zwei Knoten des bisherigen Grafen: Hierdurch wird eine Fl¨
ache
geteilt und es gilt:
f ′ − k′ + e′ = (f + 1) − (k + 1) + e = f − k + e = 2 .
Mit den beiden letzten Punkten kann man die Formel auf beliebige zusammenh¨
angende Grafen ausweiten:
Satz 2.2 (Euler) In einem zusammenh¨
angenden Grafen (in R2 , R3 oder auf der Kugeloberfl¨
ache) gilt
f −k+e=2.
2.2
Lege-Spiele
Diesen Satz wende ich auf ein erstes Beispiel an:
Beispiel 2.3 (17 H¨
olzer) Aus 17 H¨
olzer wird ein 2-zeiliges, 3-spaltiges Tableau aus Quadraten
olzer so entfernt werden, dass nur 3 Quadrate
gelegt, vgl. Abb. 13. Aus diesem Tableau sollen 5 H¨
u
urlich kein Holz u
¨brig bleiben. Es darf nat¨
¨brig bleiben.
Mit der Eulerschen Formel erhalten wir mit 4 Fl¨
achen (3 Quadrate und die Außenfl¨
ache) und
12 Kanten 4 − 12 + e = 2, woraus e = 10 folgt. Damit ber¨
uhren sich die 3 Quadrate in zwei
Ecken, sie haben keinen gemeinsame Kante. Abb. 14 zeigt bis auf Symmetrie die einzige L¨
osung.
Abb. 13: 17 H¨olzer
Abb. 14: 12 H¨olzer
Beispiel 2.4 Aus 6 H¨
olzern sollen 4 gleichseitige Dreiecke mit der Seitenl¨
ange ein Holz gebaut
werden.
Mit der Eulerschen Formel folgt f − 6 + e = 2. In der Ebene folgt mit f = 5 sofort der
Widerspruch e = 3, was nur ein Dreieck erlauben w¨
urde. Bei einem r¨
aumlichen Grafen erhalten
wir mit f = 4 f¨
ur die Eckenzahl e = 4. Dies ist der Tetraeder.
2.3
Platonische K¨
orper
Platonische K¨
orper sind im Sinne der Mathematik sch¨
one K¨
orper. Sie zeichnen sich durch hohe
Regelm¨
aßigkeit aus:
Definition 2.5 Ein platonischer K¨
orper ist ein durch regelm¨
aßige n-Ecke (n fest) begrenzter
K¨
orper, bei dem in jeder Ecke gleichviel Kanten enden.
Prof. Dr. Dieter Kilsch
Mathematik und Spiele
6
Abb. 15: Tetraeder
Diese Definition wird weiter untersucht und mit Hilfe der Euler-Charakteristik ausgewertet.
Es seien
• n die Anzahl der Kanten einer Fl¨
ache. Weil jede Kante zu zwei Fl¨
achen geh¨
ort, gilt n · f =
2k.
• m die Anzahl der Kanten einer Ecke. Weil jede Kante zwei Ecken (Knoten) hat, gilt
m · e = 2k.
Mit diesen Ergebnissen eliminieren wir e und f aus der Eulerschen Formel. Aus 2 = f − k + e =
2k
2k
1 1
1
1
1
1
1
−k+
folgt nach Division durch 2k
+ = +
und hieraus
+
> .
n
m
k 2
n m
n m
2
Dieses Ergebnis zeigt, dass n und m nicht groß werden d¨
urfen. Die Auswertung ist in folgenden
Tabellen enthalten:
1
n
+
1
m
−
1
2
k, e =
m
2k
m,
f=
2k
n
m
n
3
4
5
n
3
4
5
3
1
6
1
12
1
30
1
12
1
30
3
(6, 4, 4)
(12, 6, 8)
(30, 12, 20)
0
<0
4
(12, 8, 6)
−−
−−
<0
<0
5
(30, 20, 12)
−−
−−
4
5
Damit gibt es f¨
unf platonische K¨
orper:
(a) (n,m,k,e,f) = (3,3,6,4,4): Vierflach oder Tetraeder aus Dreiecken, s. Abb. 15.
(b) (n,m,k,e,f) = (3,4,12,6,8): Oktaeder aus Dreiecken, s. Abb. 16.
(c) (n,m,k,e,f) = (3,5,30,12,20): Ikosaeder (Zwanzigflach) aus Dreiecken, s. Abb. 18.
(d) (n,m,k,e,f) = (4,3,12,8,6): W¨
urfel: Sechsflach aus Quadraten, s. Abb. 17.
(e) (n,m,k,e,f) = (5,3,30,20,12): Dodekaeder (Zw¨
olfflach) aus F¨
unfecken: Pentagondodekaeder,
2
s. Abb. 18 .
Oktaeder und W¨
urfel, Ikosaeder und Dodekaeder sind dual3 zu einander.
3
3.1
Induktion und R¨
atsel
Induktion
In einem Witz steckt immer ein Kern Wahrheit oder Lebensweisheit, so auch in folgendem
Mathematik(er)witz:
2
Diese Grafik, Version vom 28.2.2005, steht unter der GNU-Lizenz in Wikipedia zur Verf¨
ugung. Sie stammt
von Peter Steinberg.
3
Der duale Graf entsteht dadurch, dass der Mittelpunkt einer Fl¨
ache zu einem Knoten wird und Knoten
benachbarter Fl¨
achen durch eine Kante verbunden werden.
Prof. Dr. Dieter Kilsch
Abb. 16: Oktaeder
Mathematik und Spiele
7
Abb. 17: W¨urfel
Abb. 18: Ikosaeder (gr¨un), Dodekaeder (gelb)
Ein Ingenieur und ein Mathematiker sollen nacheinander zwei Aufgaben l¨
osen:
¨
(a) Uber
einem offenen Feuer h¨
angt ein Haken, neben der Feuerstelle steht ein mit
Wasser gef¨
ullter Metalleimer. Die Aufgabe besteht darin, Wasser zu kochen.
Der Ingenieur h¨
angt den Eimer in den Haken und wartet bis das Wasser kocht.
Der Mathematiker macht dasselbe.
(b) Jetzt steht der gef¨
ullte Eimer einige Zentimeter weiter entfernt von der Feuerstelle. Die Aufgabe besteht wieder darin, Wasser zu kochen.
Der Ingenieur h¨
angt den Eimer in den Haken und wartet bis das Wasser kocht.
Der Mathematiker stellt den Eimer an die alte Stelle und sagt: Dass ich das
”
Problem von dieser Stelle aus l¨
osen kann, habe ich schon gezeigt.“
Es ist ein Prinzip der Mathematik, Probleme auf kleinere Probleme zur¨
uckzuf¨
uhren oder aus
L¨
osungen von kleinen Problemen auf L¨
osungen großer Probleme zu schließen. Dies wird in der
Mathematik wie folgt formuliert:
Satz 3.1 Gilt eine Eigenschaft f¨
ur eine erste Zahl und kann man zeigen, dass die Eigenschaft
von einer nat¨
urlichen Zahl, die mindestens so groß wie die erste ist, auf die n¨
achste u
¨bertragen
werden kann, so gilt sie f¨
ur alle nat¨
urliche Zahlen ab der genannten ersten.
Diese Technik wird zum Beispiel benutzt, um zu zeigen, dass jede nat¨
urliche Zahl gr¨
oßer
gleich zwei eine Primzahl ist oder als Produkt von Primzahlen geschrieben werden kann, also
als Produkt von Primzahlen mit mindestens einem Faktor:
Zwei ist eine Primzahl, sie ist also die erste Zahl, die die geforderte Eigenschaft hat.
Angenommen, wir haben f¨
ur alle Zahlen kleiner n die Eigenschaft nachgewiesen und m¨
ussen
sie jetzt f¨
ur n nachweisen. Es treten zwei F¨
alle auf. Entweder n ist eine Primzahl oder nicht. Im
ersten Fall ist die Eigenschaft nachgewiesen. Im zweiten Fall ist n = a · b ein Produkt kleinerer
Zahlen, die damit schon als Produkte von Primzahlen geschrieben werden k¨
onnen. Damit ist
auch n ein Produkt von Primzahlen.
⋄
Diese Technik hilft auch beim L¨
osen von R¨
atseln:
3.2
Die Blau¨
augigen auf der Insel des grausamer K¨
onig
R¨
atsel 3.2 Auf einer einsamen Insel herrscht ein grausiger K¨
onig, der blau¨
augige Untertanen
hasst. Eines Tages erblickt er beim Wandern u
augige(n). Noch am
¨ber seine Insel eine(n) Blau¨
selben Tag erl¨
asst er den Befehl, dass, da er blau¨
augige Inselbewohner(innen) gesehen habe, er
Prof. Dr. Dieter Kilsch
Mathematik und Spiele
8
verf¨
ugt, dass jede(r) Einwohner(in) seiner Insel in der Nacht, nachdem er/sie erkannt hat, dass
er/sie blau¨
augig ist, die Insel verlassen muss.
Jede(m) ist klar, dass der Befehl befolgt werden muss und keine(r) wagt, u
¨ber das Problem zu
sprechen. Auf der Insel gibt es keine Spiegel und auch sonst keine M¨
oglichkeit, sich in die Augen
zu schauen. Aber die Insel ist so klein, dass jede(r) jede(n) jeden Tag trifft und damit die Augen
der Anderen sehen kann.
Zehn Tage und N¨
achte bleibt alles beim Alten auf der Insel, aber am Morgen des elften Tages
fehlen einige Inselbewohner(innen), wieviele haben die Insel verlassen?
Ich beginne mit zwei Vor¨
uberlegungen:
(a) Angenommen, ich laufe den ganzen Tag u
augigen. Was
¨ ber die Insel und sehe keinen Blau¨
bedeutet dies?
Da der K¨
onig gesagt hat, er habe Blau¨
augige gesehen, muss ich schließen, dass ich blaue
Augen habe und werde die Insel in der ersten Nacht verlassen.
(b) Angenommen, ich laufe den ganzen Tag u
augigen.
¨ ber die Insel und sehe einen einzigen Blau¨
Ich erwarte nat¨
urlich von ihm, dass er in der ersten Nacht die Insel verl¨
asst. Aber am
kommenden Tag sehe ich ihn wieder. Was bedeutet dies? Auch er hat einen Blau¨
augigen
gesehen. Da ich nur einen Blau¨
augigen gesehen habe, muss ich der andere sein. Also verlasse
ich die Insel in der zweiten Nacht.
¨
Diese Uberlegungen
kann man nat¨
urlich weiter betreiben: Angenommen, ich laufe den ganzen
Tag u
augige. Ich erwarte nat¨
urlich von ihnen, dass sie die Insel
¨ ber die Insel und sehe zwei Blau¨
in der zweiten Nacht verlassen. Aber am Tag nach der zweiten Nacht sehe ich sie immer noch.
Was bedeutet dies?
...
In der Mathematik formuliert man eine Vermutung, und versucht, sie zu beweisen:
Satz 3.3 Wenn n Blau¨
augige auf der Insel leben, verlassen sie in der n-ten Nacht die Insel.
Dieser Satz ist f¨
ur n = 1 nach der ersten Vor¨
uberlegung richtig.
Angenommen, er gilt f¨
ur eine Zahl n von Blau¨
augigen, dann muss ich zeigen, dass er auch f¨
ur
n + 1 Blau¨
augige gilt. Wenn ich also einer der n + 1 Blau¨
augigen bin und beim Herumlaufen auf
der Insel folglich n Blau¨
augige ausmachen kann, erwarte ich, da der Satz f¨
ur n gilt, dass diese
in der n-ten Nacht die Insel verlassen.
Ich sehe sie aber am (n + 1)-ten Tag immer noch, denn jeder der anderen Blau¨
augigen erwartete dasselbe von den anderen. Daraus muss ich schließen, dass jeder andere Blau¨
augige auch
n Blau¨
augige sah. Damit ist klar, dass ich blaue Augen habe und ich die Insel in der n¨
achsten
Nacht verlassen muss.
⋄
4
Das Nimmspiel
Zu Beginn des Nimm-Spiels werden beliebig viele H¨
olzer auf beliebig viele
Stapel gelegt. Die beiden Spieler nehmen anschließend abwechselnd beliebig
viele H¨
olzer von einem Stapel. Bei jedem Zug d¨
urfen nur H¨
olzer von einem
Stapel genommen werden! Gewonnen hat, wer das letzte Holz nimmt.4
Gibt es eine Strategie, dieses Spiel immer zu gewinnen?
4
Das Spiel kann auch so abge¨
andert werden, dass derjenige der das letzte Holz nimmt, verliert. Dazu muss
man die Strategie bei den letzten Z¨
ugen ¨
andern.
Prof. Dr. Dieter Kilsch
4.1
Mathematik und Spiele
9
Gewinnsituationen am Ende des Spiels
Eine Position, aus der ich bei gutem weiteren Spielen bei beliebiger Aktion des Gegners gewinne,
nenne ich Gewinnsituation, eine Position, aus der ich bei gutem Spiel meines Gegners keine
Gewinnm¨
oglichkeit habe, heißt Verliersituation.
Ich betrachte zun¨
achst Situationen am Ende des Spiels und behaupte, wenn ich meinem
Gegner die in Abb. 19 dargestellte Gewinnsituation u
¨ berlasse, hat er keine Chance zu gewinnen.
Er hat zwei M¨
oglichkeiten:
(a) Er nimmt ein Holz: Dann nehme ich von dem anderen Stapel ein Holz, so dass die in
Abb. 20 dargestellt Situation entsteht. Auch dies ist eine Gewinnsituation: Mein Gegner
kann nur ein Holz nehmen, f¨
ur mich bleibt das letzte.
(b) Er nimmt zwei H¨
olzer, leer also einen Stapel. Dann leere ich den anderen Stapel und habe
damit das letzte Holz genommen.1
Die in Abb. 19 und 20 dargestellten Positionen sind also Gewinnsituationen.
Abb. 19: Zwei-Zwei-Gewinnsituation
Abb. 20: Eins-Eins Gewinnsituation
Wie sehen Gewinnsituationen mit vielen H¨
olzern aus? Diese Fragen beantworte ich mit Hilfe
der Dualzahlen, vgl. [7].
4.2
Dualzahlen, Gewinn- und Verliersituationen
Wenn wir Zahlen schreiben, verstehen wir sie als Dezimalzahlen. Dies bedeutet, dass jede Stelle
mit einer Potenz von 10 verbunden wird: 243 bedeutet 3·1+4·10+2·100 oder 2·100+4·10+3·1.
Im Dualsystem arbeiten wir nicht mit der Basis 10 (und ihren Potenzen), sondern mit der
Basis 2. Die Zahl 13 im Dualsystem lautet:
1310 = 1 · 8 + 1 · 4 + 0 · 2 + 1 · 1 = 11012
Die tiefgestellte 10 bedeutet, das wir 13 als Dezimalzahl lesen, die tiefgestellte 2 legt die
Ziffernfolge 1101 als Dualzahl fest. Die tiefgestellte 10 wird in der Regel nicht geschrieben,
schließlich ist das Dezimalsystem unser u
¨ bliches Zahlensystem.
Ein m¨
ogliche Anfangssituation eines Nimm-Spiels ist in Abb. 21 dargestellt. Die Stapel enthalten 10 = 10102 , 7 = 1112 und 5 = 1012 H¨
olzer. Diese Ziffernfolgen werden dezimal zu
Dualziffernsummen addiert:
1010
111
101
1222
Ich behaupte:
Satz 4.1 Eine Gewinnsituation liegt genau dann vor, wenn alle Dualziffernsummen gerade sind.
Zun¨
achst beobachten wir, dass die Dualziffernsummen der beiden Gewinnsituationen in Abb. 19
und 20 gleich 11 + 11 = 22 und 1 + 1 = 2 gerade Zahlen sind.
Prof. Dr. Dieter Kilsch
Mathematik und Spiele
Abb. 21: Eine Anfangssituation des Nimm-Spiels
10
Abb. 22: Zu erzeugende Gewinnsituation
¨
Im n¨achsten Schritt muss man sich u
¨ berlegen, dass aus einer Gewinnsituation durch Andern
¨
der Anzahl der H¨
olzer in einem Stapel, also Andern
der Dualzahl eines Stapels eine Verliersituation entstehen muss: Eine Ziffer ¨
andert sich von 0 zu eins oder von 1 zu 0. Damit ¨
andert
sich die Dualziffernsumme um eins nach ober oder unten, so dass aus einer geraden Summe eine
ungerade wird. Damit ist die Gewinnsituation verloren gegangen.
Im letzten Schritt u
¨ berlegen wir uns, dass aus einer Verliersituation immer eine Gewinnsituation gemacht werden kann. Hierzu betrachten wir nochmals Abb. 21. Die ungerade Dualziffernsumme wird durch den ersten Stapel erzeugt. Ohne den ersten Stapel lautet die Dualziffernsumme
111
101
212
¨
Andern
wir den ersten Stapel zu 102 = 2 H¨
olzern, so sind die Dualziffernsummen wieder alle
gerade. Diese Situation ist in Abb. 22 dargestellt.
Dieses Vorgehen kann in jeder Situation angewandt werden und liefert eine Strategie, die
einem Spieler erlaubt, jedes Nimm-Spiel zu gewinnen, wenn er einmal eine Gewinnsituation
erreicht hat.
⋄
5
5.1
Geometrie und Kombinatorik
Zehn Punkte und fu
¨ nf Geraden
Zehn Punkte sollen so in der Ebene gezeichnet werden, das sich f¨
unf Geraden genau in diesen
Punkten schneiden.
Nat¨
urlich kann man durch Ausprobieren zu einer L¨
osung kommen. Es ist aber viel interessanter sich zu u
osungen m¨
oglich sind. Die kleinste Anzahl von Schnittpunkten
¨ berlegen, welche L¨
erh¨
alt man, wenn sich alle Geraden in genau einem Punkt schneiden. Dann haben die f¨
unf
Geraden einen Schnittpunkt und keine zehn.
M¨
oglichst viele Schnittpunkt erh¨
alt man, wenn sich in jedem Punkt nur zwei Geraden schneiden. Das sind bei f¨
unf Geraden genau 4 + 3 + 2 + 1 = 10, also die gesuchte Variante. Die L¨
osung
des R¨
atsels sind Verbindungslinien im Pentagon: Man muss jeden Punkt mit dem u
achsten
¨ bern¨
verbinden.
5.2
Erweiterung des R¨
atsels
Diese Idee kann nat¨
urlich auf weitere Punkteanzahlen u
¨ bertragen werden. Immer schneiden sich
genau zwei Geraden in einem Punkt. Daher sind keine der beteiligten Geraden parallel.
Geraden
3
4
5
6
7
8
Punkte
3
6
10
15
21
28
Figur
Dreieck: Jeden Punkt mit dem n¨
achsten verbinden.
Pentagon: Jeden Punkt mit dem u
achsten verbinden.
¨ bern¨
Septagon: Jeden Punkt mit dem drittn¨
achsten verbinden.
Abbildung
23
24
25
26
27
28
Prof. Dr. Dieter Kilsch
Mathematik und Spiele
11
Allgemein erh¨
alt man eine L¨
osung f¨
ur ungerade Punkteanzahl n und 1+2+. . .+n−1 = n(n−1)
2
Geraden, indem man in einem regelm¨
aßigen n-Eck jeden Punkt mit dem n−1
-n¨
a
chsten
verbindet.
2
Bei gerader Punkteanzahl bietet das regelm¨
aßige n-Eck keine L¨
osung, weil je zwei Kanten
parallel sind. F¨
ur eine L¨
osung muss jeweils eine Kante leicht gedreht werden, so dass die Regelm¨
aßigkeit verloren geht.
Abb. 23: 3 Geraden - 3 Punkte
Abb. 24: 4 Geraden - 6 Punkte
Abb. 25: 5 Geraden - 10 Punkte
Abb. 26: 6 Geraden - 15 Punkte
Abb. 27: 7 Geraden - 21 Punkte
Abb. 28: 8 Geraden - 28 Punkte
Literaturverzeichnis
[1] Beasley, John D.: The Mathematics of Games. Oxford University Press, Oxford, 1991.
[2] Behrends, Ehrhard (Herausgeber): F¨
unf Minuten Mathematik. Vieweg, Wiesbaden,
2006.
[3] Beutelspacher, Albrecht: Das ist o.B.d.A. trivial!“ Vieweg, M¨
unchen, 1991.
”
[4] Beutelspacher, Albrecht: In Mathematik war ich immer schlecht“. Vieweg, Braun”
schweig, 1999.
[5] Beutelspacher, Albrecht: Pasta all’infinito. dtv, M¨
unchen, 2001.
[6] Beutelspacher, Albrecht und Marcus Wagner: Wie man durch eine Postkarte steigt.
Herder, 2010.
¨
[7] Conway, John H.: Uber
Zahlen und Spiele. Vieweg, Braunschweig, 1983.
[8] Enzensberger, Hans Magnus: Der Zahlenteufel. dtv, M¨
unchen, 1999.
[9] Enzensberger, Hans Magnus: Zugbr¨
ucke außer Betrieb. A K Peters, Natick, Mass.,
1999.
[10] Paul, Dietrich: PISA, Bach, Pythagoras. Vieweg, Wiesbaden, 2005.
[11] Seife, Charles: Zwilling der Unendlichkeit: Eine Biographie der Zahl Null. Goldmann,
2002.
[12] Singh, Simon: Fermats letzter Satz. Hanser, M¨
unchen, 1998.
[13] Singh, Simon: Geheime Botschaften. Hanser, M¨
unchen, 2000.
[14] Stewart, Ian: Spiel, Satz und Sieg f¨
ur die Mathematik. Birkh¨
auser, Basel, 1990.

Download Report