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

問題編

問題

 $N$ を $5$ 以上の整数とする。 $1$ 以上 $2N$ 以下の整数から、相異なる $N$ 個の整数を選ぶ。ただし $1$ は必ず選ぶこととする。選んだ数の集合を $S$ とし、 $S$ に関する以下の条件を考える。

 条件1: $S$ は連続する $2$ 個の整数からなる集合を1つも含まない。
 条件2: $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) 条件1を満たすような選び方は何通りあるか。

(2) 条件2を満たすような選び方は何通りあるか。

【広告】
【画期的な歴史入門書と話題沸騰! 30万部突破!】
youtubeで話題! 現役教師の新感覚の世界史
今、一番売れている世界史本!

推理小説を読むように一気に読める!
"新感覚"の教科書にあなたも必ずハマる!

現役公立高校教師としては初めて、Youtubeに世界史の授業動画を公開し、
たちまち、大学受験生や社会人、教育関係者から「神授業! 」として話題沸騰の
現役・公立高校教師が書いた“新感覚"の世界史の教科書!
大学受験、学び直しにも。高校生から、主婦、社会人まで必読の1冊!
著者:山﨑 圭一
出版社:SBクリエイティブ
発売日:2018-08-18
ページ数:352 ページ
値段:¥1,650
(2021年09月 時点の情報です)

考え方

(2)は、どういう切り口で数えるかで、めんどくささが大きく変わってきます。一番思いつきやすい切り口は、何個連続するかで分ける方法ですが、かなり複雑になります(別解に載せています)。

1 2