東京大学 2021年 文系 第2問 解説

方針・初手

(1) は「どの2つの数も隣り合わない」ような選び方を求める典型問題である。選ぶ数を●、選ばない数を〇として並び替えを考える方法や、選んだ数の差を文字でおいて方程式の解の個数に帰着させる手法が有効である。

(2) は「連続する $N-2$ 個の整数からなる集合を少なくとも1つ含む」選び方を求める。選んだ数の集合 $S$ に含まれる連続する整数の極大ブロックの「最大長」に着目し、それが $N-2$、$N-1$、$N$ となる場合に分けて数え上げる。この際、常に「$1$ を必ず選ぶ」という条件を満たすように注意深く場合分けを行う。

解法1

(1)

$1$ から $2N$ までの整数のうち、選ぶ $N$ 個を●、選ばない $N$ 個を〇とする。条件1を満たす選び方は、●が隣り合わないような〇と●の並べ方と1対1に対応する。

「$1$ は必ず選ぶ」ため、一番左端は必ず●である。 ●が隣り合わないようにするためには、左端以外の $N-1$ 個の●のすぐ左に、必ず〇を1つずつ配置したブロック「〇●」を作ればよい。

左端の●と、$N-1$ 個のブロック「〇●」を一列に並べると、 ● 〇● 〇● 〇● $\dots$ 〇● となる。この時点で●は $N$ 個、〇は $N-1$ 個使われているため、残っている〇はあと1個である。

この最後の1個の〇を挿入できる場所を考える。一番左の●のさらに左に〇を入れると「$1$ を選ばない」ことになってしまうため、そこには入れられない。 したがって、〇を挿入できる場所は、 ・$N-1$ 箇所ある「●と〇の間」（つまり、●のすぐ右） ・一番右端の●の右側 のいずれかである。

これらの挿入可能な箇所は合計 $(N-1) + 1 = N$ 箇所ある。どこに〇を入れても条件を満たす並べ方が1つ決まるため、求める選び方は $N$ 通りである。

(2)

選んだ数の集合 $S$ に含まれる、連続する整数の極大集合（ブロック）のうち、要素数が最大のものを $M$ とする。条件2を満たすのは $M \ge N-2$ のときである。 $S$ の要素数は全体で $N$ 個であるため、$M$ の値は $N-2$、$N-1$、$N$ のいずれかである。これらが互いに排反であることを利用して場合分けを行う。

(i) $M = N$ のとき $S$ は連続する $N$ 個の整数からなる。$1 \in S$ であるから、集合は $S = \{1, 2, \dots, N\}$ に限られる。 この選び方は $1$ 通りである。

(ii) $M = N-1$ のとき $S$ は、長さ $N-1$ のブロックと、これと隣り合わない離れた1つの要素からなる。 ・長さ $N-1$ のブロックが $1$ を含む場合 ブロックは $\{1, 2, \dots, N-1\}$ となる。残りの1要素は $N$ と隣り合わないため、$N+1$ 以上 $2N$ 以下の範囲から選ぶ。この選び方は $(2N) - (N+1) + 1 = N$ 通りである。

・離れた1つの要素が $1$ である場合 長さ $N-1$ のブロックの最小要素を $k$ とする。$1$ と隣り合わないため $k \ge 3$ である。また、最大要素 $k+N-2$ は $2N$ 以下であるから、$k \le N+2$ を満たす。 よって $k$ の範囲は $3 \le k \le N+2$ となり、その選び方は $N$ 通りである。 これらより、$M=N-1$ となる選び方は $N + N = 2N$ 通りである。

(iii) $M = N-2$ のとき $S$ は、長さ $N-2$ のブロック $B$ と、これと隣り合わない2つの要素からなる。 $N \ge 5$ より $N-2 \ge 3$ であるため、残りの2要素が連続したとしても長さは最大2であり、$B$ が最長のブロックとして一意に定まる。 ・$B$ が $1$ を含む場合 $B = \{1, 2, \dots, N-2\}$ となる。残りの2要素は $N-1$ と隣り合わないため、$N$ 以上 $2N$ 以下の $N+1$ 個の整数から2つを選ぶ。この選び方は

$$ {}_{N+1}\mathrm{C}_{2} = \frac{N(N+1)}{2} $$

通りである。

・残りの2要素のうちの1つが $1$ である場合 もう1つの要素を $x$ とし、$B = \{k, k+1, \dots, k+N-3\}$ とする。 $B$ は $1$ と隣り合わないため $k \ge 3$ である。また、最大要素は $2N$ 以下より $k \le N+3$ である。 $x$ が満たすべき条件は、「$x \neq 1$ かつ $x \notin B$ かつ $x$ は $B$ と隣り合わない」ことである。ブロック $B$ が数直線の右端 $2N$ に接するかどうかで、選べない数の個数が変わるためさらに場合分けする。

(ア)

$3 \le k \le N+2$ のとき $B$ の両隣の数 $k-1$ と $k+N-2$ はいずれも $2$ 以上 $2N$ 以下の範囲に存在する。 $x$ として選べない数は、$1$ と $B$ の要素（$N-2$ 個）および $B$ の両隣（2個）の合計 $N+1$ 個である。よって $x$ の選び方は $2N - (N+1) = N-1$ 通りである。 $k$ の選び方は $N$ 通りあるので、$N(N-1)$ 通りとなる。

(イ)

$k = N+3$ のとき $B = \{N+3, \dots, 2N\}$ であり、$B$ の右隣の数は存在しない。 $x$ として選べない数は、$1$ と $B$ の要素（$N-2$ 個）および $B$ の左隣（1個）の合計 $N$ 個である。よって $x$ の選び方は $2N - N = N$ 通りである。 $k=N+3$ の $1$ 通りであるから、$1 \times N = N$ 通りとなる。

以上より、$M=N-2$ となる選び方は

$$ \frac{N(N+1)}{2} + N(N-1) + N = \frac{N^2+N + 2N^2 - 2N + 2N}{2} = \frac{3N^2+N}{2} $$

通りである。

（i）、（ii）、（iii） の合計を計算して、求める選び方は

$$ 1 + 2N + \frac{3N^2+N}{2} = \frac{2 + 4N + 3N^2 + N}{2} = \frac{3N^2+5N+2}{2} = \frac{(N+1)(3N+2)}{2} $$

通りとなる。

解法2

(1) の別解

選んだ $N$ 個の整数を小さい順に $a_1, a_2, \dots, a_N$ とする。 条件より $a_1 = 1$ であり、どの2数も連続しないため、

$$ a_{i+1} - a_i \ge 2 \quad (i = 1, 2, \dots, N-1) $$

が成り立つ。 ここで $x_i = a_{i+1} - a_i - 2 \ge 0$ ($i = 1, 2, \dots, N-1$) とおく。 また、$x_N = 2N - a_N$ とおくと、$a_N \le 2N$ より $x_N \ge 0$ である。

これらの変数の和をとると、

$$ \sum_{i=1}^{N} x_i = \sum_{i=1}^{N-1} (a_{i+1} - a_i - 2) + (2N - a_N) $$

となり、右辺を計算すると、

$$ \sum_{i=1}^{N} x_i = (a_N - a_1) - 2(N-1) + 2N - a_N = -1 - 2N + 2 + 2N = 1 $$

となる。すなわち、

$$ x_1 + x_2 + \dots + x_N = 1 \quad (x_i \ge 0) $$

を満たす $0$ 以上の整数の組 $(x_1, x_2, \dots, x_N)$ の個数を求めればよい。 これは $N$ 個の変数のうちのいずれか1つだけが $1$ で、残りがすべて $0$ となる場合であるから、求める選び方は $N$ 通りである。

解説

(1) は「隣り合わない選び方」を数える問題である。解法1のように「〇と●の配置」として捉える方法と、解法2のように「隣接項の差」を文字に置いて整数解の個数に帰着させる方法がある。

(2) は排反な場合分けで数える問題である。「連続する $N-2$ 個を少なくとも 1 つ含む」という条件を、「最大の連続長が $N-2, N-1, N$ のいずれかである」と言い換えると重複を避けやすい。さらに、「$1$ を含むかどうか」で分けると漏れも防ぎやすい。

答え

(1)

$N$ 通り

(2)

$\frac{(N+1)(3N+2)}{2}$ 通り