Stimmen meine Lösungen zu den folgenden Aufgaben zum Spielbaum?

...komplette Frage anzeigen Bild1 - (Mathematik, Algebra, Spieltheorie) Bild 2 - (Mathematik, Algebra, Spieltheorie)

3 Antworten

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 : )

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 ∈ {1;3;4} mit (modulo 7) n–k ∈ {0; 2}, ansonsten spiele ein beliebiges k ∈ {1;3;4} !

Was möchtest Du wissen?