[math][東京医科歯科大学][場合の数]2023年東京医科歯科大学数学問題1

問題
方針
解答
解説
関連問題
関連リンク

問題

$xy$平面において、$x$座標および$y$座標が共に整数であるような点を格子点と呼び。$xy$平面上の相異なる$2$つの格子点を端点とする折れ線のうち、$x$座標または$y$座標が等しい格子点どうしを結ぶ線分のみから構成され、かつ同じ点を$2$度通ることはないものを、格子折れ線と呼ぶ。ここで、格子折れ線の向きは考慮せず、端点および通過する点がすべて等しい格子折れ線は同じものとする。また、自然数$n$に対し、$$0\leq x\leq n\text{かつ}0\leq y\leq 1$$を満たす格子点全体の集合を$V_n$とする。さらに、$V_n$に属する格子点をすべて通り、かつ$V_n$に属さない格子点は通らない格子折れ線全体の集合を$L_n$とする。たとえば、$7$つの格子点$(0, 1), (0, 0), (1, 0), (1, 1), (4, 1), (4, 0), (2, 0)$を順に結んだ折れ線は$L_4$に属する。このとき、以下の各問に答えよ。
$(1)$ $L_1$および$L_2$に属する格子折れ線をすべて図示せよ。
$(2)$ $L_4$に属する格子折れ線のうち、両端点の$x$座標の差が$3$以上となるものをすべて図示せよ。
$(3)$ $n\geq 3$のとき、$L_n$に属する格子折れ線のうち、両端点の$x$座標の差がちょうど$n-2$となるものの個数を求めよ。
$(4)$ $L_n$に属する格子折れ線の個数$L_n$を、$n$を用いて表わせ。

方針

$(1)$ まずは手を動かす。

$(2)$ これも列挙していく。

$(3)$ 図を描いていくと、格子折れ線を作るときの制約は厳し目なので、たくさんの場合分けが生じないことがわかる。

$(4)$ 両端点の$x$座標を決めてしまうと、格子折れ線は一意に定まる。ただし、両端点の$x$座標が等しい場合は場合分けが必要になる。

解答

$(1)$ $L_1$は以下の$4$つになる。

$L_2$は以下の$8$つになる。

$(2)$ 以下の$6$つとなる。

$(3)$ 一方の端点が$(0, 0)$であるとき、もう一方の端点の$y$座標は$n$が奇数ならば$0$、$n$が偶数ならば$1$になる。

一方の端点が$(0, 1)$であるとき、もう一方の端点の$y$座標は$n$が奇数ならば$1$、$n$が偶数ならば$0$になる。

一方の端点が$(1, 0)$であるとき、もう一方の端点の$y$座標は$n$が奇数ならば$0$、$n$が偶数ならば$1$になる。

一方の端点が$(1, 1)$であるとき、もう一方の端点の$y$座標は$n$が奇数ならば$1$、$n$が偶数ならば$0$になる。

一方の端点が$(2, 0)$であるとき、もう一方の端点の$y$座標は$n$が奇数ならば$0$、$n$が偶数ならば$1$になる。

一方の端点が$(2, 1)$であるとき、もう一方の端点の$y$座標は$n$が奇数ならば$1$、$n$が偶数ならば$0$になる。

いずれも一意に格子折れ線が定まるので、両端点の$x$座標の差が$n-2$となるものの個数は$\underline{6}$個である。

$(4)$ 両端点の$x$座標が同じとき、下のような$2$通りがある。$1\leq x\leq n-1$のときは、両端点が$x$であるような格子折れ線は存在しない。

両端点の$x$座標が異なるとき、$0\leq i<j\leq n$となる整数$(i, j)$の選び方は$\displaystyle _{n+1}{\mathbb{C}}_{2} = \frac{n(n+1)}{2}$通り。このそれぞれに対して、片方の端点の$y$座標を決めたとき、もう片方の端点の$y$座標は一意に定まり、格子折れ線も一意に定まる。よって求める格子折れ線の個数は、$\displaystyle 2+2\cdot \frac{n(n+1)}{2} = \underline{n^2+n+2}$となる。