Stimmen meine Lösungen zu den folgenden Aufgaben zum Spielbaum?
Hi
Stimmen meine Lösungen zu den folgenden Aufgaben:
Aufgaben;
Aufgabe 1
Betrachten Sie das folgende NIM-Spiel: Auf einem Haufen liegen 8 Streichhölzchen. Ein Zug besteht darin, entweder 1, 3 oder 4 Hölzchen zu entfernen. A beginnt, und verloren hat, wer nicht mehr ziehen kann.
a) Für welchen Spieler gibt es welche Gewinnstrategie?
Aufgabe 2
„Schokoladenspiel“: Zwei Spieler A und B sitzen vor einer Tafel Schokolade mit m Zeilen und Spalten und ziehen abwechselnd, beginnend bei A ( n m n, ∈` ). Das Täfelchen oben links ist irgendwie markiert. Ein Zug besteht aus dem Wegbrechen (und Essen) eines Teils der Schokolade entlang irgendeiner Kante (einige Zeilen oder aber einige Spalten). Dabei darf das markierte Täfelchen oben links nie entfernt werden. Verlierer ist, wer am Ende nur noch das markierte Täfelchen oben links vor sich sieht und folglich nicht mehr ziehen kann. Spielen Sie das Spiel mit der folgenden Schokolade. Bild 1 angehängt.
a) Analysieren Sie das Spiel im Hinblick auf Gewinnstrategien . (Ist damit gemeint das man zeigen soll ob das Spiel eine Gewinnstrategie hat, oder ob man zeigen soll welcher Spieler eine Gewinnstrategie hat?)
Aufgabe 3:¨
Wir verallgemeinern das Spiel aus Aufgabe 2: Zwei Spieler A und B sitzen vor Streichhölzchen ( ) und ziehen abwechselnd, beginnend mit A. Ein Zug besteht aus dem Entfernen von n n∈` x Hölzchen, wobei 1≤ ≤x a . Dabei ist a eine Konstante, nämlich die maximale Anzahl Hölzchen, die in einem Schritt entfernt werden dürfen. Verlierer ist, wer nicht mehr ziehen kann. Analysieren Sie das Spiel im Hinblick auf Gewinnstrategien.
Meine Lösungen:
Aufgabe 1;
a) Für den Spieler B gibt es eine Gewinnstrategie.
Aufgabe 2:
a) Für den Spieler A gibt es eine Gewinnstrategie
Aufgabe 3:¨
Bild 2 angehängt,
thx
3 Antworten
Aufgabe 1. Betrachte das Spiel G(n,I,II) für n≥0: Spieler I wählt k ∈ {1;3;4} und dann tritt G(n–k,II,I) auf. Bezeichne mit GEW(n,I,II) = S, dass Spieler S eine Gewinnstrategie hat. Es gilt GEW(0,I,II) = II.
BEHAUPTUNG. Sei n ∈ N mit n > 0. Dann
H(n): GEW(n,I,II) = I ⟺ (mod 7) n∈{1;3;4;5;6}
und entsprechend:
H*(n): GEW(n,I,II) = II ⟺ (mod 7) n∈{0;2}
BEWEIS. Induktionsanfang. Es gilt per Definition GEW(0,I,II) = II.
Für n=1 darf Spieler I nun 1 spielen, worauf hin G(0,II,I) auftritt, welches per Definition durch I gewonnen wird. Deshalb GEW(1,I,II) = I.
Für n=2 kann Spieler I nur 1 spielen, es tritt G(1,II,I) auf, welches wie oben durch II gewonnen wird, deshalb GEW(2,I,II) = II.
Für n=3 kann Spieler I endlich 3 spielen, wonach G(0,II,I) auf, welches II verliert. Deshalb GEW(3,I,II) = I.
Induktionshypothese. Sei n ∈ N mit n ≥ 4. (Insbesondere können alle Züge 1;3;4 gewählt werden.) Angenommen für alle 1 ≤ m < n gilt H(m) (oder äquivalent: es gilt H*(m)).
Induktionsschluss. Im G(n,I,II) sucht Spieler I nach einem k ∈ {1;3;4}, mit dem GEW(n–k,II,I) = I gilt. Aufgrund der Induktionshypothese gilt dies — man achte auf den Tausch zwischen I und II in dem Teilspiel G(n–k,II,I) —
- genau dann, wenn ∃k∈{1;3;4}: GEW(n–k,II,I) = I
- ⟺ ∃k∈{1;3;4}: GEW(n–k,I,II) = II
- ⟺ ∃k∈{1;3;4}: I verliert G(n–k,I,II)
- ⟺ ∃k∈{1;3;4}: (modulo 7) n–k ∈ {0; 2}
- ⟺ (modulo 7) n ∈ {1+0; 3+0; 4+0; 1+2; 3+2; 4+2}
- ⟺ (modulo 7) n ∈ {1; 3; 4; 3; 5; 6} = {1; 3; 4; 5; 6}
Somit gilt die Induktiosaussage H(n). ⊣
FOLGERUNG. Für n=8 gilt n≣1 (mod 7), also gewinnt A in G(8,A,B). Eine (teilspielperfekte) Gewinnnstrategie ist wie folgt:
(π) Wenn du dran bist und von n > 0 abziehen musst, dann spiele ein k ∈ {1;3;4} mit (modulo 7) n–k ∈ {0; 2}, ansonsten spiele ein beliebiges k ∈ {1;3;4} !
Aufgabe 2.
Ist damit gemeint das man zeigen soll ob das Spiel eine Gewinnstrategie hat, oder ob man zeigen soll welcher Spieler eine Gewinnstrategie hat?)
Satz. Jedes endliche 0-Summe Spiel ist determiniert: es gibt einen Spieler mit Gewinnstrategie. ⊣
Das solltest du dir merken. Daher geht es in dieser Aufgabe um die Frage: Wer hat eine Gewinnstrategie und wie lautet eine solche?
Das Spiel G(m,n,S,S*) für m,n ≥ 1 bezeichnet: Spieler S ist dran und muss etwas von einer mxn Tafel abnehmen. Spieler S wählt dann (j,k) mit 0≤j<m und 0≤k<n und so, dass entweder (j=0 und k>0) oder (j>0 und k=0); dann tritt G(m–j,n–k,S*,S) auf. Dass GEW(m,n,S,S*) = R bezeichnet, dass im Spiel G(m,n,S,S*), Spieler R gewinnt. Es sei definiert dass G(1,1,S,S*) durch S* gewonnen wird.
BEHAUPTUNG. Es sei m, n ≥ 1. Dann gilt
H(m,n): I hat eine GS in G(m,n,I,II) ⟺ m ≠ n
oder äquivalent
H*(m,n): II hat eine GS in G(m,n,I,II) ⟺ m = n.
BEWEIS. Man argumentiert per Induktion über N x N lexikalisch geordnet. Für m=n=1 gilt per Definition GEW(m,n,S,S*)=S* also gilt H*(1,1).
Für Min{m; n} > 1 und G(m,n,S,S*):
- Fall 1: m=n. Sei (j,k) ein möglicher Zug für S. Es tritt G(m–j,n–k,S*,S) ein. Es gilt auch (m–j,n–k) < (m,n) lexikalisch, sodass die Induktionsannahme gilt, nämlich H(m–j,n–k). Da m–j ≠ n–k, hat S* eine Gewinnstrategie in G(m–j,n–k,S*,S). Da dies für alle Züge (j,k) von S in G(m,n,S,S*) der Fall ist, lässt sich eine Gewinnstrategie für S* in G(m,n,S,S*) finden.
- Fall 2: m≠n. Sei k=|m–n|≥1. Falls m<n, kann S den Zug (–,k) spielen, woraufhin G(m,m,S*,S) eintritt, in welchem S eine Gewinnstrategie hat (per Induktion). Falls n<m, kann S den Zug (k,–) spielen, woraufhin G(n,n,S*,S) eintritt, in welchem S eine Gewinnstrategie hat (per Induktion). Also lässt sich eine Gewinnstrategie für S in G(m,n,S,S*) finden.
Daraus ergibt sich die Induktionshypothese H(m,n). ⊣
FOLGERUNG.
Eine Gewinnstrategie des Spiels ist folgende:
(⃞) Spiele so, dass, wenn möglich, du die Tafel quadratisch hinterlässt.
M. a. W. „Quadratisch. Praktisch. Gut.“ Nehme Milka und gebe Rittersport zurück : )
http://www.educ.ethz.ch/unt/um/mathe/anw/spiel/Spiele1.doc
Ab 4. wird es interessant...