解説

方針・初手

点 $(5,3)$ に到達するには、右方向に正味 $5$、上方向に正味 $3$ だけ進む必要がある。

最短では右に $5$ 回、上に $3$ 回の合計 $8$ 回で到達する。したがって、移動回数が $8$ より少ない場合は不可能であり、また余分な移動は「右左」または「上下」のように $2$ 回単位で打ち消し合うため、移動回数の偶奇も重要である。

解法1

右、左、上、下への移動回数をそれぞれ $r,l,u,d$ とする。

点 $(5,3)$ に到達する条件は、

$$ r-l=5,\qquad u-d=3

$$

であり、さらに $n$ 回移動するから、

$$ r+l+u+d=n

$$

である。

$a_6$ について

点 $(5,3)$ までの最短距離は

$$ 5+3=8

$$

である。よって、$6$ 回の移動では到達できない。

したがって、

$$ a_6=0

$$

である。

$a_9$ について

$(5,3)$ までの最短移動回数は $8$ 回である。最短経路に余分な移動を加える場合、余分な移動は行って戻る形になるため、$2$ 回単位で増える。

したがって、到達可能な移動回数は

$$ 8,10,12,\dots

$$

のように偶数回に限られる。

$9$ 回は奇数回なので到達できない。

よって、

$$ a_9=0

$$

である。

$a_{10}$ について

$10$ 回で点 $(5,3)$ に到達する場合を数える。

条件

$$ r-l=5,\qquad u-d=3

$$

より、

$$ r=l+5,\qquad u=d+3

$$

である。これを

$$ r+l+u+d=10

$$

に代入すると、

$$ (l+5)+l+(d+3)+d=10

$$

となる。整理して、

$$ 2l+2d+8=10

$$

より、

$$ l+d=1

$$

である。

したがって、場合は次の $2$ 通りである。

**(i)**

$l=1,\ d=0$ のとき

このとき、

$$ r=6,\qquad u=3

$$

である。つまり、右 $6$ 回、左 $1$ 回、上 $3$ 回、下 $0$ 回を並べる。

その並べ方は、

$$ \frac{10!}{6!1!3!}=840

$$

である。

**(ii)**

$l=0,\ d=1$ のとき

このとき、

$$ r=5,\qquad u=4

$$

である。つまり、右 $5$ 回、左 $0$ 回、上 $4$ 回、下 $1$ 回を並べる。

その並べ方は、

$$ \frac{10!}{5!4!1!}=1260

$$

である。

よって、

$$ a_{10}=840+1260=2100

$$

である。

解説

この問題では、各方向への移動回数を文字でおくのが基本である。

点 $(5,3)$ に着くには、右と左の差が $5$、上と下の差が $3$ になればよい。つまり、移動の順番ではなく、まず各方向への移動回数の組を決め、その後でそれらを何通りに並べられるかを数える。

また、最短移動回数が $8$ 回であり、余分な移動は必ず $2$ 回単位で増えることから、$6$ 回や $9$ 回では到達できないことがすぐに分かる。

答え

**(1)**

$$ a_6=0

$$

**(2)**

$$ a_9=0

$$

**(3)**

$$ a_{10}=2100

$$