解説

方針・初手

1回の移動で $x+y$ は必ず $1$ だけ増えるか、$1$ だけ減る。したがって、時刻と座標和の偶奇に注目すると、到達可能性を素早く判定できる。

確率計算では、各時刻の全経路数が $4^n$ 通りであることを用い、目的の点に到達する経路数を数える。

解法1

右への移動を $R$、左への移動を $L$、上への移動を $U$、下への移動を $D$ と書く。各移動は確率 $\dfrac14$ で起こるから、時刻 $n$ までの移動列はすべて等確率であり、各移動列の確率は $\left(\dfrac14\right)^n$ である。

(1)

時刻 $2$ では、全移動列は

$$ 4^2=16

$$

通りである。

点 $(0,0)$ にいるためには、2回の移動で元に戻ればよい。可能な移動列は

$$ RL,\ LR,\ UD,\ DU

$$

の $4$ 通りである。よって

$$ P((0,0))=\frac{4}{16}=\frac14

$$

である。

点 $(1,0)$ については、時刻 $2$ で $x+y=1$ となる。しかし時刻 $2$ に到達できる点では $x+y$ は偶数でなければならないので、到達不可能である。したがって

$$ P((1,0))=0

$$

である。

点 $(1,1)$ にいるためには、右に1回、上に1回移動すればよい。可能な移動列は

$$ RU,\ UR

$$

の $2$ 通りである。よって

$$ P((1,1))=\frac{2}{16}=\frac18

$$

である。

点 $(2,0)$ にいるためには、右に2回移動するしかない。可能な移動列は

$$ RR

$$

の $1$ 通りである。よって

$$ P((2,0))=\frac{1}{16}

$$

である。

(2)

時刻 $4$ で点 $(0,0)$ にいるためには、右への移動回数と左への移動回数が等しく、上への移動回数と下への移動回数が等しければよい。

4回の移動で元に戻る場合を、移動の種類の回数で分ける。

（i） 右2回、左2回の場合

この場合の移動列は

$$ \frac{4!}{2!2!}=6

$$

通りである。

（ii） 上2回、下2回の場合

この場合も同様に

$$ \frac{4!}{2!2!}=6

$$

通りである。

（iii） 右1回、左1回、上1回、下1回の場合

この場合の移動列は

$$ 4!=24

$$

通りである。

したがって、時刻 $4$ で原点にいる移動列の総数は

$$ 6+6+24=36

$$

通りである。

全移動列は

$$ 4^4=256

$$

通りであるから、求める確率は

$$ \frac{36}{256}=\frac{9}{64}

$$

である。

(3)

時刻 $0$ では駒は $(0,0)$ にある。このとき

$$ 0-(0+0)=0

$$

であり、これは $2$ の倍数である。

次に、時刻 $k$ に点 $(x,y)$ にいて、$k-(x+y)$ が $2$ の倍数であるとする。

時刻 $k+1$ では、駒は次のいずれかに移動する。

$$ (x+1,y),\quad (x-1,y),\quad (x,y+1),\quad (x,y-1)

$$

それぞれについて、時刻 $k+1$ と座標和との差を調べる。

点 $(x+1,y)$ に移動したとき、

$$ (k+1)-{(x+1)+y}=k-(x+y)

$$

である。

点 $(x-1,y)$ に移動したとき、

$$ (k+1)-{(x-1)+y}=k-(x+y)+2

$$

である。

点 $(x,y+1)$ に移動したとき、

$$ (k+1)-{x+(y+1)}=k-(x+y)

$$

である。

点 $(x,y-1)$ に移動したとき、

$$ (k+1)-{x+(y-1)}=k-(x+y)+2

$$

である。

いずれの場合も、$k-(x+y)$ が $2$ の倍数ならば、新しい時刻と新しい座標和との差も $2$ の倍数である。

したがって数学的帰納法により、時刻 $n$ に駒が点 $(x,y)$ にあるならば、$n-(x+y)$ は $2$ の倍数である。

解説

この問題の中心は、各時刻の経路数を数えることと、偶奇の不変性を見抜くことである。

特に、1回の移動で $x+y$ は必ず $1$ 増えるか $1$ 減るので、時刻が1進むごとに $x+y$ の偶奇も必ず変わる。したがって、時刻 $n$ と座標和 $x+y$ の偶奇は常に一致する。この性質を使うと、(1) の点 $(1,0)$ のように、数え上げる前に到達不可能だと判断できる。

(2) では、単に「原点に戻る」と考えるのではなく、右と左の回数、上と下の回数がそれぞれ等しいという条件に言い換えると数えやすい。

答え

**(1)**

$$ \begin{aligned} P((0,0))&=\frac14,\\ P((1,0))&=0,\\ P((1,1))&=\frac18,\\ P((2,0))&=\frac1{16} \end{aligned}

$$

**(2)**

$$ \frac{9}{64}

$$

**(3)**

時刻 $n$ に駒が点 $(x,y)$ にあるならば、

$$ n-(x+y)

$$

は $2$ の倍数である。