"เกม Markov"

Question

ฉันเรียกเกมที่คล้ายกับเกมที่ฉันอธิบายไว้ด้านล่างว่าเป็นเกม Markov ฉันกำลังเลือกชุดเกมหนึ่งหรือมากกว่าหนึ่งพารามิเตอร์ ความท้าทายที่เปิดกว้างคือการค้นหาว่าผู้เล่นคนใด$\ 0\ $ หรือ $\ 1\ $ มีกลยุทธ์ที่ชนะสำหรับแต่ละพารามิเตอร์ที่กำหนด $\ W.$

การแจ้งเตือน $\ n\%2=0\ $ สำหรับ $\ n\ $ แม้และ $\ n\%2=1\ $ สำหรับ $\ n\ $ แปลก.;

ปล่อย $ d(0)=J(0)=0.\ $ สำหรับจำนวนเต็มบวกโดยพลการ $\ n,\ $ ผู้เล่น $\ n\%2\ $ เลือกจำนวนเต็มบวก $\ d(n)\le d(n-1)+1;\ $ แล้ว $\ J(n)=J(n-1)+d(n).$

เมื่อผู้เล่นแข่งขันกันในเกม $\ M(W),\ $ ที่ไหน $\ W\ $ เป็นจำนวนเต็มบวกคงที่โดยพลการจากนั้นผู้เล่นที่ได้รับตรง $J(n)=W\ $ ชนะ

ปล่อย $\ \omega(W)=0\ $ ถ้าผู้เล่น $0$ มีกลยุทธ์การชนะที่ $M(W);\ $ เป็นอย่างอื่นให้ $\ \omega(W)=1\ $ ถ้าผู้เล่น $1$ มีกลยุทธ์การชนะที่ $M(W)$.

ปัญหา:   ฟังก์ชันคำนวณ$\ \omega:\mathbb N\to\{0\ 1\}.$

ตัวอย่างเช่น: $\ \omega(1)=1;\ \omega(2)=\omega(3)=0;\ \omega(4)=1, $ เป็นต้นอย่างไรก็ตาม $\ \omega(120)\ $ หรือ $\ \omega(5553)\ $ ยากกว่านิดหน่อย (และไม่รู้จักฉัน)

Answer 1

คำตอบไม่เปลี่ยนแปลงมากนักเมื่อมีจำนวนมากขึ้น

คำตอบเต็มคือ $$ \omega(W)=\left\{ \begin{array}{ll} 1, & W\%5=1,4\\ 0, & W\%5=0,2,3 \end{array}\right. $$

ให้เราพูดตำแหน่งนั้น $(W-J,d)$ จะชนะถ้าผู้เล่น $n\%2$ มีกลยุทธ์ที่ชนะสำหรับเกม $M(W)$ ในตาของเขา $n$ ด้วย $d(n)=d,J(n)=J$. มันจะสูญเสียอย่างอื่น เห็นได้ชัดว่ามันขึ้นอยู่กับความแตกต่างเท่านั้น$W-J$.

$(i,d)$ คือการชนะหากมีการสูญเสีย $(j,f)$ เซนต์ $j+f=i,f\le d+1$. เราสนใจว่า$(W-1,1)$ กำลังชนะ

สำหรับสิ่งนี้ก็เพียงพอที่จะพิจารณาเท่านั้น $(i,d)$ ด้วย $d\le 3$.

รูปแบบมีลักษณะดังนี้:

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

หากต้องการดูโปรดสังเกต:

• $(0,d)$ กำลังสูญเสียสำหรับทุกคน $d$เช่นแถวแรกเต็มไปด้วย $-$ของ
• ถ้า $(i,d)$ เป็นผู้ชนะแล้ว $(i,d+1)$ คือการชนะกล่าวคือทางด้านขวาของ $+$ เป็นอื่นเสมอ $+$

Answer 2

เรามีคำตอบแบบเต็มจาก @JosephGordon ที่พิสูจน์แล้วว่าเป็นระยะของ $\ \omega,\ $ ความยาวของช่วงเวลาคือ 5. โจเซฟ - ขอบคุณมาก!

ให้ฉันเขียนวิธีแก้ปัญหาที่อย่างน้อยฉันก็ทำตามได้ง่ายกว่า

จำผู้เล่นคนนั้นไว้ $\ \omega(n)\ $ เป็นผู้ที่มีกลยุทธ์ในการชนะเกม Markov $\ M(n).$

ทฤษฎีบทสำหรับทุกจำนวนเต็มบวก$\ n\ $ คุณสมบัติสองประการต่อไปนี้ถือ:

• ผู้เล่น $\ \omega(n)\ $ สามารถชนะทุกเกม $\ M(n)\ $ โดยเลือกการเคลื่อนไหวของตัวเองทั้งหมดเช่นนั้น $\ d(k)\le 3;$

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

  ผู้เล่นพิสูจน์$\ \omega(n)\ $เมื่อเล่นเกม $\ M(n+5)\ $สามารถมาถึงตำแหน่ง $\ n\ $ ในขณะที่ใช้การเคลื่อนไหวเช่นนั้น $\ d(k)\le 3\ $แต่ละครั้ง. โดยเฉพาะอย่างยิ่ง,$\ d(t)\le 3\ $ เมื่อไหร่ $\ J(t)=n.\ $ ดังนั้นตอนนี้เรามีเพียงสี่ส่วนขยายของเกม:

• $\ d(t+1)=4.\ $ จากนั้นผู้เล่น $\ \omega(n)\ $ เล่น $\ d(t+2)=1\ $ และชนะ (ตั้งแต่ $\ J(t+2)=n+5\ \text{and}\ t+2\equiv t\mod 2)$;

• $\ d(t+1)=3.\ $ จากนั้นผู้เล่น $\ \omega(n)\ $ เล่น $\ d(t+2)=2\ $ และชนะ;

• $\ d(t+1)=2.\ $ จากนั้นผู้เล่น $\ \omega(n)\ $ เล่น $\ d(t+2)=3\ $ และชนะ;

• $\ d(t+1)=1.\ $ จากนั้นผู้เล่น $\ \omega(n)\ $ เล่น $\ d(t+2)=1;\ $ จากนั้นผู้เล่นคนอื่นเล่น $\ d(t+3)= 1$ หรือ $2\ $และผู้เล่น $\ \omega(n)\ $ เล่น $\ 2$ หรือ $1\ $ ตามลำดับและชนะ

การโต้แย้งที่เหลืออย่างเป็นทางการเป็นกิจวัตรและชัดเจนโดยสิ้นเชิง สิ้นสุดการพิสูจน์

คำอธิบายตัวเลขที่สมบูรณ์ของ $\ \omega\ $ กำหนดโดยทฤษฎีบทข้างต้นและค่าเริ่มต้น $5$ ค่า:

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

ตัวอย่างเช่น $\ \omega(5)=0\ $ เพราะ J (1) = 1 ตามด้วยผู้เล่น $0$ สามารถเล่น d (2) = 1 เช่น J (2) = 2 จากนั้น - หลังจากย้ายโดยผู้เล่น $0$ - ผู้เล่น $\ 0\ $ จะเล่น $\ J(4)=5.$