Un "gioco Markov"

Question

Chiamo giochi simili a quello che descrivo di seguito come giochi Markov. Sto selezionando solo quello o piuttosto una serie di giochi a 1 parametro. La sfida aperta è scoprire quale dei giocatori$\ 0\ $ o $\ 1\ $ ha una strategia vincente per ciascuno dei parametri dati $\ W.$

NOTAZIONE $\ n\%2=0\ $ per $\ n\ $ anche, e $\ n\%2=1\ $ per $\ n\ $ dispari.;

Permettere $ d(0)=J(0)=0.\ $ Per numero intero positivo arbitrario $\ n,\ $ giocatore $\ n\%2\ $ seleziona un numero intero positivo $\ d(n)\le d(n-1)+1;\ $ poi $\ J(n)=J(n-1)+d(n).$

Quando i giocatori competono al gioco $\ M(W),\ $ dove $\ W\ $ è un numero intero positivo fissato arbitrariamente, quindi il giocatore che ottiene esattamente $J(n)=W\ $ vince.

Permettere $\ \omega(W)=0\ $ se giocatore $0$ ha una strategia vincente a $M(W);\ $ altrimenti lascia $\ \omega(W)=1\ $ se giocatore $1$ ha una strategia vincente a $M(W)$.

PROBLEMA:   funzione di calcolo$\ \omega:\mathbb N\to\{0\ 1\}.$

Per esempio: $\ \omega(1)=1;\ \omega(2)=\omega(3)=0;\ \omega(4)=1, $ ecc. Tuttavia, $\ \omega(120)\ $ o $\ \omega(5553)\ $ è un po 'più difficile (e sconosciuto a me).

Answer 1

La risposta non cambia molto con numeri maggiori.

La risposta completa è $$ \omega(W)=\left\{ \begin{array}{ll} 1, & W\%5=1,4\\ 0, & W\%5=0,2,3 \end{array}\right. $$

Diciamo quella posizione $(W-J,d)$ sta vincendo se giocatore $n\%2$ ha una strategia vincente per il gioco $M(W)$ a sua volta $n$ con $d(n)=d,J(n)=J$. Altrimenti sta perdendo. Chiaramente, in effetti dipende solo dalla differenza$W-J$.

$(i,d)$ è vincere se e solo se esiste perdere $(j,f)$ st $j+f=i,f\le d+1$. Ci interessa sapere se$(W-1,1)$ sta vincendo.

Per questo è sufficiente considerare solo $(i,d)$ con $d\le 3$.

Il modello ha questo aspetto:

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

Per vederlo, nota:

• $(0,d)$ sta perdendo per tutti $d$, ovvero la prima riga viene riempita con $-$'S
• Se $(i,d)$ sta vincendo, quindi $(i,d+1)$ sta vincendo, cioè a destra di $+$ è sempre un altro $+$

Answer 2

Abbiamo già una risposta completa da @JosephGordon che ha dimostrato la periodicità di $\ \omega,\ $ la durata del periodo è di 5. Joseph - molte grazie!

Lasciatemi scrivere una soluzione che almeno per me è più facile da seguire.

Ricorda quel giocatore $\ \omega(n)\ $ è colui che ha la strategia vincente per il gioco di Markov $\ M(n).$

Teorema Per ogni intero positivo$\ n\ $ le seguenti due proprietà valgono:

• Giocatore $\ \omega(n)\ $ può vincere ogni partita di $\ M(n)\ $ selezionando tutte le proprie mosse in modo tale che $\ d(k)\le 3;$

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

  Giocatore di prova$\ \omega(n)\ $, durante il gioco $\ M(n+5)\ $, è in grado di arrivare alla posizione $\ n\ $ mentre si utilizzano mosse tali $\ d(k)\le 3\ $ogni volta. In particolare,$\ d(t)\le 3\ $ quando $\ J(t)=n.\ $ Quindi, ora abbiamo solo quattro estensioni del gioco:

• $\ d(t+1)=4.\ $ Quindi giocatore $\ \omega(n)\ $ gioca $\ d(t+2)=1\ $ e vince (da $\ J(t+2)=n+5\ \text{and}\ t+2\equiv t\mod 2)$;

• $\ d(t+1)=3.\ $ Quindi giocatore $\ \omega(n)\ $ gioca $\ d(t+2)=2\ $ e vince;

• $\ d(t+1)=2.\ $ Quindi giocatore $\ \omega(n)\ $ gioca $\ d(t+2)=3\ $ e vince;

• $\ d(t+1)=1.\ $ Quindi giocatore $\ \omega(n)\ $ gioca $\ d(t+2)=1;\ $ poi l'altro giocatore gioca $\ d(t+3)= 1$ o $2\ $e lettore $\ \omega(n)\ $ gioca $\ 2$ o $1\ $ rispettivamente, e vince.

Il resto formale dell'argomento è del tutto normale e ovvio. Fine della PROVA.

La descrizione numerica completa di $\ \omega\ $ è dato dal teorema di cui sopra e dall'iniziale $5$ valori:

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

Per esempio, $\ \omega(5)=0\ $ perché J (1) = 1, allora player $0$ può giocare d (2) = 1, cioè J (2) = 2, quindi - dopo una mossa del giocatore $0$ -- giocatore $\ 0\ $ Giocherò $\ J(4)=5.$