読者です 読者をやめる 読者になる 読者になる

さとぅーの寝言

睡眠が大好きだけど大嫌いな駆け出しさんすうマンです。勉強したことや趣味について適当に綴っていきます。

大学編入試験の過去問解説(2)-仲間外れにするかしないか

前回:大学編入試験の過去問解説(1)-行列の固有値


あ~だりぃ~ブログ書くのだりぃ~

勝手に金入ってこねぇかなぁ~~~~~



あ,どうもみなさんこんにちは.

いかがお過ごしでしょうか.


意識の高い受験生はそろそろ過去問を解き始めている頃なのかね~



ちなみに,僕は受験が無事終わったって言うのに,卒研やらなんやらで息をつく暇がありません.



同情なんて要りません.

同情する暇があるなら金をくれってんだ.



そういや,最近ごちうさカフェでぴょんぴょんしてきましたよ^~

残りの高専生活を乗り切る活力をもらえた気がしました.

おそらく,気がしただけですが.



話が逸れてすんません.

そろそろ今回取り上げる問題を見ていきましょう.


n自然数kn 以下の自然数とする.n 人の学生が k 個のグループに分かれ,
各グループで円上に並ぶときの並び方の総数を S(n,k) と表す.ただし,各グループは
1名以上の学生を含むものとする.

(1)省略

(2)S(n,k)=(n-1)S(n-1,k)+S(n-1,k-1) が成立することを示せ.
ただし,S(0,0)=1,各 i \, (i \ge 1) に対して S(i,0)=0 とし,
任意の i,j \, (i < j) に対して S(i,j)=0 とする.

(3)H_n \displaystyle H_n= \frac{S(n+1,2)}{n!}

とする.H_nn を用いて表せ.

(4)設問(3)の H_n が,任意の自然数 n \, (n \ge 1) に対して,

 \displaystyle \frac{\lfloor \mathrm{log}_2 \, n \rfloor + 1}{2} < H_n \le \lfloor \mathrm{log}_2 \, n \rfloor + 1 

を満たすことを示せ.ただし,\lfloor x \rfloorx 以下の最大の整数を表すものとする.


設問(1)は解説するまでもないのでカット.

とりま,問題文の内容を簡単に図でまとめてみました.


f:id:mathg-32:20161009171141j:plain


以下から各設問の解説に飛べます.

 


設問(2)

まず,n人の中からある1人に注目し,その人を「Aさん」と名付けます.

そして,Aさんを含めたn人がk個のグループに分かれるとき,以下の2通りに場合分けすることができます.

 (i) Aさんが単独でグループを作る.
 (ii) Aさんが単独でグループを作らない.

要は,Aさんが他のn-1人の学生からハブられているかどうかってことですね.

S(n,k) を求めるためには,ケース(i),(ii)それぞれの場合における並べ方の総数を求めて,それらを足し合わせれば良いわけです.


まずは,ケース(i)から考えてみましょう.


f:id:mathg-32:20161009174828j:plain


なんだかAさんが可哀想だという声がちらほら聞こえてきそうですが,そんなことは気にせず話を進めていきます.


Aさんがぼっちでグループを作っているということは,残りのn-1人でk-1個のグループを作ることになります.

そのときの並べ方の総数は,問題をきちんと把握していればすぐに S(n-1,k-1) であることが分かります.


というわけで,ケース(i)のとき,並べ方の総数は S(n-1,k-1) になります.



お次はケース(ii).


f:id:mathg-32:20161009180501j:plain


ケース(ii)では,Aさんがぼっちにならないようにグループ分けすることを考えます.


まず最初,Aさんを除くn-1人の学生だけでk個のグループに分かれます.

このときの並べ方の総数は明らかに S(n-1,k) となります.


問題は次で,Aさんをk個のグループのどこかに混ぜてあげなければなりません.

そのとき,Aさんが割り込める場所はどれだけあるのかという話です.


上図において5人のグループを見てみると,Aさんが割り込める場所は5か所あることが分かります.

さらに,Aさんがどこに割り込んでも並び方が異なることも明らかです.


同様にしてk個のグループ全体で見てみると,割り込める場所はn-1か所あり,どこに割り込んでも並び方は異なります.

つまり,Aさんが割り込んで新しい並び方をつくるときの場合の数は,全部でn-1通りあります.


以上より,ケース(ii)のとき,並べ方の総数は (n-1) \times S(n-1,k) になります.



ケース(i),(ii)それぞれの場合における並べ方の総数が求まったので,あとは足し合わせて

 \displaystyle S(n,k)=(n-1)S(n-1,k)+S(n-1,k-1)

となるわけです.

設問(3)

 \displaystyle H_n= \frac{S(n+1,2)}{n!}

この H_nn を用いて表さないといけないそうです.

言い換えると,数列 (H_n) の一般項を求めろってことですね.


とりあえず,S(n+1,2) に設問(2)で登場した公式を適用してみましょう.

 \displaystyle S(n+1,2) = nS(n,2) + S(n,1)
 
ここで,S(n,1) が登場してきました.

S(n,1) は,「n人の学生が1つの円をつくるように並ぶときの,並び方の総数」です.


何を隠そう,これは円順列なので,

\displaystyle S(n,1) = (n-1)!

となります.


つまり,

 \displaystyle S(n+1,2) = nS(n,2) + (n-1)!


次は,これを H_n の式に放り込んでみます.

 \displaystyle
\begin{align}
 H_n &= \frac{nS(n,2)}{n!} + \frac{(n-1)!}{n!} \\
     &= \frac{S(n,2)}{(n-1)!} + \frac{1}{n} \\
     &= H_{n-1} + \frac{1}{n}
\end{align}


おっと,ここで数列 (H_n) の漸化式が出てきましたね~

あとはこの漸化式を解いて一般項を求めれば,一丁上がりです.


とりあえずは力技で解いてみましょう.

 \displaystyle
\begin{align}
H_n     &= H_{n-1} + \frac{1}{n} \\
H_{n-1} &= H_{n-2} + \frac{1}{n-1} \\
&\vdots \\
H_3 &= H_2 + \frac{1}{3} \\
H_2 &= H_1 + \frac{1}{2} \\
H_1 &= \frac{S(2,2)}{1!} = 1
\end{align}

これらを下から順に代入していくと

\displaystyle
\begin{align}
H_n &= 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} \\
    &= \sum_{k=1}^{n} \frac{1}{k}
\end{align}

となり,一般項が求まりました.


別にこれでもいいんですが,もう少しきちんとした解き方も考えてみましょう.

階差数列を用いて一般項を求める方法について | 高校数学の美しい物語を参考にさせていただきました.


漸化式を整理すると,

 \displaystyle H_{n+1} - H_{n} = \frac{1}{n+1}

となるわけですが,これは (H_n) の階差数列が (\frac{1}{n+1}) になることを意味します.

この階差数列を (b_n) とおきます.
(つまり b_n := H_{n+1} - H_{n} = \frac{1}{n+1}.)


また,H_n

 \displaystyle
\begin{align}
H_n &= H_1 + (H_2 - H_1) + (H_3 - H_2) + \cdots + (H_n - H_{n-1}) \\
    &= H_1 + \sum_{k=1}^{n-1} (H_{n+1} - H_n) \\
    &= H_1 + \sum_{k=1}^{n-1} b_n
\end{align}

と書き直すことができます.

あとは,H_1, \, b_n を代入してやれば,先程と同じ答えが出てきます.

設問(4)

 \displaystyle \frac{\lfloor \mathrm{log}_2 \, n \rfloor + 1}{2} < H_n \le \lfloor \mathrm{log}_2 \, n \rfloor + 1

これが成り立つことを示せと言われているわけなんですが,なんとも手強そうですね…

n=5のとき

任意の n に対して成り立つかどうか調べる前に,まずは n=5 のときに成り立つことを証明します.

※この後に述べる「nが任意の自然数のとき」の証明方法を意識しながら書いています.


まず, 2^2 < 5 < 2^3 が成り立つので,各辺の対数をとって

 \displaystyle 2 < \mathrm{log}_2 5 < 3

となるので,

 \displaystyle \lfloor \mathrm{log}_2 5 \rfloor = 2

であることが分かります.

すると,示すべき不等式は

 \displaystyle \frac{3}{2} < H_5 \le 3

と書き直すことができます.


まずは,\frac{3}{2} < H_5 が成り立つかを確認します.


\displaystyle
\begin{align}
H_5 &= 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} \\
    &> 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} \\
    &> \frac{1}{2} + \frac{1}{2} + \frac{1}{4} + \frac{1}{4} \\
    &= \frac{1}{2} + \underbrace{\left( \frac{1}{2^1} \right)}_{2^0 個} + \underbrace{\left( \frac{1}{2^2} + \frac{1}{2^2} \right)}_{2^1 個} \\
    &= \frac{1}{2} + \frac{1}{2^1} + \frac{2^1}{2^2} \\
    &= \frac{1}{2} + \frac{1}{2} + \frac{1}{2} \\
    &= \frac{3}{2}
\end{align}

\displaystyle \therefore \frac{3}{2} < H_5


続いて, H_5 \le 3 が成り立つかを確認します.


\displaystyle
\begin{align}
H_5 &= 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} \\
    &< 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6} + \frac{1}{7} \\
\Bigg( &= 1 + \frac{1}{2^2-2} + \frac{1}{2^2-1} + \frac{1}{2^3-4} + \frac{1}{2^3-3} + \frac{1}{2^3-2} + \frac{1}{2^3-1} \Bigg) \\
    &< 1 + \frac{1}{2} + \frac{1}{2} + \frac{1}{4} + \frac{1}{4} + \frac{1}{4} + \frac{1}{4} \\
    &= 1 + \underbrace{\left( \frac{1}{2^1} + \frac{1}{2^1} \right)}_{2^1 個} + \underbrace{\left( \frac{1}{2^2} + \frac{1}{2^2} + \frac{1}{2^2} + \frac{1}{2^2} \right)}_{2^2 個} \\
    &= 1 + \frac{2^1}{2^1} + \frac{2^2}{2^2} \\
    &= 1+1+1 \\
    &= 3
\end{align}

\displaystyle \therefore H_5 < 3


以上より,確かに

 \displaystyle \frac{3}{2} < H_5 \le 3

を満たしていますね.

nが任意の自然数のとき

「n=5のとき」の証明法がここでも使えます.

きちんと証明してみましょう.

証)n が任意の自然数のとき,2^k \le n < 2^{k+1} を満たす整数 k \, (k \ge 0) が存在する.
すると,k \le \mathrm{log}_2 n < k+1 なので, \lfloor \mathrm{log}_2 n \rfloor = k.

よって,示すべき不等式は

 \displaystyle \frac{k+1}{2} < H_n \le k+1

と書き換えられる.

 \displaystyle
\begin{align}
H_n &= 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} \\
    &\ge 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{2^k} \\
    &> \frac{1}{2} + \underbrace{\left( \frac{1}{2^1} \right)}_{2^0 個} + \underbrace{\left( \frac{1}{2^2} + \frac{1}{2^2} \right)}_{2^1 個} + \cdots + \underbrace{\left( \frac{1}{2^k} + \cdots + \frac{1}{2^k} \right)}_{2^{k-1} 個} \\
    &= \underbrace{\frac{1}{2} + \cdots + \frac{1}{2}}_{k+1 個} \\
    &= \frac{k+1}{2}
\end{align}


\displaystyle \therefore \frac{k+1}{2} < H_n


\displaystyle
\begin{align}
H_n &= 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} \\
    &\le 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} + \cdots + \frac{1}{2^{k+1} - 1} \\
    &\le 1 + \underbrace{\left( \frac{1}{2^1} + \frac{1}{2^1} \right)}_{2^1 個} + \underbrace{\left( \frac{1}{2^2} + \frac{1}{2^2} + \frac{1}{2^2} + \frac{1}{2^2} \right)}_{2^2 個} + \cdots + \underbrace{\left( \frac{1}{2^k} + \cdots + \frac{1}{2^k} \right)}_{2^{k} 個} \\
    &= \underbrace{1 + \cdots + 1}_{k+1 個} \\
    &= k+1
\end{align}


\displaystyle \therefore H_n \le k+1


以上より,任意の自然数 nに対して

 \displaystyle \frac{k+1}{2} < H_n \le k+1

が成り立つことが示された.\blacksquare

 
 
 

解説は以上になります!

疲れた!


設問(4)とかは結構難しいけど,設問(2)なんかは受験生なら一度は解いておきたい問題な気がしますね.


(初見で分からなかったなんて言えない…)


でも(4)は自力で解いたからな(キレ気味



それにしても,こういう記事を書いてると受験勉強を頑張っていたあの頃が思い出されますなぁ…

一般の大学受験生はそろそろラストスパートをかけている頃ですよね.


受験生に幸あれ!


そんじゃあまたね~


次回:大学編入試験の過去問解説(3)-調和級数になりたかった級数