問題
【ｎ×ｍ盤】
ｎ×ｍの大きさの盤を使用する。
【ランダム詰将棋】
着手は動かす駒を決めることしかできず、その駒が可能な動き方全体から等確率で１つ選ばれて動く。指定された確率p以上で詰みとなる着手列を求める。
［備考］
・攻方は王手を掛けなくてもよい。
・攻方は最短手数の詰みを目指し、受方はできるだけ詰まないように応じる。
・着手列Fの途中で詰みとなる場合も、「着手列Fで詰み」とみなす。
・千日手は考慮しない。同一局面が現れてもよい。
【蟠蛇（蛇）】
縦と斜め後ろに１マス進む駒。
【Zero（零）】
(0,0)-Leaper。つまり、現在位置に移動する駒。
【駒詰】
玉が指定駒の性能になる。ルール名は例えば「角王」のように「駒名＋王」で表す。
解答
蛇 零 蛇 零 …… 蛇 まで 43手（攻方が22回指す）
攻方は蛇を動かすしかなく、受方は零を動かす（その場にとどまる）しかない。零王が詰みであることは、蛇が32の地点にいることに他ならない。したがって、攻方が何回蛇を動かせば
\(\displaystyle \begin{pmatrix} \text{蛇が一度でも32に} \\ \text{到達する確率} \end{pmatrix} \geq1-\left(\frac{5}{6}\right)^{10}\)
となるかを考えればよい。
蛇が２段目にいるときは確率 \(1\) で真上に動き、１段目にいるときはいずれにせよ２段目へ動く。そこで、攻方の２手を１ステップとし、下図の \(S_1\) を出発するランダムウォークを考える。
時刻 \(n\) でランダムウォーカーが \(S_1, S_2, S_3\) にいる確率をそれぞれ \(a_n, b_n, c_n\) とおけば、\(c_n\) は「攻方が \(2n\) 回指して詰みである確率」に他ならない。
\(a_n, b_n, c_n\) について以下が成り立つ：
\( \begin{align}
a_n &= \frac{1}{2}a_{n-1} + \frac{1}{3}b_{n-1} \\
b_n &= \frac{1}{2}a_{n-1} + \frac{1}{3}b_{n-1} \\
c_n &= \frac{1}{3}b_{n-1} + c_{n-1}
\end{align} \)
したがって、
\( A = \begin{bmatrix}
1/2 & 1/2 & 0 \\
1/3 & 1/3 & 1/3 \\
0 & 0 & 1
\end{bmatrix} \)
とおけば
\( \begin{align}
\begin{bmatrix} a_n & b_n & c_n \end{bmatrix}
&= \begin{bmatrix} a_{n-1} & b_{n-1} & c_{n-1} \end{bmatrix} A \\
&= \begin{bmatrix} a_{n-2} & b_{n-2} & c_{n-2} \end{bmatrix} A^2 \\
&= \cdots \\
&= \begin{bmatrix} a_0 & b_0 & c_0 \end{bmatrix} A^n \\
&= \begin{bmatrix} 1 & 0 & 0 \end{bmatrix} A^n
\end{align} \)
となる。行列 \(A\) の \(n\) 乗を求めればよい。\(A\) の固有多項式は
\(\displaystyle \det(A-\lambda I) = \ – \lambda \left(\lambda \ – \frac{5}{6}\right) (\lambda \ – 1) \)
と計算できる。異なる \(3\) つの根を持つので \(A\) は対角化可能。実際、
\( D = \begin{bmatrix}
0 & 0 & 0 \\
0 & 5/6 & 0 \\
0 & 0 & 1
\end{bmatrix} \)
\( P = \begin{bmatrix}
-1 & 3/2 & 1 \\
1 & 1 & 1 \\
0 & 0 & 1
\end{bmatrix} \)
\(\displaystyle P^{-1} = \frac{1}{5}\begin{bmatrix}
-2 & 3 & -1 \\
2 & 2 & -4 \\
0 & 0 & 5
\end{bmatrix} \)
を用いて \(P^{-1}AP=D\) とできる。\(A=PDP^{-1}\) なので \(A^n=PD^nP^{-1}\) である。これを計算して
\(\displaystyle A^n = \begin{bmatrix}
\frac{1}{2}\left(\frac{5}{6}\right)^{n-1} & \frac{1}{2}\left(\frac{5}{6}\right)^{n-1} & 1 – \left(\frac{5}{6}\right)^{n-1} \\
\frac{1}{3}\left(\frac{5}{6}\right)^{n-1} & \frac{1}{3}\left(\frac{5}{6}\right)^{n-1} & 1 – \frac{2}{3}\left(\frac{5}{6}\right)^{n-1} \\
0 & 0 & 1
\end{bmatrix} \)
となる。したがって
\(\displaystyle c_n = 1 \ – \left(\frac{5}{6}\right)^{n-1} \)
である。\(\displaystyle c_n \geq1-\left(\frac{5}{6}\right)^{10}\) を満たす最小の自然数は \(n=11\) なので、攻方が \(22\) 回指せばよい。
計算ミスなどあればご指摘いただけますと幸いです。
また、もっと簡単な求め方があれば是非教えてください。