0

2026年 東北大学 理系 第4問

0
0
$$$$
2026年 東北大学 理系 第4問

座標平面において,$x$ 座標も $y$ 座標も整数である点全体の集合上を移動する点 $\mathrm{P}$ がある。時刻 $0$ に点 $\mathrm{P}$ は原点 $\mathrm{O}$ にある。$0$ 以上の整数 $t$ に対し,時刻 $t$ に点 $\mathrm{P}$ が点 $(m,n)$ にあるとき,時刻 $t+1$ での点 $\mathrm{P}$ の位置は $4$ 点
$$ (m+1,n),\quad (m-1,n),\quad (m,n+1),\quad (m,n-1) $$
のいずれかであり,また,どの位置にある確率も $\dfrac{1}{4}$ である。以下の問いに答えよ。
(1) 時刻 $8$ に点 $\mathrm{P}$ が点 $(4,0)$ にある確率を求めよ。
(2) 時刻 $8$ に点 $\mathrm{P}$ が双曲線 $x^2-y^2=16$ 上にある確率を求めよ。
(3) 時刻 $8$ に点 $\mathrm{P}$ が双曲線 $x^2-y^2=16$ 上にあるとき,時刻 $1$,時刻 $2$,$\cdots$,時刻 $7$ のいずれかに点 $\mathrm{P}$ が点 $(4,2)$ にある条件付き確率を求めよ。


1. 問題の構造

1.1 記法と標本空間

  • 一歩の移動を $\mathsf{E}=(1,0)$,$\mathsf{W}=(-1,0)$,$\mathsf{N}=(0,1)$,$\mathsf{S}=(0,-1)$(東・西・北・南)で表す。長さ $t$ の移動列の全体を $\Omega_t=\lbrace\mathsf{E},\mathsf{W},\mathsf{N},\mathsf{S}\rbrace^t$ とし,$\sigma=(\sigma_1,\ldots,\sigma_t)\in\Omega_t$ の時刻 $k$ の位置を $\mathrm{P}_k=\sigma_1+\cdots+\sigma_k=(X_k,Y_k)$($\mathrm{P}_0=\mathrm{O}$)とする。
  • 問題文の推移規則(各時刻に,それまでの経過によらず4点のそれぞれへ確率 $\frac14$ で移る)と乗法定理により,どの $\sigma\in\Omega_8$ も確率 $4^{-8}$ で実現する。以下,時刻 $8$ までで決まる事象を $\Omega_8$ の部分集合と同一視し,$\Pr(E)=|E|/4^8$ とする。
  • $N_t(z)=|\lbrace\sigma\in\Omega_t:\ \mathrm{P}_t=z\rbrace|$ を,原点から $t$ 歩で点 $z$ に至る移動列の数とし,$N_t((x,y))$ を $N_t(x,y)$ とも書く。$K\subset\mathbb{Z}^2$ に対し $N_t(K)=\sum_{z\in K}N_t(z)$ とする。
  • $z=(x,y)$ に対し $\lVert z\rVert_1=|x|+|y|$ とする。
  • 整数 $t\geqq0$,$u$ に対し,$t+u$ が偶数かつ $|u|\leqq t$ のとき $c_t(u)=\binom{t}{(t+u)/2}$,それ以外のとき $c_t(u)=0$ とする。$c_t(u)$ は和が $u$ となる長さ $t$ の $\pm1$ 列の個数であり,$c_t(-u)=c_t(u)$,$\sum_u c_t(u)=2^t$ が成り立つ。なお $\binom{n}{r}={}_n\mathrm{C}_r$ である。
    問題の集合と事象を
    $$ H=\lbrace(x,y)\in\mathbb{Z}^2:\ x^2-y^2=16\rbrace,\qquad B=\lbrace\mathrm{P}_8\in H\rbrace,\qquad A=\bigcup_{t=1}^{7}\lbrace\mathrm{P}_t=(4,2)\rbrace $$
    とおく。求める値は
    $$ \text{(1)}\ \ \frac{N_8(4,0)}{4^8},\qquad \text{(2)}\ \ \Pr(B)=\frac{N_8(H)}{4^8},\qquad \text{(3)}\ \ \Pr(A\mid B)=\frac{|A\cap B|}{|B|} $$
    である。(3) では因子 $4^{-8}$ が約分され,分母は全移動列の数 $4^8$ ではなく $|B|=N_8(H)$ になる。

1.2 到達可能性:距離と偶奇

到達可能性

$t\geqq0$,$z=(x,y)\in\mathbb{Z}^2$ とする。
(i) $N_t(z) > 0$ であるための必要十分条件は,$\lVert z\rVert_1\leqq t$ かつ $x+y\equiv t\pmod 2$ である。
(ii) $\lVert z\rVert_1=t$ のとき,$z$ に至る移動列は,水平方向には $x$ の符号の向きにだけ $|x|$ 回,鉛直方向には $y$ の符号の向きにだけ $|y|$ 回進むものに限られる。特に $N_t(z)=\binom{t}{|x|}$ である。

(i) 一歩で $|x|$,$|y|$ の一方だけがちょうど $1$ 変化するから,$\lVert\mathrm{P}_k\rVert_1$ は一歩ごとに $\pm1$ 変化する。また $X_k+Y_k$ も一歩ごとに $\pm1$ 変化する。よって $\lVert\mathrm{P}_t\rVert_1\leqq t$ と $X_t+Y_t\equiv t\pmod2$ が必要である。逆に条件をみたすとき,$\lVert z\rVert_1$ 歩の最短の移動列の後に $\mathsf{E}\mathsf{W}$ を $(t-\lVert z\rVert_1)/2$ 組(偶奇の条件から整数)続ければ $z$ に至る。
(ii) 東・西・北・南への移動回数を $e,w,n,s$ とすると $x=e-w$,$y=n-s$ であり,
$$ t=e+w+n+s\geqq|e-w|+|n-s|=\lVert z\rVert_1 . $$
等号は $\min(e,w)=\min(n,s)=0$ のときに限る。よって $\lVert z\rVert_1=t$ なら逆向きの移動は現れず,$(e,w,n,s)$ は $z$ から一意に定まる。並べ方は $\binom{t}{|x|}$ 通りである。

時刻 $8$ に到達可能な点は,菱形 $\lVert z\rVert_1\leqq8$ に含まれ $x+y$ が偶数の格子点である。境界 $\lVert z\rVert_1=8$ の上では遠回りが一歩も許されず,経路数は二項係数一つで与えられる。

1.3 双曲線上の格子点

双曲線上の格子点

$$ H=\lbrace(4,0),\ (-4,0),\ (5,3),\ (5,-3),\ (-5,3),\ (-5,-3)\rbrace . $$
これらはすべて時刻 $8$ に到達可能であり,$\lVert(\pm4,0)\rVert_1=4$,$\lVert(\pm5,\pm3)\rVert_1=8$ である。

$u=x+y$,$v=x-y$ とおくと $x^2-y^2=uv$ であり,$u-v=2y$ より $u\equiv v\pmod2$ である。$uv=16$ は偶数だから $u,v$ はともに偶数であり,$u=2u'$,$v=2v'$ とおくと $u'v'=4$ となる。よって
$$ (u,v)\in\lbrace(2,8),\ (4,4),\ (8,2),\ (-2,-8),\ (-4,-4),\ (-8,-2)\rbrace . $$
逆にこれらは $x=\frac{u+v}{2}$,$y=\frac{u-v}{2}$ により,順に整数点 $(5,-3),(4,0),(5,3),(-5,3),(-4,0),(-5,-3)$ を与える。各点で $x+y=u$ は偶数,$\lVert\cdot\rVert_1\leqq8$ であるから, 補題1 により時刻 $8$ に到達可能である。

$H$ の6点は,座標の符号反転で移り合う二つの型に分かれる。

型点個数$\lVert z\rVert_1$時刻 $8$ での経路
I$(\pm4,0)$$2$$4$往復 $2$ 組分の余裕がある
II$(\pm5,\pm3)$$4$$8$全 $8$ 歩が最短経路

歩行は $x$ と $y$ の交換についても対称であるが,交換は $H$ を双曲線 $y^2-x^2=16$ に移すので,$(\pm3,\pm5)$ は $H$ に属さない。$H$ に対して使える対称性は符号反転だけである( 1.5 節 )。

1.4 通過時刻の一意性

通過時刻の一意性

$1\leqq t\leqq7$ のうち $\lbrace\mathrm{P}_t=(4,2)\rbrace\neq\varnothing$ となるのは $t=6$ のみである。したがって
$$ A=\lbrace\mathrm{P}_6=(4,2)\rbrace . $$
さらに時刻 $6$ までの移動は $\mathsf{E}$ 4回と $\mathsf{N}$ 2回の並べ替えに限られ,$N_6(4,2)=\binom{6}{2}=15$ である。

補題1 (i) より $t\geqq\lVert(4,2)\rVert_1=6$ かつ $t\equiv4+2\equiv0\pmod 2$ が必要であり,$1\leqq t\leqq7$ ではこれは $t=6$ に限る。後半は 補題1 (ii) による。

「時刻 $1$ から $7$ のいずれか」という7個の事象の和は,実質的に一つの事象である。同じ移動列が複数の時刻に $(4,2)$ を訪れることもないから,包除原理や初到達時刻による分解は必要ない。

1.5 対称性と経路の連結

$\lbrace\mathsf{E},\mathsf{W},\mathsf{N},\mathsf{S}\rbrace$ を保つ $\mathbb{Z}^2$ の線形変換の全体を $G$ とする。$G$ は $(x,y)\mapsto(\pm x,\pm y),\ (\pm y,\pm x)$ の8個からなる位数 $8$ の二面体群である。$g\in G$ に対し $\sigma\mapsto(g\sigma_1,\ldots,g\sigma_t)$ は $\Omega_t$ の全単射で,終点を $g$ で移す。よって
$$ N_t(gz)=N_t(z)\qquad(g\in G). $$
$H$ を保つのは $G$ のうち符号反転 $(x,y)\mapsto(\pm x,\pm y)$ の4個であり( 1.3 節 ),
$$ N_8(H)=2N_8(4,0)+4N_8(5,3). $$

経路の連結

$0\leqq s\leqq t$,$z\in\mathbb{Z}^2$,$K\subset\mathbb{Z}^2$ に対し,$K-z=\lbrace w-z:\ w\in K\rbrace$ とおくと
$$ \bigl|\lbrace\sigma\in\Omega_t:\ \mathrm{P}_s=z,\ \mathrm{P}_t\in K\rbrace\bigr|=N_s(z)\,N_{t-s}(K-z). $$

$\sigma\mapsto\bigl((\sigma_1,\ldots,\sigma_s),(\sigma_{s+1},\ldots,\sigma_t)\bigr)$ は $\Omega_t$ から $\Omega_s\times\Omega_{t-s}$ への全単射であり,$\mathrm{P}_t=\mathrm{P}_s+(\sigma_{s+1}+\cdots+\sigma_t)$ である。左辺の集合は,前半が $z$ に至り後半の変位が $K-z$ に属する組の全体と一対一に対応する。

補題3 と合わせると
$$ |A\cap B|=N_6(4,2)\,N_2\bigl(H-(4,2)\bigr) $$
である。これは Markov 性の組合せ論的な表現であり,(3) のすべての解法に共通する骨格である。

1.6 斜め座標:移動規則と双曲線の同時分解

$U_t=X_t+Y_t$,$V_t=X_t-Y_t$ とおくと,一歩の変化は次のとおりである。

一歩$\mathsf{E}$$\mathsf{W}$$\mathsf{N}$$\mathsf{S}$
$(\Delta X,\Delta Y)$$(1,0)$$(-1,0)$$(0,1)$$(0,-1)$
$(\Delta U,\Delta V)$$(1,1)$$(-1,-1)$$(1,-1)$$(-1,1)$

4方向と符号の組 $\lbrace1,-1\rbrace^2$ が一対一に対応する。さらに
$$ X_t^2-Y_t^2=U_tV_t,\qquad \lVert(x,y)\rVert_1=\max\bigl(|x+y|,\ |x-y|\bigr) $$
であるから,双曲線 $x^2-y^2=16$ は $uv=16$ に,到達可能な菱形 $\lVert z\rVert_1\leqq t$ は正方形 $|u|\leqq t,\ |v|\leqq t$ に変わる。終点条件と移動規則が,同じ一次形式 $x\pm y$ によって同時に分解される。

経路数の積公式

任意の $t\geqq0$,$(x,y)\in\mathbb{Z}^2$ に対し
$$ N_t(x,y)=c_t(x+y)\,c_t(x-y). $$
また $\Omega_t$ 上の一様分布のもとで $U_t$ と $V_t$ は独立であり,$\Pr(U_t=u)=\Pr(V_t=u)=c_t(u)/2^t$ である。

上の表の対応 $\phi:\lbrace\mathsf{E},\mathsf{W},\mathsf{N},\mathsf{S}\rbrace\to\lbrace1,-1\rbrace^2$,$\phi(d)=(\Delta U,\Delta V)$ は全単射である。よって $\sigma\mapsto(\varepsilon,\eta)$,$(\varepsilon_i,\eta_i)=\phi(\sigma_i)$ は $\Omega_t$ から $\lbrace\pm1\rbrace^t\times\lbrace\pm1\rbrace^t$ への全単射であり,$U_t=\sum_i\varepsilon_i$,$V_t=\sum_i\eta_i$ である。$(x+y,\ x-y)$ は $(x,y)$ を一意に定めるから,$\mathrm{P}_t=(x,y)$ は「$\sum_i\varepsilon_i=x+y$ かつ $\sum_i\eta_i=x-y$」と同値であり,このような $(\varepsilon,\eta)$ の個数は $c_t(x+y)\,c_t(x-y)$ である。一様分布はこの全単射によって $\lbrace\pm1\rbrace^t\times\lbrace\pm1\rbrace^t$ 上の一様分布に移るから,$\varepsilon$ と $\eta$ は独立である。

元の座標 $X_t,Y_t$ は独立ではない。たとえば $\Pr(X_1=0)=\Pr(Y_1=0)=\frac12$ であるが $\Pr(X_1=Y_1=0)=0$ である。独立になるのは斜め座標 $U_t,V_t$ であり,その根拠は「4方向が4つの符号の組に一対一に対応し,しかも等確率である」ことにある( 5.3 節 )。

1.7 作問の設計と解法の導出

以上の構造から,作問の設計は次のように読める(数値設定からの分析であり,出題者の意図についての推定を含む)。

  • 設問の連鎖:$16=4^2$ により (1) の終点 $(4,0)$ は $H$ に属し,(1) は (2) の部分計算になる。(2) の $|B|$ は (3) の分母になる。三つの設問は一つの計数の段階的な拡張として配列されている。
  • 時刻 $8$ の選択:$H$ の点では $x+y$ が偶数であるから( 補題2 の証明),奇数時刻に $H$ 上にある確率は $0$ である。型 I は時刻 $4$ から,型 II は時刻 $8$ から到達可能であり,時刻 $8$ は二つの型が共存する最小の時刻である。しかもそのとき型 II はちょうど到達可能領域の境界上にある。往復の余裕を含む多項係数の和(型 I)と二項係数一つ(型 II)という計算量の異なる二種類の終点が,最小の歩数で同居する設定である。
  • 定数 $16$ と双曲線の形:$x^2-y^2=c$ の格子点は,$uv=c$,$u\equiv v\pmod2$ をみたす整数の組 $(u,v)$ と一対一に対応する。$c=16$ では $u'v'=4$ の分解3通り(符号を含め6通り)となり,符号反転で移り合う2型に整理される。さらに因数 $x\pm y$ は,歩行を独立な二つの一次元歩行に分解する斜め座標そのものである( 1.6 節 )。(2) は $U_8V_8=16$ という独立な2変数の積の条件に帰着する。直接計数でも完答できる一方,構造を見抜けば計算が一行に縮む,という二層の設計と解釈できる。
  • 通過点 $(4,2)$ の選択:$\lVert(4,2)\rVert_1=6$ と偶奇により,「時刻 $1$ から $7$ のいずれか」という和事象が時刻 $6$ の一事象に縮約される( 補題3 )。和事象の形は包除原理や初到達分解を想起させるが,距離と偶奇の確認だけで不要になる。また $(4,2)$ は型 I の $(4,0)$ と型 II の $(5,3)$ のいずれからも $\ell^1$ 距離 $2$ にあり,両方の型が分子に寄与する。$(4,2)$ から $(5,3)$ への単調な延長だけを数えると分子は $30$ となり,誤答 $\frac{15}{896}$ に至る。
  • 条件付き確率の分母:(3) は (2) の結果を分母として再利用させ,条件付けによって標本空間が $B$ に縮むことの理解を確かめている。
    各構造がどの解法を導くかを整理する。
    着目する構造数学的翻訳導かれる解法
    方向別の回数と終点の一次条件多項係数の和,境界での最短経路本解
    一歩の4方向と符号の組の対応斜め座標,二項係数の積別解1,3.2 節
    動く軸の選択と向きの選択の分離水平移動の回数による条件付け参考解1
    最後の一歩による分類隣接4点からの漸化式参考解2
    絶対値の平方差$(\lvert x\rvert+\lvert y\rvert)(\lvert x\rvert-\lvert y\rvert)=16$3.1 節
    通過時刻の一意性と経路の連結終点による分解,Bayes の公式3.3 節

2. 本解:四方向の移動回数による直接計数

2.1 方針

東・西・北・南への移動回数を未知数とし,終点の条件を一次方程式にして多項係数で数える。(2) では $H$ の6点( 補題2 )を符号反転の対称性で2型に整理し,型 II は境界上の最短経路として数える。(3) では距離と偶奇によって通過時刻を $6$ に固定し( 補題3 ),前半6歩と後半2歩の経路数の積をとる( 補題4 )。

2.2 解答

(1)

東・西・北・南への移動回数を非負整数 $e,w,n,s$ とする。$\mathrm{P}_8=(4,0)$ となる条件は
$$ e-w=4,\qquad n-s=0,\qquad e+w+n+s=8 $$
である。$w=k$ とおくと $e=4+k$,$n=s=2-k$ であり,$n\geqq0$ より $k\in\lbrace0,1,2\rbrace$ である。回数の組を固定したときの移動列の数は多項係数で与えられるから
$$ \begin{aligned} N_8(4,0)&=\sum_{k=0}^{2}\frac{8!}{(4+k)!\,k!\,\bigl((2-k)!\bigr)^2} =\frac{8!}{4!\,2!\,2!}+\frac{8!}{5!\,1!\,1!\,1!}+\frac{8!}{6!\,2!}\\ &=420+336+28=784 . \end{aligned} $$
したがって
$$ \Pr\bigl(\mathrm{P}_8=(4,0)\bigr)=\frac{784}{4^8}=\frac{49}{4096}. $$

(2)

$x^2-y^2=(x+y)(x-y)=16$ において,$x+y$ と $x-y$ は差が $2y$ であるから偶奇が一致し,積が偶数であるからともに偶数である。$\frac{x+y}{2}\cdot\frac{x-y}{2}=4$ より
$$ H=\lbrace(\pm4,0),\ (\pm5,\pm3)\rbrace\qquad(\text{複号任意,6点}) $$
である( 補題2 )。符号反転 $(x,y)\mapsto(\pm x,\pm y)$ は東西・南北の入れ替えによって移動列の全単射を与えるから,$N_8(-4,0)=N_8(4,0)=784$,$N_8(\pm5,\pm3)=N_8(5,3)$ である。
$(5,3)$ については,$e-w=5$,$n-s=3$ の和と $e+w+n+s=8$ を比べて $2(w+s)=0$,すなわち $w=s=0$,$e=5$,$n=3$ を得る。よって
$$ N_8(5,3)=\binom{8}{3}=56 . $$
ゆえに
$$ N_8(H)=2\cdot784+4\cdot56=1792,\qquad \Pr(B)=\frac{1792}{4^8}=\frac{7}{256}. $$

(3)

一歩で $|x|+|y|$ は $1$ だけ増減し,$x+y$ の偶奇は毎回入れ替わる。$(4,2)$ では $|x|+|y|=6$,$x+y=6$ であるから,$(4,2)$ にいる時刻は $6$ 以上の偶数である。よって時刻 $1$ から $7$ のうちで可能なのは時刻 $6$ だけであり,$A=\lbrace\mathrm{P}_6=(4,2)\rbrace$ である。時刻 $6$ までの移動は $\mathsf{E}$ 4回と $\mathsf{N}$ 2回に限られ,その並べ方は
$$ N_6(4,2)=\binom{6}{2}=15 $$
通りである。
次に,時刻 $6$ に $(4,2)$ にいて,残り2歩で $H$ に至る移動を数える。2歩で到達できるのは $(4,2)$ からの $\ell^1$ 距離が $2$ 以下の点であり,$H$ の各点との距離は
$$ (4,0):\ 2,\qquad (5,3):\ 2,\qquad (5,-3):\ 6,\qquad (-4,0):\ 10,\qquad (-5,3):\ 10,\qquad (-5,-3):\ 14 $$
である。距離がちょうど $2$ の点へは最短経路に限られるから,最後の2歩は
$$ (4,0)\ \text{へ}:\ \mathsf{S}\mathsf{S}\ \ (1\ \text{通り}),\qquad (5,3)\ \text{へ}:\ \mathsf{E}\mathsf{N},\ \mathsf{N}\mathsf{E}\ \ (2\ \text{通り}) $$
の3通りである。前半6歩と後半2歩は独立に選べるから( 補題4 )
$$ |A\cap B|=15\times3=45 . $$
したがって
$$ \Pr(A\mid B)=\frac{\Pr(A\cap B)}{\Pr(B)}=\frac{45/4^8}{1792/4^8}=\frac{45}{1792}. $$

解答のまとめ

設問経路数確率
(1)$N_8(4,0)=784$$\dfrac{49}{4096}$
(2)$N_8(H)=1792$$\dfrac{7}{256}$
(3)$\lvert A\cap B\rvert=45$$\dfrac{45}{1792}$

2.3 検証・検算

    1. の値は $784=28^2=\binom{8}{2}^2$ である。これは 補題5 による $N_8(4,0)=c_8(4)^2$ と一致し,$\Pr\bigl(\mathrm{P}_8=(4,0)\bigr)=\bigl(\frac{7}{64}\bigr)^2$ は,一次元の歩行 $U_8$,$V_8$ がそれぞれ $4$ に至る確率 $\frac{28}{256}=\frac{7}{64}$ の積である。
    1. は $N_8(H)=2\cdot28^2+4\cdot2\cdot28=2\cdot28\cdot(28+4)=64\binom{8}{2}$ と整理でき,$\Pr(B)=\binom{8}{2}\big/2^{10}=\frac{7}{256}$ と再計算できる。この簡約は数値 $28+4=32$ に依存するもので,一般の時刻・定数では成り立たない。
    1. は Bayes の公式でも確かめられる。 補題4 より $|A|=N_6(4,2)\cdot4^2=240$,$|A\cap B|=15\cdot3$ であるから $\Pr(A)=\frac{15}{4096}$,$\Pr(B\mid A)=\frac{3}{16}$ であり,$\Pr(A\mid B)=\Pr(A)\Pr(B\mid A)/\Pr(B)=\frac{45}{1792}$ を得る。比 $\Pr(A\mid B)/\Pr(A)=\frac{48}{7} > 1$ は,原点から遠い終点への到達という条件が,遠方の点 $(4,2)$ の通過を起こりやすくすることと整合する。
  • 全 $4^8=65536$ 通りの移動列を計算機で列挙すると,$N_8(4,0)=784$,$|B|=1792$,$|A|=240$,$|A\cap B|=45$ を得て,すべて一致する。
  • 典型的な誤り:最後の2歩を $\mathsf{E}\mathsf{N},\mathsf{N}\mathsf{E}$ に限ると分子が $30$ となり $\frac{15}{896}$ を得る。分母を $4^8$ とすると $\frac{45}{65536}$ を得る。交換の対称性を $H$ に適用すると $(\pm3,\pm5)$ を誤って加える。

3. 別解と参考解

3.1〜3.3 節は本解の一部を置き換える別証・他の導出,3.4 節は経路の表現を取り替える別解,3.5〜3.6 節は計算の原理を変える参考解である。

3.1 到達可能な $H$ の点の別証:絶対値の平方差

着想・方針

$x^2-y^2=|x|^2-|y|^2=(|x|+|y|)(|x|-|y|)$ の第1因子は $\lVert z\rVert_1$ そのものである。因数分解と到達可能性が同じ量で結び付き,点の決定と経路の型の判定を同時に行える。

解答

$z=(x,y)\in H$ とし,$r=|x|+|y|$,$q=|x|-|y|$ とおく。$rq=16$ と $r\geqq0$ より $r > 0$,$q > 0$ であり,$q\leqq r$ である。$r-q=2|y|$ より $r\equiv q\pmod2$ であり,$rq$ は偶数であるから $r,q$ はともに偶数である。$rq=16$,$0 < q\leqq r$ をみたす偶数の組は $(r,q)=(4,4),\ (8,2)$ のみであるから
$$ (|x|,|y|)=\Bigl(\frac{r+q}{2},\ \frac{r-q}{2}\Bigr)=(4,0),\ (5,3). $$
よって $H=\lbrace(\pm4,0),(\pm5,\pm3)\rbrace$ である。さらに $\lVert z\rVert_1=r\in\lbrace4,8\rbrace$,$x+y\equiv r\equiv0\pmod2$ であるから, 補題1 によりいずれも時刻 $8$ に到達可能である。

検証・検算

$r$ の値がそのまま型を与える。$r=4$ は余裕 $8-4=4$(往復2組),$r=8$ は余裕 $0$(最短経路)であり, 1.3 節 の表と一致する。$(r,q)=(16,1)$ は偶奇の条件で除かれるから,到達可能性 $r\leqq8$ を用いなくても $H$ 全体が決まる。

3.2 積公式の別証:母関数の因数分解

着想・方針

一歩を単項式 $z^{\pm1}$,$w^{\pm1}$ で表すと,$t$ 歩の経路数は Laurent 多項式の $t$ 乗の係数になる。一歩の多項式が二つの一変数多項式の積に分解されれば, 補題5 は係数の積として従う。

解答

$F(z,w)=z+z^{-1}+w+w^{-1}$ とおく。$F^t$ を展開すると,$t$ 個の因子のそれぞれから一歩を選ぶ選び方が移動列に対応するから
$$ F(z,w)^t=\sum_{(x,y)\in\mathbb{Z}^2}N_t(x,y)\,z^xw^y . $$
$z=ab$,$w=ab^{-1}$ を代入すると $z^xw^y=a^{x+y}b^{x-y}$ であり,$(x,y)\mapsto(x+y,\ x-y)$ は単射であるから,相異なる単項式は相異なる単項式に移り,係数は保たれる。一方
$$ F(ab,ab^{-1})=ab+a^{-1}b^{-1}+ab^{-1}+a^{-1}b=(a+a^{-1})(b+b^{-1}) $$
であり,$(a+a^{-1})^t=\sum_u c_t(u)\,a^u$ であるから
$$ \sum_{(x,y)\in\mathbb{Z}^2}N_t(x,y)\,a^{x+y}b^{x-y}=\Bigl(\sum_{u}c_t(u)\,a^u\Bigr)\Bigl(\sum_{v}c_t(v)\,b^v\Bigr). $$
両辺の $a^{x+y}b^{x-y}$ の係数を比べて $N_t(x,y)=c_t(x+y)\,c_t(x-y)$ を得る。右辺で $c_t(u)c_t(v)\neq0$ となるのは $u\equiv v\equiv t\pmod 2$ のときに限るから,右辺の単項式はすべて左辺の形 $a^{x+y}b^{x-y}$ をもつ。

検証・検算

$t=1$ では $(a+a^{-1})(b+b^{-1})$ の4項が4方向に対応する。$t=2$,$(x,y)=(0,0)$ では $c_2(0)^2=4$ となり,移動列 $\mathsf{E}\mathsf{W},\mathsf{W}\mathsf{E},\mathsf{N}\mathsf{S},\mathsf{S}\mathsf{N}$ の数と一致する。

3.3 (3) の他の導出:終点による分解と Bayes の公式

着想・方針

$B$ は6個の終点に分かれる。終点を固定すれば,経由の条件付き確率は「前半の経路数 × 後半の経路数 ÷ 全体の経路数」となり,これを $B$ のもとでの終点の分布で平均すればよい。あるいは $\Pr(A)$,$\Pr(B\mid A)$ を先に求めて Bayes の公式を用いる。

解答

終点を固定した通過確率

$0\leqq s\leqq T$,$z,w\in\mathbb{Z}^2$,$N_T(w) > 0$ とする。$\Omega_T$ 上の一様分布のもとで
$$ \Pr(\mathrm{P}_s=z\mid \mathrm{P}_T=w)=\frac{N_s(z)\,N_{T-s}(w-z)}{N_T(w)} . $$

補題4 で $t=T$,$K=\lbrace w\rbrace$ とした式の両辺を $N_T(w)$ で割ればよい。

補題3 より $A=\lbrace\mathrm{P}_6=(4,2)\rbrace$ である。$w\in H$ に対し $w-(4,2)$ は
$$ (0,-2),\quad (1,1),\quad (1,-5),\quad (-8,-2),\quad (-9,1),\quad (-9,-5) $$
であり,$N_2$ が正となるのは最初の2つで,$N_2(0,-2)=1$,$N_2(1,1)=2$ である。よって
$$ \Pr\bigl(A\mid\mathrm{P}_8=(4,0)\bigr)=\frac{15\cdot1}{784}=\frac{15}{784},\qquad \Pr\bigl(A\mid\mathrm{P}_8=(5,3)\bigr)=\frac{15\cdot2}{56}=\frac{15}{28} $$
であり,$H$ の他の4点では $0$ である。$\Pr(\mathrm{P}_8=w\mid B)=N_8(w)/1792$ で重み付けると,全確率の公式より
$$ \Pr(A\mid B)=\frac{784}{1792}\cdot\frac{15}{784}+\frac{56}{1792}\cdot\frac{15}{28}=\frac{15}{1792}+\frac{30}{1792}=\frac{45}{1792}. $$
Bayes の公式による場合, 補題4 より $|A|=15\cdot4^2$,$|A\cap B|=15\cdot3$ であるから $\Pr(A)=\frac{15}{4^6}$,$\Pr(B\mid A)=\frac{3}{16}$ であり
$$ \Pr(A\mid B)=\frac{\Pr(A)\,\Pr(B\mid A)}{\Pr(B)}=\frac{\frac{15}{4096}\cdot\frac{3}{16}}{\frac{7}{256}}=\frac{45}{1792}. $$

検証・検算

条件 $B$ のもとで終点が型 I にある確率は $\frac{2\cdot784}{1792}=\frac78$ であるが,分子 $45$ への寄与は型 I が $15$,型 II が $30$ である。型 II の終点 $(5,3)$ への経路は単調な格子路 $\binom{8}{3}=56$ 本であり,そのうち $(4,2)$ を通るものは $\binom{6}{2}\binom{2}{1}=30$ 本である(超幾何分布, 5.4 節 )。寄与の比 $15:30$ は,本解の後半2歩の内訳 $1:2$ に一致する。

3.4 別解1:斜め座標による二つの独立な歩行

着想・方針

双曲線の因数 $x+y$,$x-y$ を新しい座標にとると,一歩は二つの独立な $\pm1$ の選択になる( 1.6 節 )。経路数は二項係数の積 $c_t(x+y)\,c_t(x-y)$ となり,(2) は $U_8V_8=16$ をみたす偶数の組の列挙に帰着する。$H$ の決定と経路数の計算が一度に済む。

解答

$U_t=X_t+Y_t$,$V_t=X_t-Y_t$ とする。一歩ごとの $(\Delta U,\Delta V)$ は $(1,1),(-1,-1),(1,-1),(-1,1)$ のいずれかで,4方向と一対一に対応する。 補題5 より,$t$ 歩で $(x,y)$ に至る移動列の数は
$$ N_t(x,y)=c_t(x+y)\,c_t(x-y) $$
である。時刻 $8$ の一次元の経路数 $c_8(u)$ は次のとおりである($u$ が奇数のときは $0$)。

$u$$\pm8$$\pm6$$\pm4$$\pm2$$0$
$c_8(u)$$1$$8$$28$$56$$70$
(1)

$(x,y)=(4,0)$ は $(u,v)=(4,4)$ に対応するから
$$ N_8(4,0)=c_8(4)^2=\binom{8}{6}^2=784,\qquad \Pr\bigl(\mathrm{P}_8=(4,0)\bigr)=\frac{784}{4^8}=\frac{49}{4096}. $$

(2)

$B=\lbrace U_8V_8=16\rbrace$ である。$U_8,V_8$ は偶数で絶対値は $8$ 以下であるから,$uv=16$ をみたす組は
$$ (u,v)=(2,8),\ (4,4),\ (8,2),\ (-2,-8),\ (-4,-4),\ (-8,-2) $$
に限られる。$c_8(-u)=c_8(u)$ より
$$ N_8(H)=2\bigl(c_8(2)c_8(8)+c_8(4)^2+c_8(8)c_8(2)\bigr)=2(56+784+56)=1792,\qquad \Pr(B)=\frac{7}{256}. $$

(3)

補題3 より $A=\lbrace\mathrm{P}_6=(4,2)\rbrace=\lbrace(U_6,V_6)=(6,2)\rbrace$ であり
$$ N_6(4,2)=c_6(6)\,c_6(2)=1\cdot15=15 . $$
残り2歩での $U,V$ の増分を $\alpha,\beta\in\lbrace-2,0,2\rbrace$ とすると,その2歩の移動列の数は $c_2(\alpha)\,c_2(\beta)$ であり,$c_2(\pm2)=1$,$c_2(0)=2$ である。$(U_8,V_8)$ の値ごとの2歩の移動列の数は次の表のとおりである。

2歩の移動列の数$V_8=0$$V_8=2$$V_8=4$
$U_8=4$$1$$2$$1$
$U_8=6$$2$$4$$2$
$U_8=8$$1$$2$$1$

$U_8V_8=16$ をみたすのは $(4,4)$ と $(8,2)$ のみであり($U_8=6$ では $V_8=\frac83$ となり不適),その和は $1+2=3$ である。 補題4 より
$$ |A\cap B|=15\cdot3=45,\qquad \Pr(A\mid B)=\frac{45}{1792}. $$

検証・検算

  • 3×3 の表は $(1,2,1)$ と $(1,2,1)$ の外積であり,総和は $4^2=16$ である。
  • $(t,x,y)=(8,5,3)$ では $c_8(8)c_8(2)=56$ となり,本解の $\binom{8}{3}$ と一致する。$(7,4,1)$ では $c_7(5)c_7(3)=7\cdot21=147$ となり, 3.6 節 の漸化式による値と一致する。
    1. の確率は $\Pr(U_8=4)\Pr(V_8=4)=\bigl(\frac{28}{256}\bigr)^2$ であり,独立性と整合する。

3.5 参考解1:水平移動回数による時間分割

着想・方針

8歩のうち水平に動く時刻を先に選ぶと,残る自由度は「東西の向き」と「南北の向き」という二つの一次元の符号選択に分かれる。空間の座標ではなく時間を分割して,二つの一次元歩行に帰着させる方法である。

解答

時間分割公式

$$ N_t(x,y)=\sum_{k=0}^{t}\binom{t}{k}\,c_k(x)\,c_{t-k}(y). $$

移動列 $\sigma\in\Omega_t$ に,水平に動く時刻の集合 $J\subset\lbrace1,\ldots,t\rbrace$,$J$ 上の東西の符号列,$J$ の補集合上の南北の符号列の三つ組を対応させると全単射である。$|J|=k$ のとき終点が $(x,y)$ となるのは,東西の符号の和が $x$,南北の符号の和が $y$ のときであり,その個数は $\binom{t}{k}c_k(x)\,c_{t-k}(y)$ である。

確率の言葉では,水平移動の回数 $K_t$ は二項分布 $\mathrm{Bin}(t,\frac12)$ に従い,$K_t=k$ のもとで水平・鉛直の成分は長さ $k$,$t-k$ の独立な一次元歩行である。

(1)

$c_k(4)\neq0$ には $k\geqq4$ かつ $k$ が偶数,$c_{8-k}(0)\neq0$ には $8-k$ が偶数であることが必要であるから $k\in\lbrace4,6,8\rbrace$ であり
$$ \begin{aligned} N_8(4,0)&=\binom84c_4(4)\,c_4(0)+\binom86c_6(4)\,c_2(0)+\binom88c_8(4)\,c_0(0)\\ &=70\cdot1\cdot6+28\cdot6\cdot2+1\cdot28\cdot1=420+336+28=784 . \end{aligned} $$

(2)

$c_k(5)\neq0$ には $k\geqq5$,$c_{8-k}(3)\neq0$ には $8-k\geqq3$ が必要であるから $k=5$ のみであり,$N_8(5,3)=\binom85c_5(5)\,c_3(3)=56$ である。対称性より $N_8(H)=2\cdot784+4\cdot56=1792$。

(3)

$N_6(4,2)=\binom64c_4(4)\,c_2(2)=15$ である。後半2歩については $N_2(0,-2)=\binom20c_0(0)\,c_2(-2)=1$,$N_2(1,1)=\binom21c_1(1)\,c_1(1)=2$ であり,$H-(4,2)$ の他の点では $0$ である。よって $|A\cap B|=15\cdot3=45$,$\Pr(A\mid B)=\frac{45}{1792}$。

検証・検算

$k=e+w$ とすると $\binom{t}{k}\binom{k}{e}\binom{t-k}{n}=\dfrac{t!}{e!\,w!\,n!\,s!}$ であるから, 補題7 の各項は本解の多項係数の各項に一致する。実際 $k=4,6,8$ の項 $420,336,28$ は,本解の $w=0,1,2$ の項に順に対応する。参考解1は本解と同じ経路の集合を「軸の選択 → 向きの選択」の順に分類し直したものであり,計算の原理は本解に近い。

3.6 参考解2:漸化式による状態伝播

着想・方針

時刻 $t+1$ に点 $z$ にいる経路は,時刻 $t$ に $z$ の隣接4点のいずれかにいる。この局所的な規則を時刻 $0$ から積み上げる。(3) では終点側から逆向きに数える関数を併用し,時刻 $6$ で接続する。

解答

$f_t(z)=N_t(z)$ とおく。最後の一歩で分類すると($\Omega_{t+1}=\Omega_t\times\lbrace\mathsf{E},\mathsf{W},\mathsf{N},\mathsf{S}\rbrace$)
$$ f_0(z)=\begin{cases}1 & (z=\mathrm{O})\\ 0 & (z\neq\mathrm{O})\end{cases},\qquad f_{t+1}(x,y)=f_t(x-1,y)+f_t(x+1,y)+f_t(x,y-1)+f_t(x,y+1). $$
$G$ による不変性( 1.5 節 )から,$0\leqq y\leqq x$ の代表点だけを保持すればよい。$\rho(a,b)=\bigl(\max(|a|,|b|),\ \min(|a|,|b|)\bigr)$ として漸化式を $f_{t+1}(z)=\sum_{d}f_t\bigl(\rho(z+d)\bigr)$ と読み替える($d$ は4方向)。たとえば $x\geqq1$ に対し
$$ f_{t+1}(x,0)=f_t(x-1,0)+f_t(x+1,0)+2f_t(x,1),\qquad f_{t+1}(x,x)=2f_t(x,x-1)+2f_t(x+1,x) $$
であり,軸上と対角線上で係数 $2$ が現れる。時刻 $7$ までの値は次のとおりである(「重み」は代表点の $G$ 軌道に属する点の個数)。

$(x,y)$重み$t=0$$t=2$$t=4$$t=6$
$(0,0)$$1$$1$$4$$36$$400$
$(1,1)$$4$$0$$2$$24$$300$
$(2,0)$$4$$0$$1$$16$$225$
$(2,2)$$4$$0$$0$$6$$120$
$(3,1)$$8$$0$$0$$4$$90$
$(4,0)$$4$$0$$0$$1$$36$
$(3,3)$$4$$0$$0$$0$$20$
$(4,2)$$8$$0$$0$$0$$15$
$(5,1)$$8$$0$$0$$0$$6$
$(6,0)$$4$$0$$0$$0$$1$
重み付き和—$1$$16$$256$$4096$
$(x,y)$重み$t=1$$t=3$$t=5$$t=7$
:-::-::-::-::-::-:
$(1,0)$$4$$1$$9$$100$$1225$
$(2,1)$$8$$0$$3$$50$$735$
$(3,0)$$4$$0$$1$$25$$441$
$(3,2)$$8$$0$$0$$10$$245$
$(4,1)$$8$$0$$0$$5$$147$
$(5,0)$$4$$0$$0$$1$$49$
$(4,3)$$8$$0$$0$$0$$35$
$(5,2)$$8$$0$$0$$0$$21$
$(6,1)$$8$$0$$0$$0$$7$
$(7,0)$$4$$0$$0$$0$$1$
重み付き和—$4$$64$$1024$$16384$
(1)

$$ f_8(4,0)=f_7(3,0)+f_7(5,0)+2f_7(4,1)=441+49+2\cdot147=784 . $$

(2)

$f_7(6,3)$,$f_7(5,4)$ は $\lVert\cdot\rVert_1=9 > 7$ より $0$ であるから
$$ f_8(5,3)=f_7(4,3)+f_7(6,3)+f_7(5,2)+f_7(5,4)=35+0+21+0=56, $$
$N_8(H)=2\cdot784+4\cdot56=1792$ である。

(3)

時刻 $t$ に点 $z$ にいるとき,残り $8-t$ 歩で $H$ に至る移動列の数を $g_t(z)$ とする。最初の一歩で分類して
$$ g_8(z)=\begin{cases}1 & (z\in H)\\ 0 & (z\notin H)\end{cases},\qquad g_t(x,y)=g_{t+1}(x+1,y)+g_{t+1}(x-1,y)+g_{t+1}(x,y+1)+g_{t+1}(x,y-1). $$
$g_7(z)$ は $z$ の隣接点のうち $H$ に属するものの個数であり,$(4,2)$ の隣接点では $g_7(5,2)=1$(隣接点 $(5,3)$),$g_7(4,3)=1$($(5,3)$),$g_7(4,1)=1$($(4,0)$),$g_7(3,2)=0$ である。よって $g_6(4,2)=1+1+1+0=3$。 補題4 より
$$ |A\cap B|=f_6(4,2)\,g_6(4,2)=15\cdot3=45,\qquad \Pr(A\mid B)=\frac{f_6(4,2)\,g_6(4,2)}{g_0(\mathrm{O})}=\frac{45}{1792}. $$
ここで $g_0(\mathrm{O})=N_8(H)=1792$ である。

検証・検算

  • 表の各値は 補題5 の $c_t(x+y)\,c_t(x-y)$ と一致する。たとえば $f_7(4,1)=c_7(5)\,c_7(3)=7\cdot21=147$,$f_6(3,3)=c_6(6)\,c_6(0)=1\cdot20=20$。
  • 各列の重み付き和が $4^t$ に一致することは,確率の総和が $1$ であることに相当する。
  • 漸化式は経路数についての式であるから係数 $\frac14$ は付かない。確率 $p_t=f_t/4^t$ を伝播させる場合に限り,各項に $\frac14$ が付く。

3.7 同じ系列に属する変形

以下は独立の解法とは数えず,既出の解法の表現違いまたは部分的な短縮として扱う。

本解の系列

  • $N_8(5,3)=\binom83$ を「右へ5,上へ3の単調な格子路の数」とみる見方: 補題1 (ii) の言い換えである。
  • 回数の組ごとの確率を多項分布 $\dfrac{8!}{e!\,w!\,n!\,s!}\bigl(\frac14\bigr)^8$ として足す方法:同じ計算を確率で書いたものである。

別解1の系列(独立化)

  • 方向の二群:「$\mathsf{E}$ または $\mathsf{N}$」の回数 $C_t$ と「$\mathsf{E}$ または $\mathsf{S}$」の回数 $D_t$ は独立に $\mathrm{Bin}(t,\frac12)$ に従い,$U_t=2C_t-t$,$V_t=2D_t-t$,$X_t=C_t+D_t-t$,$Y_t=C_t-D_t$ が成り立つ。
  • 一歩の和分解:$\lbrace\mathsf{E},\mathsf{W},\mathsf{N},\mathsf{S}\rbrace=\lbrace\mathsf{E},\mathsf{N}\rbrace+\lbrace(0,0),(-1,-1)\rbrace$(和の表し方は一意)。母関数では $z+z^{-1}+w+w^{-1}=(z+w)(1+z^{-1}w^{-1})$ であり,$N_t(x,y)=\binom{t}{(t+x-y)/2}\binom{t}{(t-x-y)/2}$ を得る。$c_t$ の対称性により 補題5 と同じ式である。
  • 斜めの半歩:$\boldsymbol{a}=(\frac12,\frac12)$,$\boldsymbol{b}=(\frac12,-\frac12)$ とすると,一歩は $\varepsilon\boldsymbol{a}+\eta\boldsymbol{b}$($\varepsilon,\eta=\pm1$)と一意に書ける。3.2 節の代入 $z=ab$,$w=ab^{-1}$ はこの分解の母関数表示である。
  • 複素数:一歩を $\lbrace1,-1,i,-i\rbrace$ とみて $1+i$ 倍すると $\lbrace\pm1\pm i\rbrace$ となり,$(1+i)(x+iy)$ の実部 $x-y$ と虚部 $x+y$ が独立な符号の和になる。
  • 特性関数:$\frac12(\cos\theta+\cos\varphi)=\cos\frac{\theta+\varphi}{2}\cos\frac{\theta-\varphi}{2}$(和積公式)による分離( 5.6 節 )。
  • 二枚の硬貨:一方の硬貨で直線 $y=x$ の方向に,他方で $y=-x$ の方向に半歩ずつ動くとみるモデル。
  • 外積表:$\bigl(c_t(u)\,c_t(v)\bigr)_{u,v}$ を二つのパスカルの三角形の行の外積とみる見方( 5.2 節 )。
  • 中心化した二項変数の積:$X_t^2-Y_t^2$ は,独立な $\xi,\zeta\sim\mathrm{Bin}(t,\frac12)$ による $(2\xi-t)(2\zeta-t)$ と同分布である。

参考解2の系列

  • 紙の上の二次元パスカルの三角形:対称性で $0\leqq y\leqq x$ の部分だけに書き込む図上計算は,参考解2そのものである。
  • 推移行列の累乗,離散熱方程式( 5.7 節 ):同じ漸化式の線形代数的・解析的な表現である。

(3) と $H$ の決定の系列

  • 3.3 節の終点による分解と Bayes の公式,参考解2の後ろ向きの関数 $g_t$ は,いずれも 補題4 の表現違いである。
  • $x^2=y^2+4^2$ を直角三角形とみて $(3,4,5)$ を思い付く方法:発見法としては有効であるが,証明としては 補題2 の因数分解と同じ整数条件を扱っている。

採用しない方法

  • 反射原理・包除原理・初到達時刻による分解:通過時刻が $6$ に限られる( 補題3 )ため不要である。
  • マルチンゲール:$X_t^2-Y_t^2$ はマルチンゲールであるが( 5.5 節 ),期待値が $0$ という情報は $\Pr(X_8^2-Y_8^2=16)$ を決めない。
  • $Q_t=X_t^2-Y_t^2$ や $\lVert\mathrm{P}_t\rVert_1$ だけを状態とする方法:Markov 連鎖にならない。時刻 $2$ の $(0,0)$ と $(1,1)$ はともに $Q=0$ であるが,次の $Q$ の分布は $\lbrace\pm1\rbrace$ 上の一様分布と $\lbrace\pm1,\pm3\rbrace$ 上の一様分布で異なる。$(2,0)$ と $(1,1)$ はともに $\lVert\cdot\rVert_1=2$ であるが,次に $3$ となる確率は $\frac34$ と $\frac12$ で異なる。
  • 中心極限定理や Brown 運動による近似,Fourier 逆変換の積分,留数計算:近似であるか,同じ因数分解をより重い道具で表すにとどまる。
  • 元の座標のままで推移作用素をテンソル積に分解する方法:誤りである( 5.6 節 )。

3.8 解法の比較

解法主に利用する構造対象範囲長所注意点
本解方向別の回数,境界での最短経路,連結全設問高校問題文からの発想距離が最短,再現性が高い(1) の3通りの場合分け
3.1 節絶対値の平方差$H$ の決定高校点と経路の型を同時に得る符号の復元
3.2 節一歩の母関数の因数分解補題5高校〜大学積公式が一行で従う係数比較の正当化(単射性)
3.3 節終点による分解,Bayes の公式(3)高校分子の内訳が見える終点の条件付き分布の重み
別解1斜め座標,独立性全設問高校(1)(2) を二項係数の積で一括処理し,$H$ の決定も兼ねる独立性の根拠の明示
参考解1動く軸への条件付け全設問高校多項係数を二項係数に分解する本解の項の並べ替えにとどまる
参考解2局所遷移,二面体群の対称性全設問高校規則や終点集合の変更に強い表の作成に手間がかかる

試験場での第一選択は本解である。発想の飛躍がなく,(1) から (3) までが同じ計数の延長上にある。別解1は最も構造的であり,(1)(2) を二項係数の積に圧縮し,$H$ の決定も同時に行う。参考解1は本解と計算の原理が近い。参考解2は本問では計算量が多いが,移動規則や終点集合が不規則な問題へそのまま拡張できる。(3) の処理はすべての解法で共通であり,通過時刻の一意化と経路の連結に尽きる。


4. 汎用的な探索手順

本問から,「格子上の等確率な歩行について,終点や経由点の条件のもとでの確率を求める」問題に対する探索手順を抽出する。

4.1 解法と構造の対応

各解法が,1 節で抽出した構造のどれをどの形で用いるかを横断的に整理する。

構造本解別解1参考解1参考解2
距離と偶奇(補題1)用いる$c_t$ の定義に内蔵$c_k$ の定義に内蔵到達不能点を $0$ とする
$H$ の決定(補題2)因数分解$U_8V_8=16$ として同時に処理因数分解因数分解
符号反転の対称性用いる$c_t(-u)=c_t(u)$ として用いる二面体群全体を用いる
境界での最短経路型 II で用いる$c_8(\pm8)=1$ として$k=5$ のみとして用いない
通過時刻の一意性(補題3)用いる用いる用いる用いる
経路の連結(補題4)前半 × 後半前半 × 外積表前半 × 後半$f_6\cdot g_6$
独立化(補題5)用いない中核軸ごとの条件付き独立用いない

4.2 意思決定の流れ

  1. 標本空間を固定する。各歩が等確率なら,確率は経路数の比である。条件付き確率は $\Pr(A\cap B)/\Pr(B)$ と書き,分母の集合を最初に確定する。等確率でなければ,各経路の確率を重みとして足す。
  2. 計算の前に到達可能性で削る。距離の下界と偶奇(市松模様の塗り分け)で,終点と時刻の候補を絞る。距離の等号が成り立つ点では最短経路しか許されず,二項係数一つで数えられる。
  3. 終点集合を整数論的に確定する。多項式の条件は因数分解し,偶奇と約数の組で格子点を有限個に絞る。対称性は,歩行と終点集合の両方が持つものだけを用いる。
  4. 経由条件を時刻で分解する。「いずれかの時刻」は可能な時刻を列挙し,一つに定まれば連結( 補題4 )により前半と後半の積をとる。複数の時刻が残るときに初めて,初到達時刻による分解や包除原理を検討する。
  5. 計数法を選ぶ。方向別の回数の組が少数なら多項係数(本解)。一歩が独立な二択の組に分解でき,しかも終点条件がその座標で簡単になるなら座標の取り替え(別解1)。軸の選択で自然に分かれるなら時間分割(参考解1)。終点集合や移動規則が不規則なら漸化式(参考解2)。
  6. 終点で条件付ける問題では,終点ごとの条件付き確率(ブリッジ)を求めて終点の分布で平均する見方も持つ( 3.3 節 )。
  7. 検算する。別の計数法による再計算,重み付き総和 $4^t$,閉じた式(二項係数の積)との照合,Bayes の公式による逆算,条件付けによる確率の増減の向きを確かめる。

4.3 症状と有効な表現

症状検討する表現・道具本問での例
終点が到達領域の境界上にある最短経路,二項係数一つ型 II の点 $(\pm5,\pm3)$
終点条件が $x\pm y$ で書ける斜め座標,独立な二項分布(2):$U_8V_8=16$
二次の不定方程式が終点を与える因数分解,偶奇,約数の組補題2,3.1 節
「いずれかの時刻」の和事象到達可能な時刻の列挙補題3
経由点と終点の両方の条件経路の連結,終点による分解(3),3.3 節
方向回数の場合分けが増える時間分割,母関数参考解1,3.2 節
終点集合や移動規則が不規則前向き・後ろ向きの漸化式参考解2
条件付き確率分母の集合の固定,Bayes の公式(3),2.3 節

4.4 一般化と作問への応用

補題5 と $(x,y)\leftrightarrow(x+y,\ x-y)$ の対応から,任意の整数 $c\neq0$ と $T\geqq1$ について
$$ \Pr\bigl(X_T^2-Y_T^2=c\bigr)=\frac{1}{4^T}\sum_{\substack{(u,v)\in\mathbb{Z}^2\\ uv=c}}c_T(u)\,c_T(v) $$
が成り立つ。$c_T(u)\,c_T(v)\neq0$ となるのは $u\equiv v\equiv T\pmod2$,$|u|\leqq T$,$|v|\leqq T$ のときに限るから,和の各項は自動的に格子点に対応する。ここから次が従う。

  • $c\equiv2\pmod4$ なら $x^2-y^2=c$ は格子点をもたず,確率はつねに $0$ である。
  • $c$ が奇数なら $u,v$ は奇数であり,$T$ が偶数のとき確率は $0$ である。$c\equiv0\pmod4$ なら $u,v$ は偶数であり,$T$ が奇数のとき確率は $0$ である。
  • 本問の $c=16$ で $T=6$ とすると,寄与するのは $(u,v)=(\pm4,\pm4)$(複号同順)だけで,確率は $2c_6(4)^2/4^6=\frac{9}{512}$ である。$T=8$ で初めて $(\pm2,\pm8)$,$(\pm8,\pm2)$ が加わる。
    作問の観点からは,次の設計原理が読み取れる。
  • 終点集合の $\ell^1$ ノルムの最大値に時刻を一致させると,境界上の点が最短経路として現れ,計算量の異なる二種類の終点が共存する。
  • 経由点を,そのノルムと偶奇が通過時刻を一意に定めるように選ぶと,和事象が一つの事象に縮約される。
  • 経由点を複数の型の終点から等距離に置くと,終点の見落としを検出する設問になる。
  • 終点条件を $x\pm y$ の積で与えると,斜め座標による構造的な解法が開く。$xy=c$ のように元の座標の積で与えると $xy=\frac{u^2-v^2}{4}$ となり,独立な2変数の積の形にはならない。

5. 発展事項

5.1 高校数学と一般理論の境界

事項高校数学での扱い一般理論
経路の計数場合の数,多項係数,二項係数格子路の組合せ論,多項定理
斜め座標座標の取り替え,独立な試行独立確率変数への分解,部分格子
経由点条件付き確率,乗法定理Markov 性,ランダムウォーク・ブリッジ
漸化式隣接点からの和推移作用素,離散熱方程式
母関数多項式の展開と係数比較Laurent 多項式環,群環,Fourier 解析
$x^2-y^2$因数分解離散調和関数,マルチンゲール
多数歩での挙動扱わない局所中心極限定理,再帰性(Pólya)

本解・別解1・参考解1・参考解2と 3.1〜3.3 節は,いずれも高校数学(場合の数,二項定理,条件付き確率,漸化式)の範囲で完結する。右欄は,それらの計算が成り立つ理由を説明する理論である。

5.2 二つのパスカルの三角形:階数1の構造

補題5 は,斜め座標での経路数の表 $\bigl(c_t(u)\,c_t(v)\bigr)_{u,v}$ が,パスカルの三角形の第 $t$ 行を位置 $u$ に並べたベクトル $\boldsymbol{c}_t=\bigl(c_t(u)\bigr)_u$ の外積 $\boldsymbol{c}_t\boldsymbol{c}_t^{\top}$,すなわち階数1の行列であることを意味する。元の座標での表は階数1ではない。たとえば $t=1$ の表は
$$ \begin{pmatrix}0&1&0\\ 1&0&1\\ 0&1&0\end{pmatrix} $$
であり,階数は $2$ である。二次元の計数が一次元の計数二つに完全に分離するのは,適切な座標をとったときに限られる。
三つの計数法(本解・参考解1・別解1)の一致から,組合せ恒等式
$$ \sum_{\substack{e-w=x,\ n-s=y\\ e+w+n+s=t}}\frac{t!}{e!\,w!\,n!\,s!}=\sum_{k=0}^{t}\binom{t}{k}c_k(x)\,c_{t-k}(y)=c_t(x+y)\,c_t(x-y) $$
が得られる(左辺の和は非負整数 $e,w,n,s$ にわたる)。$x=y=0$,$t=2m$ では $\dfrac{(2m)!}{(j!)^2\bigl((m-j)!\bigr)^2}=\binom{2m}{m}\binom{m}{j}^2$ により,Vandermonde の恒等式 $\sum_j\binom{m}{j}^2=\binom{2m}{m}$ に帰着する。上の恒等式はその2変数版である。

5.3 独立化の一意性,等確率の条件,次元 2 の特殊性

独立化する一次形式

実数 $a,b$($(a,b)\neq(0,0)$)に対し $L(x,y)=ax+by$ とし,一歩での増分を $\Delta L$ とする。
(i) $\Delta L$ のとりうる値がちょうど2個 $\pm\gamma$($\gamma > 0$)であるための必要十分条件は $|a|=|b|$ である。したがって,そのような一次形式は定数倍を除いて $x+y$ と $x-y$ に限られる。
(ii) 方向の確率を $\Pr(\mathsf{E})=\Pr(\mathsf{W})=\frac p2$,$\Pr(\mathsf{N})=\Pr(\mathsf{S})=\frac{1-p}{2}$($0 < p < 1$)とする。このとき $\Delta U$,$\Delta V$ はそれぞれ $\pm1$ を確率 $\frac12$ ずつとるが,$\Delta U$ と $\Delta V$ が独立であるための必要十分条件は $p=\frac12$ である。

(i) $\Delta L\in\lbrace a,-a,b,-b\rbrace$ である。$a=0$ または $b=0$ なら値は $0$ と $\pm b$(または $\pm a$)の3個,$ab\neq0$ かつ $|a|\neq|b|$ なら4個,$|a|=|b|\neq0$ なら2個である。
(ii) $\Delta U=1$ となるのは $\mathsf{E}$,$\mathsf{N}$ のときで,その確率は $\frac p2+\frac{1-p}{2}=\frac12$ である。$\Delta V$ についても同様である。一方 $\Pr(\Delta U=1,\ \Delta V=1)=\Pr(\mathsf{E})=\frac p2$ であり,これが $\frac12\cdot\frac12$ に等しいのは $p=\frac12$ のときに限る。$p=\frac12$ のときは4つの符号の組がいずれも確率 $\frac14$ をもつから,独立である。

斜め座標は,移動規則から系統的に探せる唯一の候補であり,ひらめきに頼らずに見つかる。また独立性は,格子が正方形であることだけでなく,4方向が等確率であることにも依存する。
$\mathbb{Z}^d$ の単純ランダムウォークの一歩は $2d$ 通り,$d$ 個の $\pm1$ の組は $2^d$ 通りであり,$2d=2^d$ となるのは $d=1,2$ に限る。4方向を符号の組に一対一に対応させる本問の仕組みは,$d=2$ に特有である。$d=2$ では 補題5 と Stirling の公式から
$$ \Pr(\mathrm{P}_{2m}=\mathrm{O})=\Bigl(\binom{2m}{m}2^{-2m}\Bigr)^2\sim\frac{1}{\pi m}\qquad(m\to\infty) $$
が直ちに従い,$\sum_m\Pr(\mathrm{P}_{2m}=\mathrm{O})=\infty$ から原点への再帰性が得られる(Pólya の再帰定理の $d=2$ の場合)。$d=3$ では対応する級数は収束し,歩行は非再帰的である。

5.4 終点条件付きの歩行:ブリッジと超幾何分布

補題6 は,終点を固定した歩行(ランダムウォーク・ブリッジ)の時刻 $s$ での分布を与える。斜め座標では,$\mathrm{P}_T=w$ という条件は二つの符号列の和を $w$ の斜め座標 $(w_u,w_v)$ に固定する条件であり,この条件のもとでも二つの符号列は独立である(それぞれ和を固定した列の全体の上で一様)。一次元のブリッジの時刻 $s$ の位置は超幾何分布に従い
$$ \Pr\Bigl(\sum_{i\leqq s}\varepsilon_i=h\ \Big|\ \sum_{i\leqq T}\varepsilon_i=u\Bigr)=\frac{c_s(h)\,c_{T-s}(u-h)}{c_T(u)} $$
である。したがって二次元のブリッジの通過確率は,二つの超幾何確率の積になる。本問では
$$ \Pr\bigl(\mathrm{P}_6=(4,2)\mid \mathrm{P}_8=(4,0)\bigr)=\frac{c_6(6)\,c_2(-2)}{c_8(4)}\cdot\frac{c_6(2)\,c_2(2)}{c_8(4)}=\frac{1}{28}\cdot\frac{15}{28}=\frac{15}{784}, $$
$$ \Pr\bigl(\mathrm{P}_6=(4,2)\mid \mathrm{P}_8=(5,3)\bigr)=\frac{c_6(6)\,c_2(2)}{c_8(8)}\cdot\frac{c_6(2)\,c_2(0)}{c_8(2)}=1\cdot\frac{30}{56}=\frac{15}{28} $$
であり, 3.3 節 の値を再現する。

5.5 離散調和多項式とマルチンゲール

二次の離散調和多項式

関数 $f:\mathbb{Z}^2\to\mathbb{R}$ に対し
$$ (Mf)(x,y)=\frac14\bigl(f(x+1,y)+f(x-1,y)+f(x,y+1)+f(x,y-1)\bigr) $$
とおく。このとき
$$ M(x^2-y^2)=x^2-y^2,\qquad M(xy)=xy,\qquad M(x^2+y^2)=x^2+y^2+1 . $$
したがって $X_t^2-Y_t^2$,$X_tY_t$,$X_t^2+Y_t^2-t$ はマルチンゲールであり,$\mathbb{E}[X_t^2-Y_t^2]=\mathbb{E}[X_tY_t]=0$,$\mathbb{E}[X_t^2+Y_t^2]=t$ が成り立つ。

$\frac14\bigl((x+1)^2+(x-1)^2+2x^2\bigr)=x^2+\frac12$ と,$y$ についての同じ式から,第1式と第3式を得る。$\frac14\bigl((x+1)y+(x-1)y+x(y+1)+x(y-1)\bigr)=xy$ から第2式を得る。各時刻の移動がそれまでの経過によらず等確率であるから $\mathbb{E}\bigl[f(\mathrm{P}_{t+1})\mid\mathrm{P}_0,\ldots,\mathrm{P}_t\bigr]=(Mf)(\mathrm{P}_t)$ であり,後半が従う。

双曲線の族 $x^2-y^2=c$ は,離散調和多項式の等高線である。斜め座標では $x^2-y^2=uv$,$xy=\frac{u^2-v^2}{4}$,$x^2+y^2=\frac{u^2+v^2}{2}$ であり,$uv$ のマルチンゲール性は $U,V$ の増分の独立性と平均 $0$ から,$x^2+y^2-t$ のマルチンゲール性は $U_t^2-t$,$V_t^2-t$ のマルチンゲール性から直ちに従う。ただし期待値の情報は点確率を決めない。$\Pr(X_8^2-Y_8^2=16)$ を求めるには分布そのもの,すなわち 補題5 が必要である。

5.6 母関数・Fourier 解析・作用素のテンソル積

一歩の母関数 $F(z,w)=z+z^{-1}+w+w^{-1}$ は群環 $\mathbb{Z}[\mathbb{Z}^2]\cong\mathbb{Z}[z^{\pm1},w^{\pm1}]$ の元であり,経路数は $F^t$ の係数である( 3.2 節 )。単位円上 $z=e^{i\theta}$,$w=e^{i\varphi}$ に制限すると,一歩の特性関数
$$ \phi(\theta,\varphi)=\frac14F(e^{i\theta},e^{i\varphi})=\frac{\cos\theta+\cos\varphi}{2}=\cos\frac{\theta+\varphi}{2}\,\cos\frac{\theta-\varphi}{2} $$
を得る。積への分離は $(a+a^{-1})(b+b^{-1})$ への因数分解の解析的な表現であり,双対変数 $\frac{\theta\pm\varphi}{2}$ が斜め座標に対応する。
作用素の言葉では,一次元の推移作用素を $(L\psi)(n)=\frac12\bigl(\psi(n+1)+\psi(n-1)\bigr)$ とすると, 命題9 の $M$ は元の座標で
$$ M=\frac12\bigl(L\otimes I+I\otimes L\bigr) $$
と表される。これは $L\otimes L$ ではない($L\otimes L$ は斜めの4方向に動く歩行の作用素である)。斜め座標 $(u,v)$ に移り,状態空間を $u\equiv v\pmod 2$ の部分格子に制限すると
$$ M=L\otimes L $$
となり,$M^t=L^t\otimes L^t$ が 補題5 の作用素版である。テンソル積への分離には座標の取り替えが本質的に必要であり,元の座標のまま $M=L\otimes L$ とする記述は誤りである。

5.7 離散熱方程式と局所中心極限定理

確率 $p_t(z)=f_t(z)/4^t$ は
$$ p_{t+1}(z)-p_t(z)=\frac14\sum_{d}\bigl(p_t(z-d)-p_t(z)\bigr) $$
をみたす($d$ は4方向)。右辺は離散 Laplace 作用素であり,これは離散熱方程式である。 補題5 と一次元の局所中心極限定理
$$ \Pr(U_t=u)=\sqrt{\frac{2}{\pi t}}\;e^{-u^2/(2t)}\bigl(1+o(1)\bigr)\qquad(u\equiv t\ (\mathrm{mod}\ 2),\ u=O(\sqrt{t})) $$
から,$u^2+v^2=2(x^2+y^2)$ により,$x+y\equiv t\pmod2$ の点で
$$ p_t(x,y)=\frac{2}{\pi t}\,e^{-(x^2+y^2)/t}\bigl(1+o(1)\bigr) $$
を得る。$t=8$,$(x,y)=(4,0)$ では主要項は $\frac{1}{4\pi}e^{-2}\approx0.0108$ であり,正確な値 $\frac{49}{4096}\approx0.0120$ に近い。一方,境界上の $(5,3)$ では主要項 $\approx0.00114$ に対し正確な値は $\frac{56}{65536}\approx0.00085$ であり,分布の裾では近似は粗い。有限歩の厳密な点確率には組合せ的な計数が適切である。

5.8 歴史的背景

「ランダムウォーク」の語は,K. Pearson が1905年に Nature 誌に寄せた問題に由来する。格子上の単純ランダムウォークの再帰性は G. Pólya が1921年の論文(街路網における酔歩を扱ったもの)で示した。$d=2$ の再帰性の標準的な証明には, 補題5 と同じ平方の形 $\binom{2m}{m}^2$ が現れる。差分方程式と酔歩の関係は Courant–Friedrichs–Lewy(1928)の差分法の研究にも現れ,マルチンゲールの理論は J. L. Doob(1953年の著書)により体系化された。二項係数の畳み込みの公式は Vandermonde(18世紀)の名で呼ばれるが,朱世傑(1303年)にすでに現れる。本問は,これらの理論が交わる最も小さな具体例の一つになっている。


6. 最終整理

6.1 全体の構造マップ

  • 4方向等確率の歩行 → 移動列の一様分布,確率は経路数の比( 1.1 節 )
    • 削減:距離と偶奇( 補題1 )
      • 終点:$x^2-y^2=(x+y)(x-y)=16$ → $H$ は6点。型 I $(\pm4,0)$ は余裕あり,型 II $(\pm5,\pm3)$ は境界上( 補題2 ,3.1 節)
      • 経由:$\lVert(4,2)\rVert_1=6$ と偶奇 → 通過時刻は $6$ のみ( 補題3 )
    • 計数
      • 経路全体を分類する → 本解(方向別の回数),参考解1(動く軸の選択)
      • 一歩を再符号化する → 別解1(斜め座標,$N_t=c_t(x+y),c_t(x-y)$),3.2 節(母関数)
      • 局所遷移を合成する → 参考解2(前向きの $f_t$,後ろ向きの $g_t$)
    • 経由の処理:連結( 補題4 )により $15\times3$。終点による分解・Bayes の公式(3.3 節)
    • 結論:$\dfrac{49}{4096}$,$\dfrac{7}{256}$,$\dfrac{45}{1792}$

6.2 数学的教訓

  • 数える前に削る。距離と偶奇によって,終点は6点に,経由時刻は一つに定まる。
  • 距離の等号は最短経路を意味し,境界上の点は二項係数一つで数えられる。
  • 終点条件の因数 $x\pm y$ が歩行を独立化する座標と一致するとき,二次元の計数は一次元の計数二つの積になる。独立化の根拠は,4方向と符号の組の一対一対応と,4方向の等確率性である。
  • 「いずれかの時刻」は可能な時刻を列挙して縮約し,経由点で経路を前半と後半に連結する。
  • 条件付き確率では分母の集合を固定する。(3) の分母は $4^8$ ではなく $|B|=1792$ である。
  • 対称性は,歩行と対象集合の両方が共有するものだけを用いる。
  • 同じ計数の言い換え(母関数,和積公式,複素数,作用素)を別解として重複して数えず,計算の原理の違い(分類・再符号化・局所遷移)で解法を整理する。
投稿日:11日前
数学の力で現場を変える アルゴリズムエンジニア募集 - Mathlog served by OptHub

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

医学部・難関大受験生の指導を行っています。

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中