東京大学 2021年度 前期日程 第2次学力試験文系数学 第2問

(1)

1は必ず選ばれる。条件1を満たすには，1と連続する2は選ばれない。したがって，3以上 $2N$ 以下の $2N-2$ 個の整数から，隣り合わない $N-1$ 個を選べばよい。

選ぶ $N-1$ 個を小さい順に $x_1<x_2<\cdots <x_{N-1}$ とする。隣り合わない条件は $x_{j+1}\geqq x_j+2$ である。ここで $z_j=x_j-(j-1)$ とおくと $$3\leqq z_1<z_2<\cdots <z_{N-1}\leqq 2N-(N-2)=N+2$$ となる。逆にこのような $z_j$ を選べば，$x_j=z_j+(j-1)$ により隣り合わない選び方が得られる。

したがって，$3,4,\dots ,N+2$ の $N$ 個から $N-1$ 個を選ぶので，求める選び方は $${}_N{\mathrm{C}}_{N-1}=N$$ 通りである。

(2)

選ばれた整数の連続ブロックのうち，最大の長さを $m$ とする。条件2を満たすことは $m\geqq N-2$ と同値である。選ばれる数は全部で $N$ 個なので，$$m=N,N-1,N-2$$ の場合に分けて数えればよい。この分け方は最大長による分類なので重複しない。

まず $m=N$ の場合，選んだ $N$ 個すべてが連続する。1を含むので，集合は $\{1,2,\dots ,N\}$ の1通りである。

次に $m=N-1$ の場合を考える。最大ブロックが1を含むなら，そのブロックは $\{1,2,\dots ,N-1\}$ である。残り1個として $N$ を選ぶと長さ $N$ に延びてしまうので，選べるのは $N+1,N+2,\dots ,2N$ の $N$ 通りである。

最大ブロックが1を含まないなら，選んだ集合は1と長さ $N-1$ のブロックからなる。1と連結しないために，ブロックを $\{l,l+1,\dots ,l+N-2\}$ と書くと $3\leqq l\leqq N+2$ である。よってこの場合も $N$ 通りである。したがって $m=N-1$ の場合は $2N$ 通りである。

最後に $m=N-2$ の場合を考える。最大ブロックが1を含むなら，そのブロックは $\{1,2,\dots ,N-2\}$ である。残り2個は，ブロックを延長しないように $N-1$ を避けて $N,N+1,\dots ,2N$ から選ぶ。よって ${}_{N+1}{\mathrm{C}}_2$ 通りである。

最大ブロックが1を含まないなら，ブロックを $\{l,l+1,\dots ,l+N-3\}$ と書ける。1と連結しないために $3\leqq l\leqq N+3$ である。さらに，残り1個を選ぶとき，ブロックを延長する $l-1$ と $l+N-2$ は選べない。ただし $l=N+3$ のとき右隣 $l+N-2$ は $2N$ を超えて存在しない。

したがって，$3\leqq l\leqq N+2$ の $N$ 通りの $l$ については残り1個の選び方が $N-1$ 通り，$l=N+3$ については $N$ 通りである。よってこの場合は $N(N-1)+N=N^2$ 通りである。

以上を合計して，条件2を満たす選び方は $$1+2N+{}_{N+1}{\mathrm{C}}_2+N^2=\frac{3N^2+5N+2}{2}$$ 通りである。

(1) は選んだ数の間の空きと末尾の空きを変数にすると，余分な空きが合計1であることから直ちに数えられる。(2) は長さ $N-2$ の区間 $T$ と，それを含む集合 $S$ の組を数える。同じ $S$ が複数回数えられるのは最大連続長が $N-1$ または $N$ の場合だけなので，その余分を差し引く。

(1) 選んだ数を$$1=x_1<x_2<\cdots <x_N\leqq 2N$$とする。条件1より，隣り合う選択数の間にある未選択数の個数$$d_j=x_{j+1}-x_j-1(1\leqq j\leqq N-1)$$はすべて1以上である。また末尾の空きを $d_N=2N-x_N\geqq 0$ とする。選ばない数は全部で $N$ 個なので$$d_1+d_2+\cdots +d_N=N$$である。最初の $N-1$ 個から1ずつ差し引くと，$N$ 個の非負整数の和が1になる。したがって1を置く場所の選び方だけがあり，求める個数は$$N$$通りである。

(2) 長さ $N-2$ の連続区間を $T$ とし，$T\subset S$ となる組 $(S,T)$ を数える。

$T=\{1,2,\dots ,N-2\}$ のとき，残る2個は外側の $N+2$ 個から選ぶので$${}_{N+2}{\mathrm{C}}_2$$通りである。$T$ の先頭が2以上のとき，先頭は $2,3,\dots ,N+3$ の $N+2$ 通りである。1はすでに選ばれ，残る1個は $T\cup \{1\}$ の外の $N+1$ 個から選べる。よって組 $(S,T)$ の総数は$$P={}_{N+2}{\mathrm{C}}_2+(N+2)(N+1)=\frac{3}{2}(N+1)(N+2)$$である。

ただし，同じ $S$ が複数の $T$ を含む場合を補正する。最大連続長が $N-1$ の集合は，長いブロックが1を含む場合に $N$ 通り，含まない場合に $N$ 通りあり，合計 $2N$ 通りである。この各集合は長さ $N-2$ の区間を2個含むので，1回ずつ余分に数えられている。また最大連続長が $N$ の集合は $\{1,2,\dots ,N\}$ の1通りで，長さ $N-2$ の区間を3個含むため2回余分である。

したがって条件2を満たす集合の個数は$$P-2N-2=\frac{3}{2}(N+1)(N+2)-2N-2=\frac{(N+1)(3N+2)}{2}$$通りである。