東北大学 2017年度 後期日程 第2次学力試験理系（後期）数学 第4問

頂点$A$を$(0,0,0)$とし，隣り合う頂点への移動を，3つの座標のうち1つを反転する操作と考える。各時刻で3本の辺を等確率に選ぶので，長さ$n$の移動列は全部で$3^n$通りである。

(1) , (2)
時刻$n$に$A$へ戻るための条件は，3つの座標がそれぞれ偶数回反転されることである。3種類の記号の出現回数がすべて偶数である長さ$n$の列数を$N_n$とする。偶奇を取り出す標準的な数え上げにより $$N_n=\frac{1}{8}\{3^n+3\cdot 1^n+3\cdot (-1{)}^n+(-3{)}^n\}$$ である。したがって，求める確率$P_n$は$$P_n=\frac{N_n}{3^n}=\frac{1}{8}\{1+3{\left(\frac{1}{3}\right)}^n+3{(-\frac{1}{3})}^n+(-1{)}^n\}$$である。

特に$n$が奇数のときは$P_n=0$であり，$n$が偶数のときは $$P_n=\frac{1}{4}+\frac{3}{4\cdot 3^n}$$ である。よって $$P_4=\frac{1}{4}+\frac{3}{4\cdot 3^4}=\frac{7}{27},P_5=0$$ である。

(3)
時刻8に$A$へ戻る移動列の総数は $3^8{P}_8=1641$ である。

時刻8までにすべての頂点を通り，かつ時刻8に$A$にいるなら，時刻0と時刻8の$A$を除いて，残り7頂点をそれぞれ1回ずつ通る。つまり長さ8の閉路で全頂点を一周する場合を数えればよい。

反転する座標を$1,2,3$で表す。最初の2手は同じ座標を続けて選ぶと$A$に戻ってしまうので，相異なる$i,j$を選ぶ。残る座標を$k$とすると，全頂点を1回ずつ通って戻る列は，この最初の$i,j$に対して $ijikijik,ijkjijkj$ の2通りである。ここで空白を詰めて書けば，それぞれ $(i,j,i,k,i,j,i,k),(i,j,k,j,i,j,k,j)$ である。$(i,j)$の選び方は$3\cdot 2=6$通りなので，有利な移動列は $6\cdot 2=12$ 通りである。

したがって求める条件付き確率は $$\frac{12}{1641}=\frac{4}{547}$$ である。

頂点をAからの距離0,1,2,3の4層に分け，層間の遷移数からAへ戻る経路数の漸化式を作る。偶数時刻の閉路数を2次漸化式で解き，(3)は8手のハミルトン閉路を数える。

Aから辺に沿った距離が$r$である頂点の層を$L_r(0\leqq r\leqq 3)$とする。$L_r$の各頂点からは$r$本が$L_{r-1}$へ，$3-r$本が$L_{r+1}$へ向かう。

(1) , (2) 長さ$n$でAからAへ戻る経路数を$N_n$とする。4層の経路数について上の遷移を順に書き，途中の3層を消去すると$$N_{n+4}=10N_{n+2}-9N_n$$を得る。初期値は$$N_0=1,N_1=0,N_2=3,N_3=0$$である。奇数項はすべて0である。$M_m=N_{2m}$とおくと$$M_{m+2}=10M_{m+1}-9M_m,M_0=1,M_1=3.$$よって$$M_m=\frac{9^m+3}{4}\mathrm{.}$$全経路は$3^{2m}=9^m$通りなので$$P_{2m}=\frac{1}{4}+\frac{3}{4\cdot 9^m},P_{2m+1}=0.$$特に$$P_4=\frac{7}{27},P_5=0.$$(3) Aへ戻る8手の経路は$$N_8=\frac{9^4+3}{4}=1641$$通りである。8手ですべての頂点を通るには，A以外の7頂点を各1回通るハミルトン閉路でなければならない。最初の方向は3通り，次は戻らない2通りであり，その各々に対して残りを巡る方法は2通りである。したがって有利な経路は$$3\cdot 2\cdot 2=12$$通りで，条件付き確率は$$\frac{12}{1641}=\frac{4}{547}\mathrm{.}$$