Nim - Spiel
Einstieg ins Thema
Spiele einige Runden dieses Nim-Spiel gegen Juan und versuche ihn zu besiegen. Die Regeln sind einfach:
- Man darf beliebig viele Perlen nehmen, aber nur aus einer Zeile.
- Wer die letzte Perle nehmen muss, hat verloren.
Leitfragen
- Was ist die Gewinnstrategie gegen Juan?
- Wie gehst du vor, wenn du das Spiel beginnst und «Juan» als Zweites spielt?
- Welche Strategie hast du, wenn der Gegenspieler «Juan» das Spiel beginnt?
- Welche wichtigen Beobachtungen machst du? Welche Erklärungen gibt es dafür?
Auftrag 1
Beantworten Sie die Leitfragen ausführlich!
Weitere Fragen könnten sein:
- Gibt es Situationen, in denen es nicht eindeutig ist, was der nächste eigene Zug ist?
- Wie muss wann entschieden werden?
Auftrag 2
Welche Aussagen sind falsch und warum?
- A1: „Wenn ich am Zug bin, dann nehme ich immer Perlen der untersten Reihe, sodass die Reihen gleichlang werden.“
- A2: „Wenn ich wählen kann, dann soll Juan starten, so gewinnt man fast immer.“
- A3: „Es ist quasi unmöglich, langfristig zu gewinnen. Das Spiel ist nicht fair.“
Was ist Modulo und wie hilft es bei Nim-Spielen?
Modulo ist eine math. Rechenoperation, mit welcher der Rest einer Division zweier Zahlen berechnet werden kann.
Beispiel:
$(17 : 3) = 5$ Rest 2 und dies kann geschrieben werden als $17 mod 3 = 2$
In vielen Varianten des Nim-Spiels ist Modulo ein zentrales Konzept für die Gewinnstrategie:
Pearls before Swine: Hier verwendet man folgende Strategie: wenn die Nim-Summe zu Beginn eines Zuges `0` ist, befindet sich der Spieler in einer verlierenden Position, vorausgesetzt, der andere Spieler spielt optimal.
Wir addieren die einzelnen Spalten der Binärzahlen undn summieren ohne übertrag - das ergebnis ist dann 0 oder 1. Dieses Weglassen des übertrags ist nichts anderes als Modulo 2 zu rechnen. Denn Beispielsweise ist ja 5 mod 2 = 1 und 4 mod 2 = 0.
Da die Modulo-Operation uns dieses Jahr noch mehrfach begegnen wird, gibt es hier einige Übungen dazu. Versuchen Sie auch herauszufinden, wie Ihr Taschenrechner Modulo rechnet.
Auftrag 3
- Denken Sie sich sechs natürliche Zahlen aus und berechne deren Fünferreste. Mindestens zwei davon sind gleich. Warum muss das so sein? Erklären Sie!
- Berechne den Elferrest von
- 200
- 500
- 700
- 1000
- 1'000'000.
- Berechnen Sie die folgenden Modulos:
- $2^2$; $2^4$;$2^8$;$2^{12}$;$2^{100}$ mod 3
- $2^2$; $2^{20}$;$2^{100}$ mod 5
- $3^{20}$ mod 5, was kann man daraus für die Endziffer von 320 schließen?
Lösung: Wie schlägt man Juan?
- Man schreibt die Anzahl der Perlen in jeder Zeile in Binärschreibweise
- Die Summe der Bits in jeder Spalte muss gerade sein, wenn Juan drankommt. Ist dies der Fall, so ist man in einer Gewinnstellung.