OMC225(D)

　線分 $AC$ を $4$ 等分する点を，$A$ に近い方から $A_1,A_2,A_3$ とし，$A_4=C$ とする．$A$ から $A_i$ まで線の上のみを通って最短で移動する方法の総数を $f(i)$ で表す．$f(4)$ を求めればよい．
　まず，$A_1$ を通る方法は，$A$ から $A_1$ までが $f(1)$ 通り，$A_1$ から $C$ までが $f(3)$ 通りで，これらは独立なので全体では $f(1)f(3)$ 通りである．次に，$A_1$ を通らず $A_2$ を通る方法は，同様に考えて $2f(2)$ 通りである．さらに繰り返すことで，$f(4)=f(1)f(3)+2f(2)+4f(1)+10$ が成り立つことがわかる．
　同様に遡っていくことで，$f(3)=f(1)f(2)+2f(1)+4$，$f(2)=f(1)^2+2$ であるから，まとめると $$f(4) = f(1)^4 + 6f(1)^2 + 8f(1) + 14.$$ 　以下，$f(1)$ を求める．線分 $AA_1$ の中点を $X$ とし，$A$ から $X$ までの最短経路が $N$ 通りあるとすると，上と同様にして $f(1)=N^2+2$ である．さらに，線分 $AX$ の中点を $Y$ とし，$A$ から $Y$ までの最短経路が $M$ 通りあるとすると，やはり $N=M^2+2$ である．$M={}_{4}\mathrm{C}_2=6$ であるから，順に計算することで $f(4)=\mathbf{4371942276134}$ を得る．