方針
各ステップは を1増やし を または 変えるので、上向きの回数を数えれば(1)は二項係数になる。(2)は、全経路から「最後まで高さ に初めて到達する経路」を引く。後者は最後の1歩の前まで高さ 未満にある経路で、反射の対応により2つの二項係数の差で数える。(3)は を終点 と見る条件付き確率に直し、(2)を直接使う。
解答
(1)
原点から へ進む折れ線グラフを考える。各ステップでは 座標が1増え、 座標は または だけ変化する。
上向きのステップ数を 、下向きのステップ数を とすると である。したがって となる。これらが整数でなければならないので、必要十分条件は である。
この条件が成り立つとき、 回のうち上向きに進む 回を選べばよいから、折れ線グラフの数は である。
(2)
(1) より、原点から へ行く折れ線グラフ全体の数は である。
求めるものは、このうち途中で高さ の格子点 の少なくとも1つを通るものの数である。 は偶数なので、 のとき高さ にはなれない。したがって、これは「終点 より前に一度は高さ に達するもの」と同じである。
そこで、終点で初めて高さ に達する折れ線グラフの数を数える。最後の1歩は から への上向きの1歩である。よって、その直前までは原点から へ行き、途中で高さ に達しない折れ線グラフである。
原点から へ行く全体の数は である。このうち途中で高さ に達するものは、初めて高さ に達した後の部分を直線 に関して反射すると、原点から へ行く折れ線グラフと1対1に対応する。したがってその数は である。
よって、終点で初めて高さ に達するものの数は である。したがって、求める数はである。 を用いるととなる。
一方、原点から へ行く折れ線グラフの数は である。したがって求める数は、その2倍に等しい。
(3) であることは、折れ線グラフが原点から へ行くことに対応する。この全体の数は である。
条件「どの も3にならない」は、終点より前に高さ3の格子点を通らないということである。なお、 では偶奇が合わないため は起こらない。
(2) を 、 に適用すると、終点より前に高さ3に達する折れ線グラフの数は、原点から へ行く折れ線グラフの数の2倍である。これは である。
したがって、終点まで高さ3に達しないものの数は である。求める条件つき確率は である。
別解
解法2(母関数と初到達反射)
方針
経路数を の係数として求める。
高さ への初到達経路は、初到達後を反射する写像で数え、
最後に条件付き確率へ直す。
解答
(1)
上向きを 、下向きを とすると、終点 への本数は
の の係数である。よって が偶数のときだけ存在し、本である。
(2)
とおく。終点で初めて高さ に達する経路は、
最後の1歩の前まで へ行き、高さ に触れない。
途中で高さ に触れる経路の初到達後を反射すると
への経路と1対1に対応する。したがって終点初到達は全経路から引き、Pascalの関係を使えばこれは への本数の2倍である。
(3)
の全経路は 本、
時刻7までに高さ3に達する経路は (2) から
本である。よって
総評
難度7、計算量6。目安時間は
26〜30分。
主題は場合の数・確率である。解法1では誘導に沿った標準的な答案を、解法2では
異なる見方から全小問を再構成した。採点では、途中の必要条件を十分条件まで戻すこと、
場合分けの境界・等号条件・定義域を明記することが重要である。