1東京科学大学 2023年 数学 第1問解答・解説

格子折れ線は、2列の格子点をすべて1度ずつ通る道。両端点の列を $p\leqq q$ とすると、$p$ より左は「行って戻る」U字形、$q$ より右も U字形、その間は1列ずつ縦に折り返すジグザグしかない。始点の行（上か下か）を決めると全体が決まる。

格子点 $(x,\,y)$ を「$x$ 列の $y$ 行」とよぶ。格子折れ線は、隣り合う格子点を順にたどる道で、$V_{n}$ の $2(n+1)$ 点をちょうど1度ずつ通るものと同じである。

構造 両端点の列を $p\leqq q$ とする。

- $p<q$ のとき：$p$ 列より左の点（$p>0$ のとき）は、$p$ 列とは2本の横の辺でしかつながらないので、端点のない部分として「片方の行を左端まで行き、もう片方の行で戻る」U字形でたどられる。このとき $p$ 列の2点はU字形の入口と出口になり、端点 $(p,\,r)$ から U字形を回って $(p,\,1-r)$ に戻る。そこから右に進むと、次の列で縦に動かないとその列の残りの点が行き止まりになるので、$q$ 列まではジグザグ（1列ずつ縦に動き、行を変えて右へ）しかない。$q$ 列より右も同様にU字形で、最後に $q$ 列の残りの点で終わる。$p=0$ のときは始点から縦に動き、同じ形になる。したがって $(p,\,q)$ を決めると、始点の行の選び方で2通り。
- $p=q$ のとき：左右両方に点が残ると1本の道でたどれないので $p=0$ か $p=n$ で、それぞれ全体を回るU字形の1通り。

よって両端点の $x$ 座標の差が $d$（$1\leqq d\leqq n$）のものは、$q-p=d$ となる $(p,\,q)$ が $n-d+1$ 組あるので $2(n-d+1)$ 個、差が0のものは2個。

(1) $L_{1}$：差1が $2\cdot1=2$ 個、差0が2個の計4個。$L_{2}$：差2が2個、差1が4個、差0が2個の計8個。具体的には答えの欄の通り（曲がり角の点を順に結ぶ）。

(2) 差4が2個、差3が4個の計6個（答えの欄）。

(3) $d=n-2$ のとき $2\{n-(n-2)+1\}=6$ 個。

(4) $l_{n}=2+\displaystyle\sum_{d=1}^{n}2(n-d+1)=2+n(n+1)=n^{2}+n+2$。（$l_{1}=4$、$l_{2}=8$ と合う。）