2025年 年賀詰 解答

2025年1月3日

2025/1/26 神無太郎さんの解法を追記しました。

問題

3×2盤ランダム詰将棋123攻方持駒 なし受方持駒 なしp=1-(5/6)^10蛇:蟠蛇零:Zero王

【n×m盤】
n×mの大きさの盤を使用する。

【ランダム詰将棋】
着手は動かす駒を決めることしかできず、その駒が可能な動き方全体から等確率で1つ選ばれて動く。指定された確率p以上で詰みとなる着手列を求める。
[備考]
・攻方は王手を掛けなくてもよい。
・攻方は最短手数の詰みを目指し、受方はできるだけ詰まないように応じる。
・着手列Fの途中で詰みとなる場合も、「着手列Fで詰み」とみなす。
・千日手は考慮しない。同一局面が現れてもよい。

【蟠蛇(蛇)】
縦と斜め後ろに1マス進む駒。

12345

【Zero(零)】
(0,0)-Leaper。つまり、現在位置に移動する駒。

【駒詰】
玉が指定駒の性能になる。ルール名は例えば「角王」のように「駒名+王」で表す。

解答

蛇 零 蛇 零 …… 蛇 まで 43手(攻方が22回指す)

攻方は蛇を動かすしかなく、受方は零を動かす(その場にとどまる)しかない。零王が詰みであることは、蛇が32の地点にいることに他ならない。したがって、攻方が何回蛇を動かせば

\(\displaystyle \begin{pmatrix} \text{蛇が一度でも32に} \\ \text{到達する確率} \end{pmatrix} \geq1-\left(\frac{5}{6}\right)^{10}\)

となるかを考えればよい。

蛇が2段目にいるときは確率 \(1\) で真上に動き、1段目にいるときはいずれにせよ2段目へ動く。そこで、攻方の2手を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\) 回指せばよい。


計算ミスなどあればご指摘いただけますと幸いです。
また、もっと簡単な求め方があれば是非教えてください。

追記(2025/1/26)
神無太郎さんより、\(c_n\) の簡単な求め方をお知らせいただきました。ありがとうございます!
私は気が付かなかったのですが、\(a_n=b_n\) を使えば \(c_n\) がすぐに分かります。
詳細は以下の通りです。


\(n \ge 1\) として、

\( \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}
\end{align} \)

から

\( \begin{align}
a_n &= b_n = a_{n-1} \cdot \frac{5}{6} \\
&= a_{n-2} \cdot \left(\frac{5}{6}\right)^{2} \\
&= \cdots \\
&= a_{1} \cdot \left(\frac{5}{6}\right)^{n-1} \\
&= \frac{1}{2} \left(\frac{5}{6}\right)^{n-1}
\end{align} \)

となる。\(a_n + b_n + c_n = 1\) だから、

\( \begin{align}
c_n &= 1 – \left(a_n + b_n \right) \\
&= 1 – \left(\frac{5}{6}\right)^{n-1}
\end{align} \)

である。