問題
平面上の点の座標と座標がどちらも整数であるとき，その点を格子点という．与えられた格子点を第1番目とし，この点から右斜めまたは右斜めの方向にもっとも近い第2番目の格子点をとり，この2点を線分で結ぶ．同様にして第2番目の格子点から第3番目の格子点をとり，第2番目と第3番目を線分で結ぶ．以下これを有限回繰り返し，こうしてできる線分をつないだものを折れ線グラフということにする．上図に原点と格子点を結ぶ折れ線グラフの例を示す．次の問いに答えよ．必要ならば右図を参考にせよ．
(1) は正の整数，はなる整数とする．原点と格子点を結ぶ折れ線グラフが存在するための必要十分条件はが偶数であることを示せ．また，この必要十分条件がみたされているとき，原点と格子点を結ぶ折れ線グラフの数を求めよ．
(2) は2以上の整数，はなる整数で，は偶数とする．原点と格子点を結ぶ折れ線グラフであって格子点，，，の少なくとも1つを通る折れ線グラフの数は，原点と格子点を結ぶ折れ線グラフの数の2倍に等しいことを示せ．
(3) コインを9回投げる．1回から回までの試行において，表の出た回数から裏の出た回数を引いた数をで表す．このとき各格子点，，を順番に線分でつなげば折れ線グラフが得られる．ただし，とする．が起きたとき，どの も3にならない条件つき確率を求めよ．
方針
右上がりを 、右下がりを と考えると、折れ線グラフは上下移動の列に対応する。(1) は右上がり回数 と右下がり回数 を連立して数える。(2) は高さ に途中で到達する経路を、到達しない経路との差として数える。到達しない経路は最後に初めて高さ に到達する経路であり、反射法で数えられる。(3) はコイン投げを折れ線に対応させ、(2) を に適用する。
解答
(1) 右上がりに進む回数を 、右下がりに進む回数を とする。終点が であるためには でなければならない。よって である。
したがって折れ線グラフが存在するための必要十分条件は、 が整数、すなわち である。この条件が満たされるとき、 回のうち右上がりに進む 回を選べばよいので、本数は である。
(2) 原点から へ行く全経路数は、(1) より である。
まず の場合を考える。格子点 を通らない経路は、最後の点 で初めて高さ に達する経路である。このような経路は、 まで高さ に達しないで進み、最後に右上がりで に到達する。 までの経路全体は 本である。このうち途中で高さ に達するものは、初めて高さ に達した後の部分を直線 に関して反射することで、 へ行く経路と1対1に対応する。したがってその本数は である。よって、途中で高さ に達しないで最後に到達する経路数は である。
したがって、少なくとも1つの を通る経路数は
である。パスカルの関係
を用いると、これは である。
一方、原点から へ行く経路数は である。よって求める本数はその2倍である。 の場合は、すべての経路が出発点 を通るので左辺は全経路数であり、同じ二項係数の恒等式から結論が成り立つ。
(3) が起きる経路は、原点から へ行く折れ線グラフに対応する。全体の本数は である。
条件に反する経路、すなわち となる が少なくとも1つある経路数は、(2) を に適用して である。したがって、求める条件つき確率は である。, より である。