Wie kann man diese Aufgabe ohne Spielbaum lösen?

...komplette Frage anzeigen

1 Antwort

Per Induktion mittels Teilspiele … und auch reduzierte Spielbäume. Was meine ich?

Eine Instanz des Spiels sei erstmals bezeichnet durch G(n, I, II) wobei n=Anzahl der übrig gebliebenen Streichhölzer, I = Spieler der dran ist, II = der andere Spieler. Da das Spiel G(n,I,II) endlich und balanciert ist, gibt es einen eindeutigen Gewinner, GEW(n,I,II). Man kann per Induktion feststellen, wie sich diese Funktion entwickelt.


REKURSION: Anfangswerte. Erstmals löst man für n=1; 2; 3.

  • Für n=1 steht im Spiel G(n,I,II) dem Spieler nur die Option {1} zur Verfügung. Spieler I zieht das Streichholz und verliert, also GEW(1,I,II)=II.
  • Für n=2 steht im Spiel G(n,I,II) dem Spieler die Optionen {1;2} zur Verfügung. Spieler I (da er gewinnen möchte) kann 1 ziehen, was das Spiel auf G(1,II,I) reduziert, in dem II verliert und I gewinnt. Deshalb G(2,I,II)=I.
  • Für n=3 steht im Spiel G(n,I,II) dem Spieler die Optionen {1;2;3} zur Verfügung. Spieler I (da er gewinnen möchte) kann 2 ziehen, was das Spiel auf G(1,II,I) reduziert, in dem II verliert und I gewinnt. Deshalb G(3,I,II)=I.


REKURSION: Allgemeine Werte. Jetzt betrachtet man nN mit n > 3 und das Spiel G(n,I,II). Spieler I stehen die Optionen {1;2;3} zur Verfügung. Sollte Spieler I entnehmen:

  • 1 Streichholz, so reduziert sich das Spiel auf G(n–1,II,I), welches gewonnen wird durch GEW(n–1,II,I).
  • 2 Streichholz, so reduziert sich das Spiel auf G(n–2,II,I), welches gewonnen wird durch GEW(n–2,II,I).
  • 3 Streichholz, so reduziert sich das Spiel auf G(n–3,II,I), welches gewonnen wird durch GEW(n–3,II,I).

Da Spieler I zum gewinnen spielt, solange es k ∈ {1;2;3} gibt, mit G(n–k,II,I)=I, so wählt er ein solches k und gewinnt. Wenn für alle k ∈ {1;2;3} G(n–k,II,I)=II, so steht Spieler I kein Zug zur Verfügung, nach welchem er gewinnen kann in G(n,I,II). Deshalb:

(*) G(n,I,II) = I falls ∃k∈{1;2;3}: GEW(n–k,II,I)=I                    = II falls ∀k∈{1;2;3}: GEW(n–k,II,I)=II


Anhand dieser Rekursionsbeobachtungen ist es sofort nahe liegend, mit einer Beweisstrategie anzusetzen, die n-Werte modulo 4 betrachtet. Nach ein wenig Mühe erhält man:

BEHAUPTUNG. Sei n ∈ N mit n > 0. Dann

H(n):    GEW(n,I,II) = I ⟺ (modulo 4) n ∈ {0;2;3}

und entsprechend:

H*(n):   GEW(n,I,II) = II ⟺ n≣1 mod 4.

BEWEIS.

Induktionsanfang. Für n ≤ 3 gilt (wie oben gezeigt wurde) GEW(n,I,II) = I für n ∈ {2;3} und GEW(n,I,II) = II für n=1. Deshalb gilt die Hypothese für diese n-Werte.

Induktionshypothese. Sei n ∈ N mit n > 3. Dann für alle 1 ≤ m < n gilt H(m) (oder äquivalent: es gilt H*(m)).

Induktionsschluss. Im G(n,I,II) sucht, wie oben gezeigt wurde, Spieler I nach einem k ∈ {1;2;3}, 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;2;3}: I verliert G(n–k,II,I)
  • ⟺ ∃k∈{1;2;3}. n–k ≣ 1   mod 4   wegen H*(m) für m<n
  • ⟺ ∃k∈{1;2;3}. n ≣ k+1   mod 4
  • ⟺ (modulo 4) n ∈ {1+1; 2+1; 3+1}
  • ⟺ (modulo 4) n ∈ {2; 3; 4} = {2; 3; 0}.

Somit gilt die Induktiosaussage H(n). ⊣


FOLGERUNG. Für n=11, da n≣3 mod 4 gilt GEW(11,A,B)=A. Das heißt, A verfügt über eine Gewinnstrategie. ⊣

Die Gewinnstrategie für den Gewinner ist dementsprechend wie folgt:

(π) Bei dem Spielstand G(n, ich, der-andere) finde k ∈ {1;2;3} mit n–k ≣ 1 mod 4 und entferne k Streichhölzer. Falls es kein solches k gibt, entferne 1 Streichholz.

1

Müsste heißen:

I gewinnt G(n,I,II)

  • genau dann, wenn ∃k∈{1;2;3}: I gewinnt G(n–k,II,I)
  • ⟺ ∃k∈{1;2;3}: II gewinnt G(n–k,I,II)   …  Schreibweise tauschen
  • ⟺ ∃k∈{1;2;3}: I verliert G(n–k,I,II)
  • ⟺ ∃k∈{1;2;3}: n–k ≣ 1   mod 4   wegen H*(m) für m<n

usw.

1

Was möchtest Du wissen?