「マルコフゲーム」
以下で説明するものと同様のゲームをマルコフゲームと呼びます。私はその1つ、またはむしろ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)$ st $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です。ジョセフ-どうもありがとう！
少なくとも私にとっては従うのが簡単な解決策を書かせてください。
そのプレーヤーを覚えておいてください $\ \omega(n)\ $ マルコフゲームの勝利戦略を持っている人です $\ M(n).$
すべての正の整数の定理$\ n\ $ 次の2つのプロパティが成り立ちます。
プレーヤー $\ \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.$