Zwei Spieler, Pasha und Vova, spielen das nächste Spiel. Vor den Spielern liegt ein Steinhaufen. Die Spieler wechseln sich ab, Pascha macht den ersten Zug. In einem Zug kann ein Spieler 1 Stein oder 10 Steine zum Stapel hinzufügen. Wenn Sie beispielsweise einen Stapel mit 7 Steinen haben, können Sie in einem Zug einen Stapel mit 8 oder 17 Steinen erhalten. Jeder Spieler hat eine unbegrenzte Anzahl an Steinen, um Züge auszuführen. Das Spiel endet, wenn die Anzahl der Steine im Stapel mindestens 31 beträgt. Sieger ist der Spieler, der den letzten Zug ausgeführt hat, d. h. derjenige, der als erster einen Stapel mit 31 oder mehr Steinen erhält.
Im ersten Moment befanden sich S Steine im Stapel, 1 ≤ S ≤ 30.
Lösung.
1. a) Pascha kann gewinnen, wenn S = 21, ..., 30. Bei kleineren Werten von S ist es unmöglich, in einem Zug einen Stapel mit mehr als 30 Steinen zu bekommen. Pascha muss die Anzahl der Steine nur um 10 erhöhen. Für S 1. b) Vova kann im ersten Zug gewinnen (egal wie Pascha spielt), wenn zunächst S = 20 Steine auf dem Haufen sind. Nach Paschas erstem Zug befinden sich dann 21 oder 30 Steine auf dem Stapel. In beiden Fällen erhöht Wanja die Anzahl der Steine um 10 und gewinnt in einem Zug.
2. Mögliche Werte von S: 10, 19. In diesen Fällen kann Pascha offensichtlich nicht mit seinem ersten Zug gewinnen. Allerdings kann er einen Stapel mit 20 Steinen erhalten (bei S=10 erhöht er die Anzahl der Steine um 10; bei S=19 fügt er 1 Stein hinzu). Diese Position wird in Absatz 1 b erörtert. Darin kann der Spieler, der ziehen wird (das ist jetzt Vova), nicht gewinnen, aber sein Gegner (also Pascha) wird beim nächsten Zug gewinnen.
3. Möglicher Wert von S: 18. Nach Paschas erstem Zug befinden sich 19 oder 28 Steine auf dem Stapel. Wenn der Stapel 28 Steine enthält, erhöht Vova die Anzahl der Steine um 10 und Sie spielen mit Ihrem ersten Zug. Die Situation, in der sich 19 Steine auf einem Haufen befinden, wird in Absatz 2 behandelt. In dieser Situation gewinnt der Spieler, der ziehen wird (das ist jetzt Wowa), mit seinem zweiten Zug.
Gast 26.05.2014 12:31
Punkt 3. Aber was ist mit der Situation, wenn zunächst 9 Steine im Stapel liegen? Nach Paschas Zug werden die Steine entweder 10 oder 19, Vasya kommt bis 20 und weiter gemäß Punkt 1.b.
Konstantin Lawrow
Ja, 9 ist auch die richtige Antwort. Es reicht aus, mindestens einen korrekten Wert anzugeben.
Zwei Spieler, Pasha und Vova, spielen das nächste Spiel. Vor den Spielern liegt ein Steinhaufen. Die Spieler wechseln sich ab, Pascha macht den ersten Zug. In einem Spielzug kann ein Spieler 1 Stein oder 10 Steine zum Stapel hinzufügen. Wenn Sie beispielsweise einen Stapel mit 7 Steinen haben, können Sie in einem Zug einen Stapel mit 8 oder 17 Steinen erhalten. Jeder Spieler hat eine unbegrenzte Anzahl an Steinen, um Züge auszuführen. Das Spiel endet, wenn die Anzahl der Steine im Stapel mindestens 41 beträgt. Sieger ist der Spieler, der den letzten Zug ausgeführt hat, d. h. derjenige, der als erster einen Stapel mit 41 oder mehr Steinen erhält.
Im ersten Moment befanden sich S Steine im Stapel, 1 ≤ S ≤ 40.
Wir sagen, dass ein Spieler eine Gewinnstrategie hat, wenn er mit allen Zügen des Gegners gewinnen kann. Die Strategie eines Spielers zu beschreiben bedeutet, zu beschreiben, welchen Zug er in jeder Situation machen sollte, in die er mit anderen Spielzügen als der Gegner geraten könnte.
Führen Sie die folgenden Aufgaben aus. Begründen Sie in jedem Fall Ihre Antwort.
1. a) Listen Sie alle Werte der Zahl S auf, für die Pascha in einem Zug gewinnen kann. Begründen Sie, dass alle erforderlichen Werte von S gefunden wurden, und geben Sie die Gewinnzüge an.
b) Geben Sie einen Wert von S an, so dass Pascha nicht in einem Zug gewinnen kann, Vova jedoch bei jedem Zug von Pascha mit seinem ersten Zug gewinnen kann. Beschreiben Sie Vovas Erfolgsstrategie.
2. Geben Sie zwei Werte von S an, für die Pascha eine Gewinnstrategie hat, und Pascha kann nicht in einem Zug gewinnen, kann aber mit seinem zweiten Zug gewinnen, unabhängig davon, wie Vova sich bewegt. Beschreiben Sie für die gegebenen Werte von S die Gewinnstrategie von Pascha.
3. Geben Sie den Wert von S an, bei dem Vova über eine Gewinnstrategie verfügt, die es ihm ermöglicht, in jeder Pascha-Partie mit dem ersten oder zweiten Zug zu gewinnen, aber Vova nicht über eine Strategie verfügt, die es ihm ermöglicht, mit dem ersten Zug zu gewinnen. Beschreiben Sie für den angegebenen Wert von S die Gewinnstrategie von Vova. Erstellen Sie mit dieser Gewinnstrategie von Vova einen Baum aller möglichen Spiele (in Form eines Bildes oder einer Tabelle). An den Rändern des Baumes wird angezeigt, wer den Zug ausführt, und an den Knotenpunkten wird die Anzahl der Steine im Stapel angezeigt.
Lösung.
1. a) Pascha kann gewinnen, wenn S = 31, ..., 40. Bei kleineren Werten von S ist es unmöglich, in einem Zug einen Stapel mit mehr als 40 Steinen zu bekommen. Pascha muss die Anzahl der Steine nur um 10 erhöhen. Mit S b) kann Vova im ersten Zug gewinnen (egal wie Pascha spielt), wenn der Stapel zunächst S = 30 Steine enthält. Nach Paschas erstem Zug befinden sich dann 31 oder 40 Steine auf dem Stapel. In beiden Fällen erhöht Wanja die Anzahl der Steine um 10 und gewinnt in einem Zug.
2. Mögliche Werte von S: 20, 29. In diesen Fällen kann Pascha offensichtlich nicht mit seinem ersten Zug gewinnen. Allerdings kann er einen Stapel mit 30 Steinen erhalten (für S = 20 erhöht er die Anzahl der Steine um 10; für S = 29 fügt er 1 Stein hinzu). Diese Position wird in Absatz 1. b) erörtert. Darin kann der Spieler, der ziehen wird (das ist jetzt Vova), nicht gewinnen, aber sein Gegner (also Pascha) wird beim nächsten Zug gewinnen.
3. Möglicher Wert von S: 28. Nach Paschas erstem Zug befinden sich 29 oder 38 Steine auf dem Stapel. Wenn der Stapel 38 Steine erreicht, erhöht Vova die Anzahl der Steine um 10 und Sie spielen mit Ihrem ersten Zug. Die Situation, in der sich 29 Steine auf einem Haufen befinden, wird in Absatz 2 behandelt. In dieser Situation gewinnt der Spieler, der ziehen wird (das ist jetzt Wowa), mit seinem zweiten Zug.
Die Tabelle zeigt den Baum möglicher Spiele für die oben beschriebene Strategie von Vova. Die Endpositionen (Vova gewinnt darin) sind unterstrichen. In der Abbildung ist derselbe Baum grafisch dargestellt (beide Arten der Baumdarstellung sind akzeptabel).
Zwei Spieler, Petya und Vanya, spielen das nächste Spiel. Vor ihnen liegen zwei Steinhaufen, von denen der erste 2 und der zweite 3 Steine enthält. Jedes Spiel hat viele Steine. Die Spieler wechseln sich ab, wobei Petja den ersten Zug macht. Der Zug besteht darin, dass der Spieler entweder die Anzahl der Steine von einem Stapel entfernt oder 4 Steine zu einem Stapel hinzufügt. Das Spiel endet in dem Moment, in dem die Gesamtzahl der Steine in zwei Stapeln mindestens 31 beträgt. Wenn in dem Moment, in dem das Spiel endet, die Gesamtzahl der Steine in zwei Stapeln mindestens 40 beträgt, dann hat Petja gewonnen, andernfalls hat Wanja gewonnen. Gegen wen spielt man, wenn beide Spieler fehlerfrei spielen? Was sollte der erste Zug Ihres Spiels sein? Erklären Sie die Antwort.
Lösung.
Wanja gewinnt.
Betrachten Sie zum Beweis einen unvollständigen Spielbaum in Form einer Tabelle, in der jede Zelle durch ein Komma getrennte Zahlenpaare enthält. Diese Zahlen entsprechen der Anzahl der Steine in jeder Spielphase im ersten bzw. zweiten Stapel.
Die Tabelle enthält alles Möglichkeiten die Züge des Startspielers. Es zeigt, dass für jeden Zug des ersten Spielers der zweite Spieler einen Zug hat, der zum Sieg führt.
Zwei Spieler, Petya und Vasya, spielen das folgende Spiel. Vor ihnen liegen zwei Steinhaufen, von denen der erste 2 und der zweite 1 Stein enthält. Jeder Spieler hat eine unbegrenzte Anzahl an Steinen. Die Spieler wechseln sich ab, Petja beginnt. Der Zug besteht darin, dass der Spieler entweder die Anzahl der Steine in einem Stapel um das Dreifache erhöht oder 3 Steine zu einem Stapel hinzufügt. Es gewinnt der Spieler, nach dessen Zug sich mindestens 24 Steine auf einem der Stapel befinden. Wer gewinnt, wenn er fehlerfrei spielt? Was sollte der erste Zug des siegreichen Spielers sein?
Rechtfertige deine Antwort.
Lösung.
Petya gewinnt; mit seinem ersten Zug muss er die Anzahl der Steine im zweiten Stapel um das Dreifache erhöhen. Betrachten Sie zum Beweis einen unvollständigen Spielbaum in Form einer Tabelle, in der jede Zelle durch ein Komma getrennte Zahlenpaare enthält. Diese Zahlen entsprechen der Anzahl der Steine in jeder Spielphase im ersten bzw. zweiten Stapel.
Die Tabelle enthält alle möglichen Optionen für Vasyas Züge. Es zeigt, dass Petya bei jeder Antwort einen Zug hat, der zum Sieg führt.
Zwei Spieler, Petya und Vanya, spielen das folgende Spiel. Vor den Spielern liegt ein Steinhaufen. Die Spieler wechseln sich ab, Petja macht den ersten Zug. In einer Runde kann ein Spieler einen Stein zum Stapel hinzufügen oder die Anzahl der Steine im Stapel um das Fünffache erhöhen. Wenn Sie beispielsweise einen Stapel mit 10 Steinen haben, können Sie in einem Zug einen Stapel mit 11 oder 50 Steinen erhalten. Jeder Spieler hat eine unbegrenzte Anzahl an Steinen, um Züge auszuführen.
Das Spiel endet, sobald die Anzahl der Steine im Stapel mehr als 100 beträgt. Sieger ist der Spieler, der den letzten Zug ausgeführt hat, d. h. derjenige, der als erster einen Stapel mit 101 oder mehr Steinen erhält.
Im ersten Moment befanden sich S Steine im Stapel, 1 ≤ S ≤ 100.
Von einer Gewinnstrategie spricht man, wenn ein Spieler mit jedem Zug seines Gegners gewinnen kann. Die Strategie eines Spielers zu beschreiben bedeutet, zu beschreiben, welchen Zug er in jeder Situation machen sollte, in die er mit anderen Spielzügen als der Gegner geraten könnte.
Führen Sie die folgenden Aufgaben aus. Begründen Sie in jedem Fall Ihre Antwort.
1. a) Für welche Werte der Zahl S kann Petya mit seinem ersten Zug gewinnen? Listen Sie alle diese Werte und Petits Siegerzug auf.
b) Geben Sie einen Wert für S an, sodass Petya nicht in einem Zug gewinnen kann, Wanja jedoch bei jedem Zug, den Petya macht, mit seinem ersten Zug gewinnen kann. Beschreiben Sie Vanyas Erfolgsstrategie.
2. Geben Sie zwei Werte von S an, für die Petya eine Gewinnstrategie hat, und Petya kann mit seinem ersten Zug nicht gewinnen, aber Petya kann mit seinem zweiten Zug gewinnen, unabhängig davon, wie Vanya sich bewegt. Beschreiben Sie für die gegebenen Werte von S Petits Gewinnstrategie.
3. Geben Sie einen Wert von S an, sodass Vanya eine Gewinnstrategie hat, die es ihm ermöglicht, in jeder Petya-Partie mit dem ersten oder zweiten Zug zu gewinnen, und Vanya gleichzeitig keine Strategie hat, die es ihm ermöglicht, mit dem ersten zu gewinnen bewegen.
Beschreiben Sie für den gegebenen Wert von S Vanyas Gewinnstrategie. Erstellen Sie mit Vanyas Gewinnstrategie einen Baum aller möglichen Spiele. Präsentieren Sie es in Form eines Bildes oder einer Tabelle. Geben Sie für jede Kante des Baums an, wer den Zug ausführt. Geben Sie für jeden Knoten die Anzahl der Steine an der Position an.
Lösung.
1. a) Petya kann gewinnen, wenn S = 21, ..., 100. Bei kleineren Werten von S ist es unmöglich, in einem Zug einen Stapel mit mehr als 100 Steinen zu bekommen. Für Petya reicht es, die Anzahl der Steine um das Fünffache zu erhöhen. Bei S 1. b) Wanja kann mit dem ersten Zug gewinnen (egal wie Petja spielt), wenn zunächst S = 20 Steine auf dem Haufen sind. Nach Petjas erstem Zug sind dann 21 Steine oder 100 Steine auf dem Haufen. In beiden Fällen erhöht Wanja die Anzahl der Steine um das Fünffache und gewinnt in einem Zug.
2. Mögliche Werte von S: 4, 19. In diesen Fällen kann Petya offensichtlich nicht mit seinem ersten Zug gewinnen. Allerdings kann er einen Stapel von 20 Steinen erhalten (bei S = 4 erhöht er die Anzahl der Steine um das Fünffache; bei S = 19 fügt er 1 Stein hinzu). Diese Position wird in Absatz 1 b) erörtert. Darin kann der Spieler, der ziehen wird (jetzt Wanja), nicht gewinnen, aber sein Gegner (also Petja) wird bei seinem nächsten Zug gewinnen.
3. Möglicher Wert von S: 18. Nach Petyas erstem Zug befinden sich 19 oder 90 Steine auf dem Stapel. Befinden sich 90 Steine im Stapel, erhöht Wanja die Anzahl der Steine um das Fünffache und gewinnt mit seinem ersten Zug. Die Situation, in der sich 19 Steine auf dem Haufen befinden, wird in Absatz 2 behandelt. In dieser Situation gewinnt der Spieler, der ziehen wird (das ist jetzt Wanja), mit seinem zweiten Zug.
Die Tabelle zeigt den Baum möglicher Spiele für Vanyas oben beschriebene Strategie. Die Endpositionen (Wanja gewinnt darin) sind unterstrichen. In der Abbildung ist derselbe Baum grafisch dargestellt (beide Darstellungsmethoden sind akzeptabel).
Machen Sie Tests zu diesen Aufgaben
Der schwierigste Teil dieses Problems besteht darin, die Lösung richtig und logisch zu schreiben.
Beginnen wir also damit, den Zustand zu verstehen.
- Wir haben zwei Steinhaufen und zwei Spieler: den ersten (Petya) und den zweiten (Vanya).
- Die Spieler wechseln sich ab.
- Während eines Zuges können Sie entweder einen Stein zu einem der Stapel hinzufügen oder die Anzahl der Steine im Stapel verdoppeln.
- Sobald 73 oder mehr Steine auf dem Stapel liegen, endet das Spiel.
- Der Letzte, der geht, gewinnt.
Wichtige Notizen
- In einigen Aufgaben werden wir einen Baum von Parteien erstellen. Dazu sind wir gemäß der Bedingung nur in Aufgabe 3 verpflichtet. In Aufgabe 2 sind wir nicht verpflichtet Baue einen Partybaum.
- Bei jeder Aufgabe reicht es nicht aus, einfach zu sagen, wer die Gewinnerstrategie hat. Sie müssen es auch beschreiben und die mögliche Anzahl der Schritte angeben, die erforderlich sein werden, um zu gewinnen.
- Es reicht nicht aus, eine Strategie als erfolgreich zu bezeichnen. Müssen beweisen dass es zum Sieg führt. Selbst offensichtliche Aussagen erfordern Beweise.
Übung 1.
Betrachten wir nun Aufgabe 1. Es gibt (6, 33) Steine in Stapeln (erster Teil von Aufgabe 1) und (8, 32) Steine (zweiter Teil von Aufgabe 1). Wir müssen feststellen, welcher Spieler eine Gewinnstrategie hat. Mit anderen Worten: Welcher Spieler wird bei richtiger Spielweise definitiv gewinnen, unabhängig von den Aktionen des Gegners?
Hier und weiter werden wir die Lösung in zwei Teile aufteilen. Zuerst gibt es eine vorläufige Erklärung (es ist nicht erforderlich, diese im Einheitlichen Staatsexamen zu verfassen) und dann eine „formelle Entscheidung“, d. h. was auf dem Einheitlichen Staatsexamen-Formular selbst geschrieben werden muss.
Diskussion.
Stellen wir uns vor: Der erste Spieler kann offensichtlich nicht in einem Zug gewinnen, denn egal, was er tut, die Gesamtsumme wird nicht 73 sein. Die „größte“ Aktion, die er machen kann, besteht darin, die Anzahl der Steine im zweiten Stapel zu verdoppeln, sodass sie 66 sind. Aber (6, 66) sind 72 Steine, nicht 73. Das bedeutet, dass der erste Stein eindeutig in einem Zug gewonnen werden kann kann nicht. Der zweite ist jedoch durchaus leistungsfähig. Die erste kann möglicherweise vier Aktionen ausführen: 1 zum ersten Stapel hinzufügen, die Anzahl der Steine im ersten Stapel verdoppeln, 1 zum zweiten Stapel hinzufügen, die Anzahl der Steine im zweiten Stapel verdoppeln. Mal sehen, wohin das führt:
- (6.33) -> (7.33). In diesem Fall kann der zweite Spieler die Anzahl der Steine im zweiten Stapel verdoppeln. Wir erhalten (7, 66). Gesamt - 73. Der Zweite gewinnt also.
- (6.33) -> (12, 33). In diesem Fall kann der zweite Spieler die Anzahl der Steine im zweiten Stapel verdoppeln. Wir erhalten (12, 66). Gesamt - 78. Der Zweite gewinnt also.
- (6.33) -> (6.34). In diesem Fall kann der zweite Spieler die Anzahl der Steine im zweiten Stapel verdoppeln. Wir erhalten (6, 68). Gesamt - 74. Der Zweite gewinnt also.
- (6.33) -> (6.66). In diesem Fall kann der zweite Spieler die Anzahl der Steine im zweiten Stapel verdoppeln. Wir erhalten (6, 132). Die Gesamtzahl beträgt 138. Das bedeutet, dass der Zweite gewinnt.
Gesamt: Egal wie sich der erste Spieler verhält, der zweite gewinnt in einem Zug.
Löst sich ähnlich mit (8.32).
Formale Lösung für Aufgabe 1.
Der zweite Spieler hat eine Gewinnstrategie. Lassen Sie es uns beweisen und diese Strategie zeigen. Dazu erstellen wir für jede der Ausgangspositionen einen Partybaum. Im Spielbaum geben wir den Zustand beider Stapel im Format (a,b) an, wobei a die Anzahl der Steine im ersten Stapel und b die Anzahl der Steine im zweiten Stapel ist. Wenn der erste Spieler an der Reihe ist, werden wir vier mögliche Optionen für sein Verhalten in Betracht ziehen: 1 zum ersten Stapel hinzufügen, die Anzahl der Steine im ersten Stapel verdoppeln, 1 zum zweiten Stapel hinzufügen, die Anzahl der Steine im zweiten Stapel verdoppeln. Für den zweiten Spieler geben wir jeweils einen Zug an, der zu einem Sieg führt. Wir zeigen Züge in Form von Pfeilen an, neben die wir I für den ersten Zug und II für den zweiten Zug schreiben.
Spielbaum für die Startposition (6, 33).
Spielbaum für die Startposition (8, 32).
Laut Spielbaum hat der Zweite unabhängig von den Zügen des Ersten immer eine Gewinnstrategie, die es ihm ermöglicht, in einem Zug zu gewinnen, wie in den Bäumen beschrieben (die Summen nach Wanjas Zügen betragen von links nach rechts 73, 80). , 74 bzw. 136). Darüber hinaus kann laut Spielbaum der zweite Spieler in genau einem Zug gewinnen.
Aufgabe 2
Formale Lösung
Betrachten Sie die Ausgangsposition (6,32). Beachten Sie, dass es in der Nähe von (6,33) aus Aufgabe 1 liegt. In Aufgabe 1 haben wir herausgefunden, dass in Position (6, 33) der Zweite gewinnt, und zwar in einem Zug. Diese Bedingung lässt sich umformulieren: In Stellung (6.33) steht derjenige, der in einem Zug gewinnt Nicht geht (das heißt, geht als Zweiter). Oder mit anderen Worten: Wer zieht, verliert in einem Zug.
In Stellung (6.32) gewinnt der Erste in zwei Zügen. Lass es uns beweisen. Bei seinem ersten Zug fügt Petya +1 zum zweiten Stapel hinzu. Damit erhält man die Position (6.33). Wie wir zuvor herausgefunden haben, verliert in Position (6,33) derjenige, der sich bewegt. In unserem Fall wird es Vanyas Zug sein. Daher wird Vanya in einem Zug verlieren. In diesem Fall muss Petja insgesamt zwei Züge machen: den ersten (1 Stein zum zweiten Stapel hinzufügen) + den zweiten Zug gemäß dem Gruppenbaum in Aufgabe 1, wobei er nach Wanjas Strategie handelt.
Ebenso in Position (7, 32). Mit seinem ersten Zug fügt Petya +1 Stein zum ersten Stapel hinzu und erhält Position (8, 32). In dieser Position verliert nach derselben Argumentation derjenige, der sich bewegt. Es wird Vanyas Zug sein, also wird Vanya verlieren. Petyas Gewinnstrategie ist wie folgt: Petya fügt +1 Stein zum ersten Stapel hinzu und folgt dann Vanyas Strategie aus Aufgabe 1.
Ebenso in Position (8, 31). Mit seinem ersten Zug fügt Petya +1 Stein zum zweiten Stapel hinzu und erhält Position (8, 32). In dieser Position verliert nach derselben Argumentation derjenige, der sich bewegt. Es wird Vanyas Zug sein, also wird Vanya verlieren. Petyas Gewinnstrategie ist wie folgt: Petya fügt +1 Stein zum zweiten Stapel hinzu und folgt dann Vanyas Strategie aus Aufgabe 1.
Aufgabe 3
Diskussion
Beachten Sie, dass es aus Situation (7, 31) sehr leicht ist, entweder in Situationen (8, 31) und (7, 32) zu geraten, in denen gemäß der vorherigen Aufgabe derjenige gewinnt, der sich bewegt, oder in Situation ( 14, 31) und (7, 62), bei dem derjenige, der zieht, in einem Zug gewinnen kann, indem er die Anzahl der Steine im zweiten Stapel verdoppelt. Es stellt sich also heraus, dass Vanya eine Erfolgsstrategie haben muss. Darüber hinaus kann er sowohl in 2 Zügen (die ersten beiden Fälle) als auch in einem Zug (die zweiten beiden Fälle) gewinnen.
Formale Lösung
In der Ausgangsstellung (7, 31) gewinnt Wanja in ein oder zwei Zügen. Lass es uns beweisen. Dazu erstellen wir einen Baum aller Parteien.
Baum aller Spiele für die Startposition (7, 31).
Gemäß dem Baum aller Spiele gewinnt Wanja entweder in einem Zug (wenn Petja die Anzahl der Steine im ersten oder zweiten Stapel verdoppelt hat) oder in zwei Zügen (wenn Petja die Anzahl der Steine im ersten oder zweiten Stapel um 1 erhöht hat). .
Somit hat Wanja in der Ausgangsstellung (7, 31) eine Gewinnstrategie und Wanja wird in ein oder zwei Zügen gewinnen.
Jewgeni Smirnow
IT-Experte, Informatiklehrer
Die Lektion befasst sich mit der Analyse der Aufgabe 26 des Einheitlichen Staatsexamens in Informatik: Es wird eine ausführliche Erklärung und Lösung der Aufgabe 2017 gegeben
Die 26. Aufgabe – „Spieltheorie, Suche nach einer Gewinnstrategie“ – wird als Aufgabe bezeichnet hohes Level Komplexität, Bearbeitungszeit – ca. 30 Minuten, maximale Punktzahl – 3
* Einige Bilder und Seitenbeispiele stammen aus den Präsentationsmaterialien von K. Polyakov
Spieltheorie. Eine erfolgreiche Strategie finden
Um Aufgabe 26 zu lösen, müssen Sie sich die folgenden Themen und Konzepte merken:
- Um in einfachen Spielen eine Gewinnstrategie zu finden, reicht es aus, die Methode der Aufzählung aller möglichen Optionen für die Züge der Spieler zu verwenden;
- Zur Lösung von Problemen werden hierfür am häufigsten 26 Aufgaben verwendet Baumbauweise;
- wenn von jedem Knoten des Baumes zwei Zweige ausgehen, d.h. mögliche Optionen für Bewegungen, dann heißt ein solcher Baum binär(Wenn es von jeder Position aus drei Fortsetzungsmöglichkeiten gibt, ist der Baum ternär).
- alle Positionen in einfachen Spielen werden in Gewinn und Niederlage unterteilt;
- Siegerposition– Dies ist eine Position, in der der Spieler, der den ersten Zug macht, unabhängig von der Handlung des Gegners definitiv gewinnt, es sei denn, er macht einen Fehler. Gleichzeitig sagen sie, dass dieser Spieler hat Gewinnstrategie– ein Algorithmus zur Wahl des nächsten Zuges, der ihm den Sieg ermöglicht;
- wenn der Spieler, der den ersten Zug macht, dabei ist Position verlieren, dann wird er definitiv verlieren, es sei denn, sein Gegner macht einen Fehler; in diesem Fall heißt es, dass dieser Spieler hat keine Erfolgsstrategie; Daher besteht die allgemeine Strategie des Spiels darin, mit Ihrem Zug eine Verlustposition für Ihren Gegner zu schaffen;
- Gewinn- und Verliererpositionen werden wie folgt charakterisiert:
- eine Stellung, von der aus alle möglichen Züge zu Gewinnstellungen führen – verlieren;
- eine Stellung, aus der mindestens einer der folgenden möglichen Züge zu einer Verluststellung führt - gewinnen, und die Strategie des Spielers besteht darin das Spiel in ein verlorenes Spiel verwandeln(für Gegner) Position.
- Um festzustellen, welcher Spieler mit einem strategisch korrekten Spiel gewinnt, ist es notwendig, die Fragen zu beantworten:
- Kann jeder Spieler gewinnen, unabhängig von den Zügen der anderen Spieler?
- Was muss ein Spieler mit einer Gewinnstrategie bei seinem ersten Zug tun, damit er gewinnen kann, unabhängig von den Aktionen der Spielerzüge?
Erfolgreiche Strategie
Positionen gewinnen und verlieren
Wer gewinnt mit einem strategisch richtigen Spiel?
Schauen wir uns ein Beispiel an:
Ein Spiel: es gibt 5 Streichhölzer in einem Stapel; gespielt von zwei Spielern, die abwechselnd Streichhölzer vom Stapel nehmen; Bedingung: In einem Zug können Sie 1 oder 2 Streichhölzer entfernen; Der Gewinner ist derjenige, der 1 Streichholz im Stapel liegen lässt
Lösung:
Antwort: mit dem richtigen Spiel (Spielstrategie) gewinnt der erste Spieler; Dazu muss er mit seinem ersten Zug lediglich ein Streichholz entfernen.
Lösung von 26 Aufgaben des Einheitlichen Staatsexamens in Informatik
Analyse der Aufgabe 26 des Einheitlichen Staatsexamens in Informatik 2017 FIPI Option 5 (Krylov S.S., Churkina T.E.):
Zwei Spieler, Pasha und Valya, spielen das folgende Spiel. Vor den Spielern liegt ein Steinhaufen. Die Spieler wechseln sich ab Pascha macht den ersten Schritt eins zweimal. Wenn Sie beispielsweise einen Stapel mit 7 Steinen haben, können Sie in einem Zug einen Stapel mit 14 oder 8 Steinen erhalten. Jeder Spieler hat eine unbegrenzte Anzahl an Steinen für einen Zug.
Das Spiel endet, wenn die Anzahl der Steine im Stapel mindestens erreicht ist 28 . Wenn gleichzeitig nicht mehr als vorhanden sind 44 Steine, der Gewinner ist der Spieler, der den letzten Zug gemacht hat. IN ansonsten sein Gegner wird zum Sieger. Wenn sich zum Beispiel 23 Steine auf dem Stapel befinden und Pascha die Anzahl der Steine auf dem Stapel verdoppelt, endet das Spiel und Valya ist der Gewinner. Im ersten Moment befanden sich S-Steine im Stapel, 1≤ S ≤ 27.
Übung 1
a) Bei welchen Werten der Zahl S Kann Pascha in einem Zug gewinnen? Listen Sie alle diese Werte und die entsprechenden Bewegungen von Pascha auf.
b) Welcher Spieler hat wann eine Gewinnstrategie? S = 26, 25, 24? Beschreiben Sie Erfolgsstrategien für diese Fälle.
Aufgabe 2
S = 13, 12? Beschreiben Sie relevante Gewinnstrategien.
Aufgabe 3
Welcher Spieler hat wann eine Gewinnstrategie? S=11? Konstruieren Sie einen Baum aller mit dieser Gewinnstrategie möglichen Spiele (in Form eines Bildes oder einer Tabelle). Geben Sie an den Rändern des Baumes an, wer den Zug ausführt. in Knoten – die Anzahl der Steine in der Position.
✍ Lösung:
Eine ausführliche Erläuterung der Aufgabe 26 des Einheitlichen Staatsexamens finden Sie im Video:
Analyse der Aufgabe 26 des Einheitlichen Staatsexamens Informatik 2017 (eine der Optionen laut Absolvent):
Petja und Wanja spielen ein Spiel: Es gibt eine Reihe von Wörtern, man muss die Buchstaben dieser Wörter konsequent benennen. Der Gewinner ist der Spieler, der den letzten Buchstaben eines beliebigen Wortes aus der Menge nennt. Petja geht zuerst.
Es gibt zum Beispiel eine Reihe von Wörtern (Wolf, Informatik, Gruselig); Für eine bestimmte Wortgruppe kann Petya mit seinem ersten Zug den Buchstaben benennen IN, UND oder MIT. Wenn Petya den Brief wählt IN, dann wird Vanya gewinnen (nächste Züge: Petya - IN, Vania - UM, Peter - L, Vania - ZU).
Übung 1
A) Gegeben sind 2 Wörter (Buchstabensatz) ( IKLMNIKLMNH, NMLKINMLKI). Bestimmen Sie eine Erfolgsstrategie.
B) Gegeben sind 2 Wörter ( TRITRITRI...DREI, RITARITARITARITARITA...RITA). Im ersten Wort 99 Buchstaben, im zweiten 164 . Bestimmen Sie eine Erfolgsstrategie.
Aufgabe 2
Es ist notwendig, zwei Buchstaben aus dem Artikelset auszutauschen 1A im Wort mit der kürzesten Länge, so dass die Gewinnstrategie der andere Spieler ist. Erklären Sie eine erfolgreiche Strategie.
Aufgabe 3
Gegeben eine Reihe von Wörtern ( Krähe, Wolf, Welle, Derivat, Prochor, Hirse). Welcher Spieler hat eine Gewinnstrategie? Begründen Sie Ihre Antwort und schreiben Sie einen Baum aller möglichen Spiele für eine Gewinnstrategie.
✍ Lösung:
* Für Vanya werden nur Strategiezüge angezeigt
**Roter Kreis bedeutet Sieg
Weitere Informationen zur Lösung des Wortproblems finden Sie im Video-Tutorial:
Lösung 26. Demoversion des Unified State Exam 2018 Informatik:
Zwei Spieler, Petya und Vanya, spielen das folgende Spiel. Vor den Spielern liegt ein Steinhaufen. Die Spieler wechseln sich ab, Petja macht den ersten Zug. In einem Zug kann ein Spieler den Stapel auffüllen eins Stein oder erhöhen Sie die Anzahl der Steine im Stapel zweimal. Wenn Sie beispielsweise einen Stapel mit 15 Steinen haben, können Sie in einem Zug einen Stapel mit 16 oder 30 Steinen erhalten. Jeder Spieler hat eine unbegrenzte Anzahl an Steinen, um Züge auszuführen.
Das Spiel endet, wenn die Anzahl der Steine im Stapel erreicht ist mindestens 29. Gewinner ist der Spieler, der den letzten Zug gemacht hat, also als erster einen Stapel mit 29 oder mehr Steinen erhält. Im ersten Moment befanden sich S-Steine im Stapel, 1 ≤ S ≤ 28.
Wir sagen, dass ein Spieler eine Gewinnstrategie hat, wenn er mit allen Zügen des Gegners gewinnen kann. Die Strategie eines Spielers zu beschreiben bedeutet, zu beschreiben, welchen Zug er in jeder Situation machen sollte, in die er mit anderen Spielzügen als der Gegner geraten könnte. Beschreibung der Gewinnstrategie TU es nicht umfassen Züge eines Spielers, der nach dieser Strategie spielt, die für ihn nicht unbedingt gewinnbringend sind, d. h. unabhängig vom Spiel des Gegners nicht gewinnt.
Übung 1
A) Geben Sie solche Werte der Zahl S an, bei denen Petya in einem Zug gewinnen kann.
B) Geben Sie einen Wert von S an, sodass Petya nicht in einem Zug gewinnen kann, Wanja jedoch bei jedem Zug, den Petya macht, mit seinem ersten Zug gewinnen kann. Beschreiben Sie Vanyas Erfolgsstrategie.
Aufgabe 2
Geben Sie zwei solcher Werte von S an, für die Petya eine Gewinnstrategie hat, und:
— Petya kann nicht in einem Zug gewinnen;
- Petja kann mit seinem zweiten Zug gewinnen, unabhängig davon, wie Wanja sich bewegt.
Beschreiben Sie für die gegebenen Werte von S Petits Gewinnstrategie.
Aufgabe 3
Geben Sie den Wert von S an, bei dem:
— Vanya hat eine Gewinnstrategie, die es ihm ermöglicht, in jeder von Petyas Partien mit dem ersten oder zweiten Zug zu gewinnen;
— Vanya verfügt nicht über eine Strategie, die es ihm ermöglicht, beim ersten Zug garantiert zu gewinnen.
Beschreiben Sie für den gegebenen Wert von S Vanyas Gewinnstrategie. Konstruieren Sie einen Baum aller mit dieser Gewinnstrategie möglichen Spiele (in Form eines Bildes oder einer Tabelle). Geben Sie an den Rändern des Baumes an, wer den Zug ausführt. in Knoten – die Anzahl der Steine in einer Position
Der Baum sollte keine Spiele enthalten, die unmöglich sind, wenn der Gewinner seine Gewinnstrategie umsetzt. Beispielsweise ist der vollständige Spielbaum nicht die richtige Antwort auf diese Aufgabe.
✍ Lösung:
- Übung 1.
- a) Petya kann gewinnen, wenn S = 15, … 28
Aufgabe 2.
Aufgabe 3.
Die Tabelle zeigt einen Baum möglicher Spiele (und nur diese) für Vanyas beschriebene Strategie. Die Endpositionen (Wanja gewinnt darin) sind unterstrichen. In der Abbildung ist derselbe Baum grafisch dargestellt. 
Baum aller Spiele, die nach Vanyas Strategie möglich sind:
*Roter Kreis bedeutet Sieg
Frühprüfung in Informatik 2018, Option 1. Aufgabe 26:
Zwei Spieler, Pascha und Wasja, spielen das folgende Spiel. Vor den Spielern liegt ein Steinhaufen. Die Spieler wechseln sich ab Pascha macht den ersten Schritt. In einem Zug kann ein Spieler den Stapel auffüllen eins oder vier Stein bzw Erhöhen Sie die Anzahl der Steine in einem Stapel um das Fünffache. Das Spiel endet, wenn die Anzahl der Steine erreicht ist Der Heap wird mindestens 69.
Gewinner ist der Spieler, der den letzten Zug gemacht hat, also als erster einen Stapel mit 69 oder mehr Steinen erhält. Im ersten Moment befanden sich S-Steine im Stapel, 1 ≤ S ≤ 68.
Übung 1.
A) Geben Sie alle Werte der Zahl S an, für die Pascha in einem Zug gewinnen kann. Begründen Sie, dass alle erforderlichen Werte von S gefunden wurden, und geben Sie den Gewinnzug für jeden angegebenen Wert von S an.
B) Geben Sie einen Wert von S an, sodass Pascha nicht in einem Zug gewinnen kann, aber bei jedem Zug von Pascha kann Vasya mit seinem ersten Zug gewinnen. Beschreiben Sie Vasyas Erfolgsstrategie.
Aufgabe 2. Geben Sie 2 solcher Werte von S an, für die Pascha eine Gewinnstrategie hat, und Pascha kann nicht in einem Zug gewinnen und kann mit seinem zweiten Zug gewinnen, unabhängig davon, wie Vasya sich bewegt. Beschreiben Sie für jeden angegebenen Wert von S Paschas Gewinnstrategie.
Aufgabe 3. Geben Sie mindestens einen Wert von S an, für den Vasya eine Gewinnstrategie hat, die es ihm ermöglicht, in jeder Pascha-Partie mit dem ersten oder zweiten Zug zu gewinnen, und Vasya keine Strategie hat, die es ihm ermöglicht, mit dem ersten Zug zu gewinnen. Beschreiben Sie für den angegebenen Wert von S Vasyas Gewinnstrategie. Konstruieren Sie mit dieser Gewinnstrategie von Vasya einen Baum aller möglichen Spiele (in Form eines Bildes oder einer Tabelle).
✍ Lösung:
- 1.
A) S ≥ 14. Wenn die Anzahl der Steine im Stapel 14 oder mehr beträgt, muss Pascha ihre Anzahl um das Fünffache erhöhen, um so 70 oder mehr Steine zu erhalten.
B) S=13. Pascha kann in seinem ersten Zug 14, 17 oder 65 Steine machen, danach erhöht Vasya die Zahl um das Fünffache und erhält 70, 85 oder 325 Steine auf dem Stapel.
S = 13 Pascha 1. Zug: 13 + 1 = 14 Pascha 1. Zug: 13 + 4 = 17 Pascha 1. Zug: 13 * 5 = 65 Wanja 1. Zug: * 5 = S ≥ 14 Wanja gewinnt 13 - Verluststellung
2.
S = 9, 12. In diesen Fällen muss Pascha 4 Steine zu einem Stapel mit 9 Steinen oder 1 Stein zu einem Stapel mit 12 Steinen hinzufügen und erhält einen Stapel mit 13 Steinen.
Danach läuft das Spiel auf die im Absatz beschriebene Strategie hinaus 1b.
S = 13 Pascha 1. Zug: 9 + 4 = 13 Pascha gewinnt Pascha 1. Zug: 12 + 1 = 13 Pascha gewinnt 9, 12 – Gewinnstellungen ab dem zweiten Zug
3.
S=8. Mit seinem ersten Zug kann Pascha die Anzahl der Steine im Stapel auf 9, 12 oder 40 erhöhen. Wenn Pascha die Zahl um das Fünffache erhöht, gewinnt Vasya mit seinem ersten Zug und erhöht die Anzahl der Steine um das Fünffache.
Bei 9 und 12 Steinen verwendet Vasya die in angegebene Strategie Klausel 2.
S = 8 Pascha 1. Zug: 8 + 1 = 9 Wanja gewinnt (siehe Punkt 2) Pascha 1. Zug: 8 + 4 = 12 Wanja gewinnt (siehe Punkt 2) Pascha 1. Zug: 8 * 5 = 40
Sehen Sie sich das Video zur Lösung von Aufgabe 26 an:
Unified State Exam Simulator in Informatik 2018, Testversion 1. Aufgabe 26 (Krylov S., Ushakov D.):
ein Stein oder . Das Spiel endet in dem Moment, in dem die Gesamtzahl der Steine in den Stapeln erreicht ist mindestens 73.
Der Gewinner ist der Spieler, der den letzten Zug gemacht hat, d. h. der erste, der eine solche Position erhält, dass die Stapel 73 Steine oder mehr enthalten.
Übung 1.
(6, 33), (8, 32)
Geben Sie an, welcher Spieler eine Gewinnstrategie hat. Beschreiben Sie jeweils die Erfolgsstrategie. Erklären Sie, warum diese Strategie zu Gewinnen führt, und geben Sie an, was größte Zahl Möglicherweise sind Züge erforderlich, damit der Gewinner mit dieser Strategie gewinnt.
Aufgabe 2.
Für jede der Startpositionen (6, 32), (7, 32), (8, 31)
Geben Sie an, welcher Spieler eine Gewinnstrategie hat.
Aufgabe 3.
Für die Ausgangsposition (7, 31)
Geben Sie an, welcher Spieler eine Gewinnstrategie hat. Erstellen Sie einen Baum aller Spiele, die mit der von Ihnen angegebenen Gewinnstrategie möglich sind. Stellen Sie sich den Baum als Bild oder Tisch vor.
✍ Lösung:
Videolösung zu Aufgabe 26 mit zwei Heaps:
26_6: Analyse der Aufgabe 26 von der Website von K. Polyakov (Nr. 31):
Zwei Spieler, Petya und Vanya, spielen das folgende Spiel. Vor den Spielern liegen zwei Steinhaufen. Die Spieler wechseln sich ab, Petja macht den ersten Zug. In einer Runde kann ein Spieler zu einem der Stapel (seiner Wahl) hinzufügen. zwei Steine oder Verdoppeln Sie die Anzahl der Steine im Stapel. Um Züge auszuführen, verfügt jeder Spieler über eine unbegrenzte Anzahl an Steinen. Das Spiel endet in dem Moment, in dem die Gesamtzahl der Steine in den Stapeln erreicht ist mindestens 44.
Der Gewinner ist der Spieler, der den letzten Zug gemacht hat, d. h. der erste, der eine solche Position erreicht, dass die Stapel 44 oder mehr Steine enthalten.
Im ersten Moment gab es im ersten Haufen 5 Steine, im zweiten Haufen – S Steine; 1 ≤ S ≤ 38.
Übung 1.
Bei welchem S: 1a)
Petya gewinnt mit seinem ersten Zug; 1b)
Gewinnt Wanja mit seinem ersten Zug?
Aufgabe 2.
Nennen Sie einen beliebigen Wert S, bei dem Petya mit seinem zweiten Zug gewinnen kann.
Aufgabe 3.
Geben Sie den Wert von S an, bei dem Vanya mit seinem ersten oder zweiten Zug gewinnt.
✍ Lösung:
5 + 20*2 = 45 (>44) * 5 – die Anzahl der Steine im ersten Haufen, sie ändert sich nicht je nach Bedingung
Antwort 1 a):
S= (Erklären Sie beim Einheitlichen Staatsexamen die Züge, zum Beispiel: (5; 20) -> (Petit’s move) -> (5; 40); 40 + 5 = 45)
Aufgabe 1 b):
Antwort 1 b): S=19 (Erklären Sie beim Einheitlichen Staatsexamen die Bewegungen, zum Beispiel: (5; 19) -> (Petyas Bewegungen): (5;21),(5;28);(7;19);(7;28). Vanya wird mit dem nächsten Zug überall gewinnen, siehe vorheriger Absatz)
Aufgabe 2:
Antwort 2: S = 16, 17 oder 18
Aufgabe 3:
Antwort 3:
S=14 (Erläutern Sie beim Einheitlichen Staatsexamen die Schritte unter Bezugnahme auf die Erläuterungen in den vorherigen Absätzen.)
Analyse der Aufgabe 26 des Einheitlichen Staatsexamens 2017 in Informatik aus der Demoversion. Diese Aufgabe gehört zum zweiten Teil und hat einen hohen Schwierigkeitsgrad. Die ungefähre Bearbeitungszeit für die Aufgabe beträgt 30 Minuten. Die maximale Punktzahl für die Erledigung der Aufgabe beträgt 3.
Überprüfte Inhaltselemente:
— Die Fähigkeit, einen Spielbaum nach einem vorgegebenen Algorithmus zu erstellen und eine Gewinnstrategie zu rechtfertigen.
Aufgabe 26
Zwei Spieler, Pasha und Valya, spielen das folgende Spiel. Vor den Spielern liegt ein Steinhaufen. Die Spieler wechseln sich ab, Pascha macht den ersten Zug. In einem Zug kann ein Spieler den Stapel auffüllen eins Stein oder erhöhen Sie die Anzahl der Steine im Stapel zweimal. Wenn Sie beispielsweise einen Stapel mit 15 Steinen haben, können Sie in einem Zug einen Stapel mit 16 oder 30 Steinen erhalten. Jeder Spieler hat eine unbegrenzte Anzahl an Steinen, um Züge auszuführen.
Das Spiel endet in dem Moment, in dem die Anzahl der Steine im Stapel mindestens 20 beträgt. Befinden sich gleichzeitig nicht mehr als 30 Steine im Stapel, gilt der Spieler als Sieger, der den letzten Zug gemacht hat. Andernfalls wird sein Gegner zum Sieger. Wenn sich zum Beispiel 17 Steine im Stapel befinden und Pascha die Anzahl der Steine im Stapel verdoppelt, endet das Spiel und Valya ist der Gewinner. Im ersten Moment war es im Haufen S Steine, 1 ≤ S ≤ 19.
Wir werden sagen, dass der Spieler hat Gewinnstrategie, wenn er mit allen Zügen des Gegners gewinnen kann. Die Strategie eines Spielers zu beschreiben bedeutet, zu beschreiben, welchen Zug er in jeder Situation machen sollte, in die er mit anderen Spielzügen als der Gegner geraten könnte.
Führen Sie die folgenden Aufgaben aus.
1. a) Bei welchen Werten der Zahl S Kann Pascha in einem Zug gewinnen?
Listen Sie alle diese Werte und die entsprechenden Bewegungen von Pascha auf.
b) Welcher Spieler hat wann eine Gewinnstrategie? S = 18, 17, 16?
Beschreiben Sie Erfolgsstrategien für diese Fälle.
2. Welcher Spieler hat wann eine Gewinnstrategie? S= 9,8? Beschreiben Sie relevante Gewinnstrategien.
3. Welcher Spieler hat wann eine Gewinnstrategie? S= 7? Konstruieren Sie einen Baum aller mit dieser Gewinnstrategie möglichen Spiele (in Form eines Bildes oder einer Tabelle). Geben Sie an den Rändern des Baumes an, wer den Zug ausführt. in Knoten – die Anzahl der Steine in der Position.
1. a) Pascha kann gewinnen, wenn S= 19 oder S= 10, 11, 12, 13, 14, 15. Wann S= 19 Der erste Zug besteht darin, einen Stein zum Stapel hinzuzufügen, wobei die restlichen Werte angezeigt werden S Sie müssen die Anzahl der Steine verdoppeln.
b) Wann S= 16, 17 oder 18, eine Verdoppelung der Steinanzahl macht keinen Sinn, da nach einem solchen Zug der Gegner gewinnt. Daher können wir davon ausgehen, dass der einzig mögliche Zug darin besteht, einen Stein zum Stapel hinzuzufügen.
Bei S= 18 Nach einem solchen Zug von Pascha befinden sich 19 Steine auf dem Stapel. In dieser Position gewinnt derjenige, der geht (d. h. Valya). (siehe Punkt 1a): bei S= 18 Pascha (der Spieler, der zuerst gehen muss) verliert.
Valya hat eine Erfolgsstrategie.
Bei S= 17, nachdem Pascha mit seinem ersten Zug einen Stein hinzugefügt hat, sind es 18 Steine auf dem Stapel. In dieser Position verliert der Spieler (d. h. Valya). (siehe oben): bei S= 17 Pascha (der Spieler, der zuerst gehen muss) gewinnt. Pascha hat eine Erfolgsstrategie.
Bei S= 16 Valya hat eine Erfolgsstrategie. Wenn Pascha in seinem ersten Zug die Anzahl der Steine verdoppelt, beträgt der Stapel tatsächlich 32 Steine und das Spiel endet sofort mit dem Sieg von Vali. Wenn Pascha einen Stein hinzufügt, beträgt der Stapel 17 Steine. Wie wir bereits wissen, gewinnt in dieser Stellung der Spieler, der ziehen muss (d. h. Valya).
In allen Fällen wird der Gewinn dadurch erreicht, dass der Spieler mit einer Gewinnstrategie während seines Zuges einen Stein auf den Stapel legen muss.
Es ist möglich, Bäume aller möglichen Parteien für bestimmte Werte zu zeichnen S.
Eine andere Möglichkeit besteht darin, (1) darauf hinzuweisen, dass eine Verdoppelung des Heaps keinen Sinn ergibt, und (2) den Fall sequentiell zu reduzieren S= 18 pro Fall S= 19, Fall S= 17 – zum Anlass S= 18 usw.
2. Wann S= 9 oder 8 Pascha hat eine Gewinnstrategie. Es besteht darin, die Anzahl der Steine im Stapel zu verdoppeln und einen Stapel mit 18 bzw. 16 Steinen zu erhalten. In beiden Fällen verliert der Spieler, der den Zug ausführt (jetzt Valya). (siehe Punkt 1b).
3. Wann S= 7 Valya hat eine Erfolgsstrategie. Nach Paschas erstem Zug kann der Stapel entweder 8 oder 14 Steine enthalten. In beiden Stellungen gewinnt der Spieler, der den Zug ausführt (jetzt Valya). Ereignis S= 8 berücksichtigt in Punkt 2, Fall S= 14 überprüft in Punkt 1a.
Die Tabelle zeigt den Baum möglicher Spiele für die beschriebene Vali-Strategie. Die Endpositionen (Valya gewinnt darin) sind unterstrichen. In der Abbildung ist derselbe Baum grafisch dargestellt (beide Arten der Baumdarstellung sind akzeptabel).
Der Baum aller Spiele, die nach Valyas Strategie möglich sind. Das >>-Zeichen zeigt die Positionen an, an denen das Spiel endet.
