Evolton

九州大学 1996年度 前期日程 第2次学力試験文系数学 第4問

原点Oから出発して,座標平面上をx軸の正の方向,またはy軸の正の方向に1だけ進むことを
次々に行って得られる経路を道という.
右の図は,原点Oと点P(4,2)とを結ぶ道の例である.
原点と点(i, j)を結ぶ,領域{(x, y)∣x≧y}内の道の総数をN(i, j)とする.
次の問に答えよ.

(1) N(2, 2),N(3, 1),N(3, 2)を求めよ.

(2) n≧1のとき,N(n, 1)を求めよ.

(3) n≧3のとき,N(n, 2)をN(n, 1)とN(n−1, 2)で表し,
N(n, 2)を求めよ.

原資料の図は配布アーカイブに含まれないため、条件に基づく模式図を示す。

問題の図

難易度5/ 10計算量4/ 10目安18分

場合の数 数え上げ、漸化式の変形、誘導利用

方針

条件 x≧y を破らない格子経路を数える。小さい値は実際の経路を分類し、N(n,1) は上向きの一歩が最初に来ないことから数える。N(n,2) は最後の一歩が右向きか上向きかで分けて漸化式を立て、初期値から和を取る。

解答

(1) (2,2) へ行くには右向きの一歩を R、上向きの一歩を U として、R を二回、U を二回使う。条件 x≧y を満たすものは RRUU,RURU の二つである。したがって N(2,2)=2 である。 (3,1) へ行くには R を三回、U を一回使う。最初に U を置くと (0,1) に出て条件を破るので、U は二歩目以降の三か所に置ける。よって N(3,1)=3 である。 (3,2) へ行く道を同様に数えると、条件を満たすものは RRRUU,RRURU,RRUUR,RURRU,RURUR である。したがって N(2,2)=2,N(3,1)=3,N(3,2)=5 である。

(2) (n,1) へ行くには、R を n 回、U を 1 回使う。U が最初に来ると x<y となってしまうが、二歩目以降なら、その時点で少なくとも x=1 なので条件を破らない。全体で n+1 歩あり、U を置ける場所は最初以外の n か所である。よって N(n,1)=n である。

(3) (n,2) へ到達する最後の一歩を考える。最後が右向きなら直前は (n−1,2)、最後が上向きなら直前は (n,1) である。この二つは重ならないので N(n,2)=N(n−1,2)+N(n,1)(n≧3) である。

(1) , (2) より N(2,2)=2、N(k,1)=k だから N(n,2)=2+∑k=3nk である。したがって N(n,2)=2+(n(n+1)2−3)=n(n+1)2−1 である。

別解

解法2

方針

反射原理を使い、条件 x≧y を満たす経路数の一般式を先に求める。全経路から、初めて y=x+1 に達する不適経路を引けば、各小問が同じ式から直ちに得られる。

解答

(1)
(i,j) へ至る全経路は i+jCj 通りである。条件 x≧y を破る経路について、初めて直線 y=x+1 に達するまでを直線 y=x+1 に関して反射する。すると、これは (−1,1) から (i,j) へ至る経路と一対一に対応する。その数はi+jCj−1である。したがってN(i,j)=i+jCj−i+jCj−1.これよりN(2,2)=6−4=2,N(3,1)=4−1=3,N(3,2)=10−5=5.(2)N(n,1)=n+1C1−n+1C0=(n+1)−1だからN(n,1)=n.(3)
最後の一歩が右向きか上向きかで分けるとN(n,2)=N(n−1,2)+N(n,1).また一般式から直接N(n,2)=n+2C2−n+2C1=(n+2)(n+1)2−(n+2)である。したがってN(n,2)=n(n+1)2−1.

総評

格子経路を条件付きで数える基本問題。目安時間は18分。小問の流れは、直接列挙、一次の場合、最後の一歩による漸化式という設計になっている。N(n,1)=n では「上向きの一歩が最初以外ならよい」と言い切れる理由を添えると、条件 x≧y の確認が明確になる。 2解法の結論を相互照合し、定義域、端点、場合分け、図示範囲まで確認した。

Evolton Pro

月額
2,480円(税込)
保存・印刷
公開過去問PDF・オーダーメイド問題集PDF
プランを確認・登録

冊子PDFで見る九大の場合の数の問題で問題集を作る

出典: 九州大学 1996年度 前期 文系 第4問。問題文はHTML表示のために再入力・数式組版しています。