Evolton

九州大学 2002年度 前期日程 第2次学力試験 場合の数・確率文系数学 第4問(c)

平面上の点のx座標とy座標がどちらも整数であるとき,その点を格子点という.
与えられた格子点を第1番目とし,
この点から右斜め45∘または右斜め−45∘の方向にもっとも近い第2番目の格子点をとり,
この2点を線分で結ぶ.
同様にして第2番目の格子点から第3番目の格子点をとり,第2番目と第3番目を線分で結ぶ.
以下これを有限回繰り返し,
こうしてできる線分をつないだものを折れ線グラフということにする.
上図に原点Oと格子点(9, −1)を結ぶ折れ線グラフの例を示す.
次の問いに答えよ.必要ならば右図を参考にせよ.

(1) nは正の整数,kは0≦k≦nなる整数とする.
原点Oと格子点(n, k)を結ぶ折れ線グラフが存在するための必要十分条件は
n+kが偶数であることを示せ.
また,この必要十分条件がみたされているとき,
原点Oと格子点(n, k)を結ぶ折れ線グラフの数を求めよ.

(2) nは2以上の整数,kは0≦k≦n−2なる整数で,n+kは偶数とする.
原点Oと格子点(n, k)を結ぶ折れ線グラフであって
格子点(0, k),(1, k),⋯,(n−2, k)の少なくとも1つを通る折れ線グラフの数は,
原点Oと格子点(n−1, k+1)を結ぶ折れ線グラフの数の2倍に等しいことを示せ.

(3) コインを9回投げる.
1回からi回までの試行において,表の出た回数から裏の出た回数を引いた数をTiで表す.
このとき各格子点(i, Ti),i=0, 1, 2, ⋯ , 9,
を順番に線分でつなげば折れ線グラフが得られる.ただし,T0=0とする.
T9=3が起きたとき,どのTi (i=0, 1, 2, ⋯ , 7)も3にならない条件つき確率を求めよ.

問題の図

難易度7/ 10計算量6/ 10目安25分

場合の数、確率 数え上げ、対称性の利用、条件付き確率

方針

右上がりを +1、右下がりを −1 と考えると、折れ線グラフは上下移動の列に対応する。(1) は右上がり回数 u と右下がり回数 v を連立して数える。(2) は高さ k に途中で到達する経路を、到達しない経路との差として数える。到達しない経路は最後に初めて高さ k に到達する経路であり、反射法で数えられる。(3) はコイン投げを折れ線に対応させ、(2) を n=9,k=3 に適用する。

解答

(1) 右上がりに進む回数を u、右下がりに進む回数を v とする。終点が (n,k) であるためには u+v=n,u−v=k でなければならない。よって u=n+k2,v=n−k2 である。

したがって折れ線グラフが存在するための必要十分条件は、(n+k)/2 が整数、すなわち n+k が偶数 である。この条件が満たされるとき、n 回のうち右上がりに進む (n+k)/2 回を選べばよいので、本数は nC(n+k)/2 である。

(2) 原点から (n,k) へ行く全経路数は、(1) より nC(n+k)/2 である。

まず k>0 の場合を考える。格子点 (0,k),(1,k),…,(n−2,k) を通らない経路は、最後の点 (n,k) で初めて高さ k に達する経路である。このような経路は、(n−1,k−1) まで高さ k に達しないで進み、最後に右上がりで (n,k) に到達する。 (n−1,k−1) までの経路全体は n−1C(n+k)/2−1 本である。このうち途中で高さ k に達するものは、初めて高さ k に達した後の部分を直線 y=k に関して反射することで、(n−1,k+1) へ行く経路と1対1に対応する。したがってその本数は n−1C(n+k)/2 である。よって、途中で高さ k に達しないで最後に到達する経路数は n−1C(n+k)/2−1−n−1C(n+k)/2 である。

したがって、少なくとも1つの (j,k) 0≦j≦n−2 を通る経路数はnC(n+k)/2−{n−1C(n+k)/2−1−n−1C(n+k)/2}である。パスカルの関係nC(n+k)/2=n−1C(n+k)/2−1+n−1C(n+k)/2を用いると、これは 2n−1C(n+k)/2 である。

一方、原点から (n−1,k+1) へ行く経路数は n−1C((n−1)+(k+1))/2=n−1C(n+k)/2 である。よって求める本数はその2倍である。k=0 の場合は、すべての経路が出発点 (0,0) を通るので左辺は全経路数であり、同じ二項係数の恒等式から結論が成り立つ。

(3) T9=3 が起きる経路は、原点から (9,3) へ行く折れ線グラフに対応する。全体の本数は 9C6 である。

条件に反する経路、すなわち Ti=3 となる i≦7 が少なくとも1つある経路数は、(2) を n=9,k=3 に適用して 28C6 である。したがって、求める条件つき確率は 1−28C69C6 である。8C6=28, 9C6=84 より 13 である。

別解

解法2(母関数と反射対応)

方針

各歩を X±1 で表して終点別の経路数を係数として求め、
初到達部分の反射対応を条件付き確率へつなぐ。

解答

(1)
上向き・下向きの1歩をそれぞれ X,X−1 とすれば、求める本数は
(X+X−1)n における Xk の係数である。指数は 2r−n
だから、存在条件は n+k が偶数であり、そのときnC(n+k)/2本である。

(2)
r=(n+k)/2 とおく。最後に初めて高さ k に達する経路について、
最後の1歩を除き、初到達後を y=k で反射する。この反射対応から
初到達経路はn−1Cr−1−n−1Cr本である。求める本数は全体からこれを引いてnCr−n−1Cr−1+n−1Cr=2n−1Cr,これは (n−1,k+1) への経路数の2倍である。

(3)
T9=3 となる全経路は 9C6=84 本、(2)より
時刻7までに高さ3を通るものは 28C6=56 本である。
よって条件を満たすものは28本で、条件付き確率は2884=13.

総評

難度7、計算量6。目安時間は
26〜30分。
主題は場合の数・確率である。解法1では誘導に沿った標準的な答案を、解法2では
異なる見方から全小問を再構成した。採点では、途中の必要条件を十分条件まで戻すこと、
場合分けの境界・等号条件・定義域を明記することが重要である。

Evolton Pro

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

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

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