方針
右上がりを 、右下がりを と考えると、折れ線グラフは上下移動の列に対応する。(1) は右上がり回数 と右下がり回数 を連立して数える。(2) は高さ に途中で到達する経路を、到達しない経路との差として数える。到達しない経路は最後に初めて高さ に到達する経路であり、反射法で数えられる。(3) はコイン投げを折れ線に対応させ、(2) を に適用する。
解答
(1) 右上がりに進む回数を 、右下がりに進む回数を とする。終点が であるためには でなければならない。よって である。
したがって折れ線グラフが存在するための必要十分条件は、 が整数、すなわち である。この条件が満たされるとき、 回のうち右上がりに進む 回を選べばよいので、本数は である。
(2) 原点から へ行く全経路数は、(1) より である。
まず の場合を考える。格子点 を通らない経路は、最後の点 で初めて高さ に達する経路である。このような経路は、 まで高さ に達しないで進み、最後に右上がりで に到達する。 までの経路全体は 本である。このうち途中で高さ に達するものは、初めて高さ に達した後の部分を直線 に関して反射することで、 へ行く経路と1対1に対応する。したがってその本数は である。よって、途中で高さ に達しないで最後に到達する経路数は である。
したがって、少なくとも1つの を通る経路数はである。パスカルの関係を用いると、これは である。
一方、原点から へ行く経路数は である。よって求める本数はその2倍である。 の場合は、すべての経路が出発点 を通るので左辺は全経路数であり、同じ二項係数の恒等式から結論が成り立つ。
(3) が起きる経路は、原点から へ行く折れ線グラフに対応する。全体の本数は である。
条件に反する経路、すなわち となる が少なくとも1つある経路数は、(2) を に適用して である。したがって、求める条件つき確率は である。, より である。
別解
解法2(母関数と反射対応)
方針
各歩を で表して終点別の経路数を係数として求め、
初到達部分の反射対応を条件付き確率へつなぐ。
解答
(1)
上向き・下向きの1歩をそれぞれ とすれば、求める本数は
における の係数である。指数は
だから、存在条件は が偶数であり、そのとき本である。
(2)
とおく。最後に初めて高さ に達する経路について、
最後の1歩を除き、初到達後を で反射する。この反射対応から
初到達経路は本である。求める本数は全体からこれを引いてこれは への経路数の2倍である。
(3)
となる全経路は 本、(2)より
時刻7までに高さ3を通るものは 本である。
よって条件を満たすものは28本で、条件付き確率は
総評
難度7、計算量6。目安時間は
26〜30分。
主題は場合の数・確率である。解法1では誘導に沿った標準的な答案を、解法2では
異なる見方から全小問を再構成した。採点では、途中の必要条件を十分条件まで戻すこと、
場合分けの境界・等号条件・定義域を明記することが重要である。