東京大学 文系 2021年度 第2問 解説
問題編
問題
$N$ を $5$ 以上の整数とする。 $1$ 以上 $2N$ 以下の整数から、相異なる $N$ 個の整数を選ぶ。ただし $1$ は必ず選ぶこととする。選んだ数の集合を $S$ とし、 $S$ に関する以下の条件を考える。
条件１： $S$ は連続する $2$ 個の整数からなる集合を1つも含まない。
条件２： $S$ は連続する $N-2$ 個の整数からなる集合を少なくとも1つ含む。ただし、 $2$ 以上の整数 $k$ に対して、連続する $k$ 個の整数からなる集合とは、ある整数 $l$ を用いて $\{
l,l+1,\cdots l+k-1 \}$ と表される集合を指す。例えば $\{1,2,3,5,7,8,9,10\}$ は連続する3個の整数からなる集合 $\{1,2,3\}$, $\{7,8,9\}$, $\{8,9,10\}$ を含む。(1) 条件１を満たすような選び方は何通りあるか。
(2) 条件２を満たすような選び方は何通りあるか。
考え方
(2)は、どういう切り口で数えるかで、めんどくささが大きく変わってきます。一番思いつきやすい切り口は、何個連続するかで分ける方法ですが、かなり複雑になります（別解に載せています）。
解答編
問題
$N$ を $5$ 以上の整数とする。 $1$ 以上 $2N$ 以下の整数から、相異なる $N$ 個の整数を選ぶ。ただし $1$ は必ず選ぶこととする。選んだ数の集合を $S$ とし、 $S$ に関する以下の条件を考える。
条件１： $S$ は連続する $2$ 個の整数からなる集合を1つも含まない。
条件２： $S$ は連続する $N-2$ 個の整数からなる集合を少なくとも1つ含む。ただし、 $2$ 以上の整数 $k$ に対して、連続する $k$ 個の整数からなる集合とは、ある整数 $l$ を用いて $\{
l,l+1,\cdots l+k-1 \}$ と表される集合を指す。例えば $\{1,2,3,5,7,8,9,10\}$ は連続する3個の整数からなる集合 $\{1,2,3\}$, $\{7,8,9\}$, $\{8,9,10\}$ を含む。(1) 条件１を満たすような選び方は何通りあるか。
解答例
選んだ数を小さい順に並べて $a_1,a_2,\cdots,a_N$ で表すこととする。
(1)
条件１を満たすとき、 $a_i+1\geqq a_i+2$ $(i=1,2,\cdots,N-1)$ が成り立つ。このとき、
\begin{eqnarray}
a_N
&\geqq &
a_{N-1}+2 \\[5pt]
&\geqq &
a_{N-2}+4 \\[5pt]
&\geqq & \cdots \\[5pt]
&\geqq &
a_1+2(N-1)=2N-1 \\[5pt]
\end{eqnarray}なので、 $a_N$ は $2N-1$ か $2N$ となるしかない。
(i) $s_N=2N-1$ のとき
$i=1,2,\cdots,N-1$ に対して $a_{i+1}=a_i+2$ が成り立つので1通り。
(ii) $s_N=2N$ のとき
$i=1,2,\cdots,N-1$ に対して、 $a_{i+1}\geqq a_i+2$ の等号が成り立たないものが1つだけある。その $i$ を $j$ とおくと、 $a_{j+1}=a_j+3$ が成り立つ。 $j$ の選び方が $N-1$ 通りあるので、こうなるケースは $N-1$ 通り。
以上から、 $1+(N-1)=N$ 通り。
（終）
解答編 つづき
問題
(2) 条件２を満たすような選び方は何通りあるか。
解答例
(2)
条件２を満たすように選んだとき、連続する整数からなる集合のうち要素数が最も多いものを考える。 $N\geqq 5$ なので、このような集合は1つに決まる。この集合の最小値を $m$ とし、 $m$ の値で場合分けをする。
(i) $m=1$ のとき
$a_1$ から $a_{N-2}$ は、それぞれ $1$ から $N-2$ までの整数である。 $a_{N-1}$ と $a_N$ は、残りの $N+2$ 個の整数から自由に選べるので、こうなる場合の数は\[ {}_{N+2}\mathrm{C}_2 \]通りである。
(ii) $m\gt 1$ のとき
$m=2$ なら、最小値が $1$ となってしまうので、 $m\ne 2$ である。また、この最小値から数えて $N-2$ 番目の数は $m+(N-3)$ であり、これは $2N$ 以下でないといけないので、\[ m\leqq 2N-(N-3)=N+3 \]である。逆に、 $3\leqq m\leqq N+3$ を満たすとき、最小値が $m$ となる連続する $N-2$ 個の整数を選ぶことができる。 $m$ の選び方は $N+1$ 通りあり、 $m$ を決めると、 $N-2$ 個の整数の選び方が決まる。
残りの1個の整数は、 $m-1$ から $m+N-3$ までの $N-1$ 個の整数と $1$ を除いた、 $N$ 個から自由に選ぶことができる。そのため、こうなる場合の数は\[ N(N+1) \]通りである。
以上より、全体の場合の数は
\begin{eqnarray}
& &
{}_{N+2}\mathrm{C}_2 +N(N+1) \\[5pt]
&=&
\frac{(N+2)(N+1)+2N(N+1)}{2} \\[5pt]
&=&
\frac{(3N+2)(N+1)}{2} \\[5pt]
\end{eqnarray}通りとなる。
（終）
別解
もっと愚直にやるなら、次のようになります。
条件２を満たすように選んだとき、連続する整数からなる集合のうち要素数が最も多いものを考えます。この要素数は、 $N$, $N-1$, $N-2$ のどれかなので、これで場合分けをします。
(i) 連続する $N$ 個の整数からなる集合を含む場合
$1$ から $N$ までの整数を選ぶときだけなので、1通り。
(ii) (i)が起こらず、連続する $N-1$ 個の整数からなる集合を含む場合
$1$ から $N-1$ までの整数を選ぶときは、 $a_N$ は $N+1$ から $2N$ までのどれかを選べばいいので $N$ 通り。
これ以外のときは、 $a_2\geqq 3$ かつ $a_N=a_2+(N-2)\leqq 2N$ なので、 $3\leqq a_2\leqq N+2$ となることが必要です。このとき、 $a_2$ を決めれば連続する $N-1$ 個の整数が1通りに決まります。 $a_2$ の選び方は $N$ 通りです。
以上から、 $2N$ 通りです。
(iii) (i)(ii) が起こらず、連続する $N-1$ 個の整数からなる集合を含む場合
$a_1$ から $a_{N-2}$ が連続するときは、$1$ から $N-2$ までの整数を選ぶときです。残りの $a_{N-1}$ と $a_N$ は、 $N$ から $2N$ までの中から自由にどれかを選べばいいので ${}_{N+1}\mathrm{C}_2$ 通り。
$a_2$ から $a_{N-1}$ が連続するときは、 $a_1+1\lt a_2$, $a_2+(N-3)+1\lt a_N$ を満たす $a_2,a_N$ を $3$ から $2N$ の中から選べばいいです。これは、 $a_2={a'}_2+1$, $a_N={a'}_N+(N-2)$ とおけば、 $a_1\lt {a'}_2$, ${a'}_2\lt {a'}_N$ を満たす ${a'}_2,{a'}_N$ を $2$ から $N+1$ の中から選べばいいです。 $N$ 個から $2$ 個を選ぶ場合の数なので、 ${}_{N}\mathrm{C}_2$ 通りです。
$a_3$ から $a_N$ が連続するときは、 $a_N=a_3+(N-3)$ なので、 $a_3\leqq N+3$ となります。よって、 $a_1\lt a_2$, $a_2+1\lt a_3$ を満たす $a_2,a_3$ を $2$ から $N+3$ の中から選べばいいです。これは、 $a_3={a'}_3+1$ とおけば、 $a_1\lt a_2$, $a_2\lt {a'}_3$ を満たす $a_2,{a'}_3$ を $2$ から $N+2$ の中から選べばいいです。 $N+1$ 個から $2$ 個を選ぶ場合の数なので、 ${}_{N+1}\mathrm{C}_2$ 通りです。
以上から、 $(2{}_{N+1}\mathrm{C}_2+{}_{N}\mathrm{C}_2)$ 通りです。
(i)(ii)(iii) より、全体の場合の数は
\begin{eqnarray}
& &
1+2N+2{}_{N+1}\mathrm{C}_2+{}_{N}\mathrm{C}_2 \\[5pt]
&=&
1+2N+(N+1)N+\frac{N(N-1)}{2} \\[5pt]
&=&
\frac{2 +4N +2N^2 +2N +N^2 -N}{2} \\[5pt]
&=&
\frac{3N^2+5N+2}{2} \\[5pt]
&=&
\frac{(3N+2)(N+1)}{2} \\[5pt]
\end{eqnarray}通りと求められます。
