Ein "Markov-Spiel"

Question

Ich nenne Spiele, die dem unten beschriebenen ähnlich sind, Markov-Spiele. Ich wähle nur diese eine oder eher eine 1-Parameter-Reihe von Spielen aus. Die offene Herausforderung besteht darin, herauszufinden, welcher der Spieler$\ 0\ $ oder $\ 1\ $ hat eine Gewinnstrategie für jeden der gegebenen Parameter $\ W.$

NOTATION $\ n\%2=0\ $ zum $\ n\ $ sogar und $\ n\%2=1\ $ zum $\ n\ $ seltsam.;

Lassen $ d(0)=J(0)=0.\ $ Für eine beliebige positive ganze Zahl $\ n,\ $ Spieler $\ n\%2\ $ wählt eine positive ganze Zahl aus $\ d(n)\le d(n-1)+1;\ $ dann $\ J(n)=J(n-1)+d(n).$

Wenn Spieler am Spiel teilnehmen $\ M(W),\ $ wo $\ W\ $ ist eine willkürlich festgelegte positive ganze Zahl, dann der Spieler, der genau bekommt $J(n)=W\ $ Gewinnt.

Lassen $\ \omega(W)=0\ $ wenn Spieler $0$ hat eine Gewinnstrategie bei $M(W);\ $ sonst lassen $\ \omega(W)=1\ $ wenn Spieler $1$ hat eine Gewinnstrategie bei $M(W)$.

PROBLEM:   Rechenfunktion$\ \omega:\mathbb N\to\{0\ 1\}.$

Beispielsweise: $\ \omega(1)=1;\ \omega(2)=\omega(3)=0;\ \omega(4)=1, $ usw. Allerdings $\ \omega(120)\ $ oder $\ \omega(5553)\ $ ist etwas schwieriger (und mir unbekannt).

Answer 1

Die Antwort ändert sich bei größeren Zahlen nicht viel.

Die vollständige Antwort lautet $$ \omega(W)=\left\{ \begin{array}{ll} 1, & W\%5=1,4\\ 0, & W\%5=0,2,3 \end{array}\right. $$

Sagen wir diese Position $(W-J,d)$ gewinnt, wenn Spieler $n\%2$ hat eine Gewinnstrategie für das Spiel $M(W)$ an der Reihe $n$ mit $d(n)=d,J(n)=J$. Es verliert sonst. Klar, es kommt ja nur auf den Unterschied an$W-J$.

$(i,d)$ gewinnt, wenn es Verluste gibt $(j,f)$ st $j+f=i,f\le d+1$. Uns interessiert, ob$(W-1,1)$ gewinnt.

Hierfür genügt es, nur zu berücksichtigen $(i,d)$ mit $d\le 3$.

Das Muster sieht folgendermaßen aus:

$ \begin{array}{ccc} - & - & -\\ + & + & +\\ + & + & +\\ - & + & +\\ + & + & +\\ - & - & -\\ \vdots & \vdots & \vdots \end{array} $

Um es zu sehen, beachten Sie:

• $(0,d)$ verliert für alle $d$dh die erste Reihe ist gefüllt mit $-$'s
• wenn $(i,d)$ gewinnt also $(i,d+1)$ gewinnt, dh rechts von $+$ ist immer ein anderer $+$

Answer 2

Wir haben bereits eine vollständige Antwort von @JosephGordon, der die Periodizität von bewiesen hat $\ \omega,\ $ Die Dauer des Zeitraums beträgt 5. Joseph - vielen Dank!

Lassen Sie mich eine Lösung schreiben, die zumindest für mich leichter zu befolgen ist.

Erinnere dich an diesen Spieler $\ \omega(n)\ $ ist derjenige, der die Gewinnstrategie für das Markov-Spiel hat $\ M(n).$

Satz Für jede positive ganze Zahl$\ n\ $ Die folgenden zwei Eigenschaften gelten:

• Spieler $\ \omega(n)\ $ kann jedes Spiel von gewinnen $\ M(n)\ $ indem Sie alle ihre eigenen Züge so auswählen, dass $\ d(k)\le 3;$

• $\ \omega(n+5) = \omega(5).\ $

Proof-   Spieler$\ \omega(n)\ $beim Spielen $\ M(n+5)\ $kann Position erreichen $\ n\ $ während Bewegungen so nutzen, dass $\ d(k)\le 3\ $jedes Mal. Speziell,$\ d(t)\le 3\ $ wann $\ J(t)=n.\ $ Somit haben wir jetzt nur vier Erweiterungen des Spiels:

• $\ d(t+1)=4.\ $ Dann Spieler $\ \omega(n)\ $ Theaterstücke $\ d(t+2)=1\ $ und gewinnt (seit $\ J(t+2)=n+5\ \text{and}\ t+2\equiv t\mod 2)$;;

• $\ d(t+1)=3.\ $ Dann Spieler $\ \omega(n)\ $ Theaterstücke $\ d(t+2)=2\ $ und gewinnt;

• $\ d(t+1)=2.\ $ Dann Spieler $\ \omega(n)\ $ Theaterstücke $\ d(t+2)=3\ $ und gewinnt;

• $\ d(t+1)=1.\ $ Dann Spieler $\ \omega(n)\ $ Theaterstücke $\ d(t+2)=1;\ $ dann spielt der andere Spieler $\ d(t+3)= 1$ oder $2\ $und Spieler $\ \omega(n)\ $ Theaterstücke $\ 2$ oder $1\ $ jeweils und gewinnt.

Der formale Rest des Arguments ist völlig routinemäßig und offensichtlich. Ende des Beweises.

Die vollständige numerische Beschreibung von $\ \omega\ $ ist durch den obigen Satz und die Initiale gegeben $5$ Werte:

$$ \omega(1)=1;\,\ \omega(2)=\omega(3)=0;\,\ \omega(4)=1, \,\ \omega(5)=0 $$

Beispielsweise, $\ \omega(5)=0\ $ weil J (1) = 1, dann Spieler $0$ kann d (2) = 1 spielen, dh J (2) = 2, dann - nach einem Zug des Spielers $0$ -- Spieler $\ 0\ $ werde spielen $\ J(4)=5.$