Evolton

東京大学 2021年度 前期日程 第2次学力試験文系数学 第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, ⋯⋯ , 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を満たすような選び方は何通りあるか。

難易度6/ 10計算量6/ 10目安25分

場合の数 数え上げ、場合分け、計算整理

方針

(1) は1が必ず選ばれるため2が選べないことから,3,4,…,2N から隣り合わない N−1 個を選ぶ問題にする。(2) は選ばれた数の最大連続ブロックの長さで分類する。条件2は最大長が N−2,N−1,N のいずれかであることと同値であり,この分類なら重複しない。各場合で,ブロックが1を含むか,1がブロックの外にあるかを分け,ブロックを延長してしまう隣接位置を除いて残りの選び方を数える。

解答

(1)

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

選ぶ N−1 個を小さい順に x1<x2<⋯<xN−1 とする。隣り合わない条件は xj+1≧xj+2 である。ここで zj=xj−(j−1) とおくと 3≦z1<z2<⋯<zN−1≦2N−(N−2)=N+2 となる。逆にこのような zj を選べば,xj=zj+(j−1) により隣り合わない選び方が得られる。

したがって,3,4,…,N+2 の N 個から N−1 個を選ぶので,求める選び方は NCN−1=N 通りである。

(2)

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

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

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

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

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

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

したがって,3≦l≦N+2 の N 通りの l については残り1個の選び方が N−1 通り,l=N+3 については N 通りである。よってこの場合は N(N−1)+N=N2 通りである。

以上を合計して,条件2を満たす選び方は 1+2N+N+1C2+N2=3N2+5N+22 通りである。

別解

解法2(隙間表示と二重計数を使う)

方針

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

解答

(1) 選んだ数を1=x1<x2<⋯<xN≦2Nとする。条件1より,隣り合う選択数の間にある未選択数の個数dj=xj+1−xj−1(1≦j≦N−1)はすべて1以上である。また末尾の空きを dN=2N−xN≧0 とする。選ばない数は全部で N 個なのでd1+d2+⋯+dN=Nである。最初の N−1 個から1ずつ差し引くと,N 個の非負整数の和が1になる。したがって1を置く場所の選び方だけがあり,求める個数はN通りである。

(2) 長さ N−2 の連続区間を T とし,T⊂S となる組 (S,T) を数える。

T={1,2,…,N−2} のとき,残る2個は外側の N+2 個から選ぶのでN+2C2通りである。T の先頭が2以上のとき,先頭は 2,3,…,N+3 の N+2 通りである。1はすでに選ばれ,残る1個は T∪{1} の外の N+1 個から選べる。よって組 (S,T) の総数はP=N+2C2+(N+2)(N+1)=32(N+1)(N+2)である。

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

したがって条件2を満たす集合の個数はP−2N−2=32(N+1)(N+2)−2N−2=(N+1)(3N+2)2通りである。

総評

難度6、計算量6。想定時間は25分程度。(1) は隣接禁止の典型変換で,1が固定されているため2を除く点が最初の注意点である。(2) は「少なくとも1つ」を直接包除で数えると重複しやすいので,最大連続ブロックの長さで分類するのが安定する。ブロックが1を含むかどうか,また隣の数を選ぶと最大長が延びることを丁寧に除外できるかが得点を分ける。

Evolton Pro

月額
2,480円(税込)
保存・印刷
公開過去問PDF・オーダーメイド問題集PDF
プランを確認・登録

冊子PDFで見る東大の場合の数の問題で問題集を作る

出典: 東京大学 2021年度 前期日程 第2次学力試験 数学(大学公式の問題PDF)。問題文はHTML表示のために再入力・数式組版しています。