"Markov 게임"
나는 아래에서 설명하는 것과 비슷한 게임을 Markov 게임이라고 부릅니다. 나는 단지 그 하나 또는 오히려 1- 파라미터 시리즈의 게임을 선택하고 있습니다. 공개적인 도전은 어떤 플레이어가$\ 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)\ $ 조금 더 어렵습니다 (그리고 나에게 알려지지 않았습니다).
답변
대답은 숫자가 많을수록 많이 변하지 않습니다.
정답은 $$ \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)$ 즉, 오른쪽에 $+$ 항상 또 다른 $+$
우리는 이미 주기성을 증명 한 @JosephGordon의 완전한 답변을 받았습니다. $\ \omega,\ $ 기간은 5입니다. Joseph – 많은 감사합니다!
적어도 나에게 따라 가기 쉬운 해결책을 작성하겠습니다.
그 선수 기억 $\ \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.\ $ 따라서 이제 게임의 확장은 4 개뿐입니다.
$\ 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.$