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分

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

方針

各ステップは x を1増やし y を 1 または −1 変えるので、上向きの回数を数えれば(1)は二項係数になる。(2)は、全経路から「最後まで高さ k に初めて到達する経路」を引く。後者は最後の1歩の前まで高さ k 未満にある経路で、反射の対応により2つの二項係数の差で数える。(3)は T9=3 を終点 (9,3) と見る条件付き確率に直し、(2)を直接使う。

解答

(1)

原点から (n,k) へ進む折れ線グラフを考える。各ステップでは x 座標が1増え、y 座標は +1 または −1 だけ変化する。

上向きのステップ数を u、下向きのステップ数を d とすると u+d=n,u−d=k である。したがって u=n+k2,d=n−k2 となる。これらが整数でなければならないので、必要十分条件は n+k が偶数 である。

この条件が成り立つとき、n 回のうち上向きに進む u=(n+k)/2 回を選べばよいから、折れ線グラフの数は nC(n+k)/2 である。

(2)

(1) より、原点から (n,k) へ行く折れ線グラフ全体の数は nCr,r=n+k2 である。

求めるものは、このうち途中で高さ k の格子点 (0,k),(1,k),…,(n−2,k) の少なくとも1つを通るものの数である。n+k は偶数なので、x=n−1 のとき高さ k にはなれない。したがって、これは「終点 (n,k) より前に一度は高さ k に達するもの」と同じである。

そこで、終点で初めて高さ k に達する折れ線グラフの数を数える。最後の1歩は (n−1,k−1) から (n,k) への上向きの1歩である。よって、その直前までは原点から (n−1,k−1) へ行き、途中で高さ k に達しない折れ線グラフである。

原点から (n−1,k−1) へ行く全体の数は n−1Cr−1 である。このうち途中で高さ k に達するものは、初めて高さ k に達した後の部分を直線 y=k に関して反射すると、原点から (n−1,k+1) へ行く折れ線グラフと1対1に対応する。したがってその数は n−1Cr である。

よって、終点で初めて高さ k に達するものの数は n−1Cr−1−n−1Cr である。したがって、求める数はnCr−(n−1Cr−1−n−1Cr)である。nCr=n−1Cr−1+n−1Cr を用いるとnCr−n−1Cr−1+n−1Cr=2n−1Crとなる。

一方、原点から (n−1,k+1) へ行く折れ線グラフの数は n−1C((n−1)+(k+1))/2=n−1Cr である。したがって求める数は、その2倍に等しい。

(3) T9=3 であることは、折れ線グラフが原点から (9,3) へ行くことに対応する。この全体の数は 9C(9+3)/2=9C6=84 である。

条件「どの Ti i=0,1,…,7 も3にならない」は、終点より前に高さ3の格子点を通らないということである。なお、i=8 では偶奇が合わないため T8=3 は起こらない。

(2) を n=9、k=3 に適用すると、終点より前に高さ3に達する折れ線グラフの数は、原点から (8,4) へ行く折れ線グラフの数の2倍である。これは 28C(8+4)/2=28C6=56 である。

したがって、終点まで高さ3に達しないものの数は 84−56=28 である。求める条件つき確率は 2884=13 である。

別解

解法2(母関数と初到達反射)

方針

経路数を (X+X−1)n の係数として求める。
高さ k への初到達経路は、初到達後を反射する写像で数え、
最後に条件付き確率へ直す。

解答

(1)
上向きを X、下向きを X−1 とすると、終点 (n,k) への本数は
(X+X−1)n の Xk の係数である。よって n+k が偶数のときだけ存在し、nC(n+k)/2本である。

(2)
r=(n+k)/2 とおく。終点で初めて高さ k に達する経路は、
最後の1歩の前まで (n−1,k−1) へ行き、高さ k に触れない。
途中で高さ k に触れる経路の初到達後を反射すると
(n−1,k+1) への経路と1対1に対応する。したがって終点初到達はn−1Cr−1−n−1Cr.全経路から引き、Pascalの関係を使えばnCr−(n−1Cr−1−n−1Cr)=2n−1Cr.これは (n−1,k+1) への本数の2倍である。

(3)
T9=3 の全経路は 9C6=84 本、
時刻7までに高さ3に達する経路は (2) から
28C6=56 本である。よって84−5684=13.

総評

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

Evolton Pro

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

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

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