Bir "Markov oyunu"

Question

Aşağıda tanımladığıma benzer oyunları Markov oyunları olarak adlandırıyorum. Sadece bir veya daha doğrusu 1 parametreli oyun serisini seçiyorum. Açık olan zorluk, hangi oyuncuların$\ 0\ $ veya $\ 1\ $ verilen parametrelerin her biri için bir kazanma stratejisi vardır $\ W.$

NOTASYON $\ n\%2=0\ $ için $\ n\ $ hatta ve $\ n\%2=1\ $ için $\ n\ $ garip .;

İzin Vermek $ d(0)=J(0)=0.\ $ Keyfi pozitif tamsayı için $\ n,\ $ oyuncu $\ n\%2\ $ pozitif bir tam sayı seçer $\ d(n)\le d(n-1)+1;\ $ sonra $\ J(n)=J(n-1)+d(n).$

Oyuncular oyunda rekabet ettiğinde $\ M(W),\ $ nerede $\ W\ $ keyfi olarak sabitlenmiş bir pozitif tam sayıdır, o zaman tam olarak $J(n)=W\ $ kazanır.

İzin Vermek $\ \omega(W)=0\ $ eğer oyuncu $0$ kazanma stratejisi var $M(W);\ $ aksi halde izin ver $\ \omega(W)=1\ $ eğer oyuncu $1$ kazanma stratejisi var $M(W)$.

PROBLEM:   Hesaplama işlevi$\ \omega:\mathbb N\to\{0\ 1\}.$

Örneğin: $\ \omega(1)=1;\ \omega(2)=\omega(3)=0;\ \omega(4)=1, $ vb. Ancak, $\ \omega(120)\ $ veya $\ \omega(5553)\ $ biraz daha zor (ve benim için bilinmiyor)

Answer 1

Cevap daha büyük sayılarla pek değişmez.

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

O pozisyonu söyleyelim $(W-J,d)$ oyuncu ise kazanıyor $n\%2$ oyun için kazanan bir stratejiye sahip $M(W)$ sırayla $n$ ile $d(n)=d,J(n)=J$. Aksi takdirde kaybediyor. Açıkçası, gerçekten sadece farka bağlı$W-J$.

$(i,d)$ eğer varsa, kaybetmek var $(j,f)$ st $j+f=i,f\le d+1$. Biz ilgileniyoruz$(W-1,1)$ kazanıyor.

Bunun için sadece düşünmek yeterli $(i,d)$ ile $d\le 3$.

Desen şuna benzer:

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

Görmek için dikkat edin:

• $(0,d)$ herkes için kaybediyor $d$yani ilk satır $-$'s
• Eğer $(i,d)$ o zaman kazanıyor $(i,d+1)$ kazanıyor, yani sağında $+$ her zaman başka $+$

Answer 2

@JosephGordon'dan şu anda tam bir cevabımız var. $\ \omega,\ $ dönemin uzunluğu 5'ti. Yusuf - çok teşekkürler!

En azından benim için takip etmesi daha kolay olan bir çözüm yazmama izin verin.

O oyuncuyu hatırla $\ \omega(n)\ $ Markov oyunu için kazanan stratejiye sahip olan $\ M(n).$

Teorem Her pozitif tam sayı için$\ n\ $ aşağıdaki iki özellik geçerlidir:

• oyuncu $\ \omega(n)\ $ her oyununu kazanabilir $\ M(n)\ $ tüm hareketlerini seçerek $\ d(k)\le 3;$

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

Proof   Player$\ \omega(n)\ $, oyun oynarken $\ M(n+5)\ $pozisyona ulaşabilir $\ n\ $ böyle hareketler kullanırken $\ d(k)\le 3\ $her seferinde. Özellikle,$\ d(t)\le 3\ $ ne zaman $\ J(t)=n.\ $ Böylece, artık oyunun sadece dört uzantısına sahibiz:

• $\ d(t+1)=4.\ $ Sonra oyuncu $\ \omega(n)\ $ oyunlar $\ d(t+2)=1\ $ ve kazanır (beri $\ J(t+2)=n+5\ \text{and}\ t+2\equiv t\mod 2)$;

• $\ d(t+1)=3.\ $ Sonra oyuncu $\ \omega(n)\ $ oyunlar $\ d(t+2)=2\ $ ve kazanır;

• $\ d(t+1)=2.\ $ Sonra oyuncu $\ \omega(n)\ $ oyunlar $\ d(t+2)=3\ $ ve kazanır;

• $\ d(t+1)=1.\ $ Sonra oyuncu $\ \omega(n)\ $ oyunlar $\ d(t+2)=1;\ $ sonra diğer oyuncu oynar $\ d(t+3)= 1$ veya $2\ $ve oyuncu $\ \omega(n)\ $ oyunlar $\ 2$ veya $1\ $ sırasıyla ve kazanır.

Tartışmanın biçimsel geri kalanı tamamen rutin ve açıktır. PROOF'un sonu.

Tam sayısal açıklaması $\ \omega\ $ yukarıdaki teorem ve başlangıç $5$ değerler:

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

Örneğin, $\ \omega(5)=0\ $ çünkü J (1) = 1, sonra oyuncu $0$ d (2) = 1 oynayabilir, yani J (2) = 2, sonra - oyuncunun hamlesinden sonra $0$ -- oyuncu $\ 0\ $ oynayacak $\ J(4)=5.$