難問奇問数学自作問題118-碁盤上経路と漸化式-

大学入試 自作問題 難問 奇問 組み合わせ 漸化式

「下図のような、各区画の長さが等しい碁盤目状の道路がある。 { \displaystyle n}を自然数とするとき、地点Aからスタートして地点 { \displaystyle Z_n}でゴールするような最短経路は何通りあるか。 { \displaystyle n}を用いて表せ。

f:id:ChunPom:20190207222252j:plain

」

 

 

碁盤目上の最短経路の問題と、漸化式を融合させた問題。 地点Aからスタートして地点 { \displaystyle Z_n}でゴールするような最短経路の数を { \displaystyle P_n}とおき、 { \displaystyle Z_n}の右斜め下の地点にゴールするような最短経路の数を { \displaystyle Q_n}とし、それぞれに漸化式を立てると良い。片方を消去して { \displaystyle Q_n}のみに関する漸化式を求めると、 { \displaystyle Q_{n+2}=16Q_{n+1}-28Q_n}を得る。この二項間漸化式を解いて { \displaystyle P_n}を求めれば、 { \displaystyle P_n=\frac{1}{12}(49\cdot 14^{n-1}-25\cdot 2^{n-1})}となる。