ちょっと、パー君連れてきて。

また、いつもの病気がはじまったか。


そしたら京都大学2010年度理系乙の第６問の解説です。

[問題]


n個のボールを2n個の箱へ投げ入れる。各ボールはいずれかの箱に入るものとし、どの箱に入る確率も等しいとする。どの箱にも1個以下のボールしか入っていない確率をp_nとする。
このとき、極限値
lim(n→∞)log(p_n)/n
を求めよ。


[解答と解説]
まずは確率の話からいっとこか。


例えばよくある間違いが2つの○と3つの×

○○×××××

から二つ選んだ時の組み合わせが○×になる確率は？

って言われると

○○

○×

××

の3通りやから、

1/3

とかやってたら間違いやねん。

普通に考えて1/3なわけがないしな。

答えは

2C1×5C1/7C2


何故間違えたのかと言うと、そもそも確率って言うものは求まらないねん。

実はこの問題はこれ以上分けられない事象、つまり○や×を一つとりだす事象を考えると、

根元事象の確率は全部同じで1/7C2である

って言う暗黙の了解があるから確率が求まるねん。

1/7C2が何個あるかって話しやねん。


この確率が同じって言うのを同様に確からしいとか言うねんけどな。


こうやって確率は、確率が定義されいるから求められるわけであって、よく書かれてる

(事象Aの起こる場合)/(起こりえる全ての場合の数)

と言う書き方は誤解が生じやすいねん。


だからこう考えてくれ。



『根元事象の確率が全部pの時(同様に確からしい時)、

p=1/(根元事象の総数)であり、事象Aの起こる確率は

P(A)=(事象Aに含まれる根元事象の数)×p』


このpが何個あるか数える話とか、根元事象の総数とか求める時に、場合の数の理論を使ってるってことなだけやねんな。

また確率と場合の数の違い、同様に確からしいとは…も参考にｓｋてくれ。


それで結局どうしたらええのかって言うと、この問題なら



n個のボールや、2n個の箱に

ボール1,ボール2,ボール3,…

とか

箱1,箱2,箱3

とか名前をつけて考えたらやりやすいねん。

スライムA,スライムB,スライムC…

みたいなノリや。

それでスライムを区別するねん。


じゃあ早速求めていこか。

確率は説明文を書くと長ったらしくなるから、絵で説明するようにしたってください。



ボールkが箱1～2n入れるのは2n通りです。

全体の総数は2n×2n×2n×…×2n=(2n)^n通り

まあ根元事象の確率が1/(2n)^nってとこやな。


それで各ボールをどの箱にも1個以下に入れるには、箱の方をn個選んでボール1～nに並べていけばいいから
2n_P_n通り

一個以下になる根元事象は2nPn個やな。

よって

p_n=2n_P_n/(2n)^n


これはさすがによくあるパターンでした。


それでこの

log(p_n)/n

を考えるわけやねんけど区分求積法を使うことになります。


これは経験的に数学3やってるとlogの中に順列のPとかnのn乗とか入ってると、logの足し算になるからだいたい区分求積ってことはわかってきます。


区分求積は



lim(n→∞)Σ(k=i(n)～j(n))1/n×f(k/n)

と言うように

1/nとf(k/n)の形を無理やり作っていきます。


それで1/nをdxにk/nをxにして

∫(a,b)f(x)dx

としたらオッケーです。

この積分区間はk=i(n)～j(n)まで足す場合は

i(n)/n→a,j(n)/n→b(n→∞)

と言うようにnで割った極限になります。


例えばi(n)=2n+1,j(n)=3n
やったら2≦x≦3で積分やな。

またk=4～n+2まで足そうがk=3～n+543まで足そうが、どっちも積分区間0≦x≦1で同じなわけやな。

これは、高校では細かいことやらないねんけど、連続関数は有界閉区間でリーマン積分可能やから、リーマン和が分割の仕方によらずある値に収束するからやねん。


だから高校では連続で有界な閉区間でしか積分しないから細かいこと考えなくても大丈夫ってことです。

と言うことで計算していくと



1/nは元々あるから、k/nを作っていけばいいわけです。


n!とn^n乗の組合わせでは

n!/nr^n=n(n-1)(n-2)…1/nnnn…n
=1/n×2/n×…×n/n

ってそれぞれバラしていって、くっつけいくパターンでだいたい上手くいくねん。


2n_P_n/(2n)^n=2n(2n-1)…(2n-n+1)/(2n)(2n)…(2n)
=1・(1-1/2n)…(1-(n-1)/2n)

って言うとこやな。

log(p_n)/n=1/n・log(1・(1-1/2n)…(1-(n-1)/2n))
=Σ(k=1～n-1)1/n・log(1-k/2n)
→
∫(0,1)log(1-x/2)dx

これはもう置換積分と言うほどでもないけど、一応
1-x/2=t
とおくと
-dx/2=dt

x 0 1
t 1 1/2

よって

-2∫(1,1/2)log(t)dt=-2[tlog(t)-t](1,1/2)
=log2-1


京都大学の入試の数学の過去問の解説

今、ポン酢の瓶で頭どつかれた時の気分や。


と言うことで、京都大学2010年度理系乙第５問の解説をしたいと思います。

[問題]


(1)nを正の整数,a=2^nとする。
3^a-1は2^(n+2)で割り切れるが2^(n+3)では割り切れないことを示せ。
(2)mを正の偶数とする。3^m-1が2^mで割り切れるならばm=2またはm=4であることを示せ。
[解答と解説]
こういうn乗とかの整数問題を見たら、だいたい反射的に思いつくのは

○二項定理
○a^n-b^n=(a-b)(a^(n-1)+a^(n-2)b+…+b^(n-1))
○数学的帰納法

やと僕は思います。



なんか二項定理を使えとか、a^n-b^nを使えとかなんか変なんが言うてるな。


そしたらまずは二項定理いっとこか。



二項定理を使うって言うのは、例えば

7^nを3で割った余りが1であることを示そうと思うと

7^n=(6+1)^n
=n_C_0・6^n+n_C_1・6^(n-1)+…+n_C_(n-1)・6+1
=6(n_C_0・6^(n-1)+n_C_1・6^(n-2)+…+n_C_(n-1))+1

とか言うように
7=(3の倍数)+(余り)
にして展開することで、(3の倍数)がある項は3で割れるから、7^nを3で割った余りは結局(余り)^nを3で割った余りと同じになるねんな。

まあこの場合は7^n≡1^n=1って言うように合同式を使えばええにはええねんけど、他にも色々なシーンで使います。


と言うことで使ってみますね。


2が問題になってるから、3=2+1にして

3^(2-n)=(2+1)^(2^n)-1
=(2^2^n+2^n_C_1・2^(2^n-1)+2^n_C_2・2^(2^n-2)+…+2^n(2^n-1)(2^n-2)/(3・2・1)・2^3+2^n(2^n-1)/2・2^2+2^n・2+1)-1

2^(n+2)でくくって…いや、n_C_kの分母の方にも2が入ってるやろうか…


ってやってると



ぶほー！！

血吐きます。


みんなもこんなことならないように。

まあやろうと思えば出来るんかもしれんけどな。



そしたら、今度は



a^n-b^n=(a-b)(a^(n-1)+a^(n-2)b+…+b^(n-1))
を使うと言うことは、どういうことかと言うと

この因数分解の式は実は、等比数列の和と言う解釈も出来るねんな。

初項a^(n-1)、公比b/a、項数nの等比数列の和を考えると

a^(n-1)+a^(n-2)b+…+b^(n-1)=a^(n-1)(1-(b/a)-n)/(1-b/a)
=(a^n-b^n)/(a-b)

これはb.a≠1つまりb≠aの時になりたつ式で、b-aを両辺にかけると

(a-b)(a^(n-1)+a^(n-2)b+…+b^(n-1))=a^n-b^n

この形にするとa=bでも両辺0で成立するから、いけるねん。


と言うことで、これを使ってみると

3^(2^n)-1=(3-1))(3^(2^n-1)+3^(2^n-2)+…+3+1)
=2(3^(2^n-1)+3^(2^n-2)+…+3+1)

…

ってやってみると、あんま関係ない感じがしてきて




角に追い詰められて、膝蹴りかまされまくります。


みんなもこんなことならないように。



やっぱ、あほの言うこと聞いてたらなあかんな。

と言うことで数学的帰納法を今度は使ってみるか。

数学的帰納法を使うと言うことは、条件を式に表すのがコツです。



この2^(n+2)で割れるが、2^(n+3)で割り切れないを式にするには、2が何個あるかってところがポイントになります。

2で何回割り切れるかやな。

2^(n+2)個あれば、2^(n+2)で割れるけど2^(n+3)では割り切れなくなります。

そこでこういう書き方をするねん。

3^a-1=2^(n+2)・p
(pは奇数)

2を全部前に持ってくると、残りは奇数やん。

この表現はたまに使うから、覚えておいて欲しいとこやな。


正確には素因数分解すると、2以外の素数が奇数やから残りは奇数の掛け算で奇数になるわけやな。


じゃあ早速やってみよか。



(1)「3^a-1は2^(n+2)で割り切れるが2^(n+3)で割り切れない」…(*)
(*)をnに関する数学的帰納法で示す。

(i)n=1のとき
3^2-1=9-1=2^3

これは明らかに(*)成立




(ii)n=kのとき(*)成立を仮定すると
3^(2^k)-1=2^(k+2)・p(pは奇数)
とおける。

これから
3^(2^k)=2^(k+2)・p+1
でn=k+1の形の3^(2^(k+1))に代入するねん。

3^(2^(k+1))-1={3^(2^k)}^2-1
=(2^(k+2)・p+1)^2-1
=2^(2k+4)・p^2+2^(k+3)・p
=2^(k+3)(2^(k+1)・p+1)・p

と2^(k+3)でくくって、

2^(k+1)・p+1は奇数やから、(2^(k+1)・p+1)・pも奇数。

だから

2^(k+3)×(奇数)

の形やから、n=k+1も(*)成立と言えます



はい、上手くいきましたね。

まあちょっと難しいかもしれんけど、整数問題で一応はよく使う処理のパターンやから、こんなんがあったなと覚えといてください。


(2)

同じく2で何回割り切れるかの問題やけど、これはやっぱり(1)がヒントやねん。

それを覚えて欲しいねん。

確かにたまに前問の誘導に乗らない方が解けることもあるねんけど、基本は前問の結果が使えないかって言うのを考えるって言うこういう処理の仕方まで覚えて欲しいねん。

そういう力をつけるのが、わんこら式やねん。

なんか、たくさん勘違いされてるけどな。


それでも、この問題ではちょっと難しいねんな。

さっきはa=2^nやったけど、mは正の偶数と書いてるだけやねん。

だから(1)のようにやるとすると

m=2^j・q(j≧1,q:奇数)

ちょっとこのqの分、a=2^nと違うねんな。




でもこれは指数の部分になるわけやから。

3^((2^j)・q)=(3^(2^j))^q

とやれば、なんだかイケそうな気がします。


こっちがそう思ってるだけの時もよくあるけどな。

まあ、色々ありますわ…


ちゃうねん、泣いてるんちゃうねん。

涙が流れてきてるだけや。


そしたらやってみよか…



mは正の偶数より

m=2^j・q
(jは自然数,qは奇数)
とおける。

3^m-1=(3^(2^j))^q-1

(1)より3^(2^j)-1=2^(j+2)・r
(rは奇数)
とおける。

これで
3^(2^k)=2^(j+2)・r+1
で代入していくわけですわ。

まあこの時に、
a^n-b^n=(a-b)(a^(n-1)+a^(n-2)b+…+b^(n-1))
を使っても3^(2^k)の形を作れて示せるねんけど、

現実的に思い付きそうで、現実的に処理できそう、機械的に解けると言う現実路線をとっていくのがわんこら式やから、ただ単に代入でいきます。

3^m-1=(3^(2^j))^q-1
=(2^(j+2)・r+1)^q-1
=Σ(k=1～q)q_C_k(2^(j+2)・r)^k+1-1
=2^(j+2){2^(j+2)Σ(k=2～q)q_C_k(2^(j+2)^(k-2))・r^k+qr}
=2^(j+2)((偶数)+(奇数)×(奇数))
=2^(j+2)・(奇数)

これで3^mｊが2でj+2回まで割り切れることがわかりました。



と言うことは、3^m-1が2^m=2^((2^j)・q)で割り切れるには

2^j・q≦j+2

であればええことになります。


これは一次関数より指数関数の方が全然増加の仕方が大きいから、jが小さい値でしか成り立たないってことは予想できます。

よく指数関数的に増えるとか言うしな。

y=xにx=1を入れれば1,x=10を入れても10やけど、y=2^xにx=1を入れれば2,x=10を入れれば1024で全然大きくて立派です。

と言うことでjは小さい値でしか成り立たないやろうから、j=1から入れていくと

j=1のとき2q≦3
これを満たすqはq=1だけです。
だから
m=2
って一つ決まりました、

j=2のとき4q≦4
これを満たすqはq=1だけ。
m=4
これでもう一つ決まった。

これでぎりぎりやからj≧3ではもはや成り立たないやろな。


j≧3ではたぶん
2^j・q＞j+2やねん。

それをどういうかは、ちょっとだけめんどくさいな。

こういう時によくあるのが、
r＞1の時
n/r^n→0(n→∞)
を証明する時に、指数r^nと整式nは比べられないから
r^n=(1+h)^n
≧n_C_0+n_C_1h+n_C_2h^2
＞n_C_2h^2
=n(n-1)h^2/2

ってやることで

0＜n/r^n2＜n/(n(n-1)h^2/2)=2/(n-1)h^2→0

と言うように指数関数に二項定理を使うことで整式に落とすことが出来て、比べることができたわけやん。

指数と整式の大小関係ではこの発想を使って、整式同士にして比べるねん。


と言うことで適当にあわせていって

j≧3のとき、2^j≧j_C_0+j_C_1+j_C_2
より
q{1+j+j(j-1)/2}-(j+2)
=(q-1)j+q-1+j(j-1)/2-1≧0+0+3・2/2-1＞0

よって2^j・q＞j+2

これでm=2,4だけと言えました。



最後のはえらく思いつきで0以上になるように数字の組み合わせを作っていって不等式を証明してるけど、数学的帰納法を使えばもっと機械的にすっきり簡単にいくねん。

ただ整式同士にしてから比べる発想は同じやけどな。




j=3の時は明らかで100円やるから許してください。

j=kの
2^k・q＞k+2
が成り立つ時に、2^(k+1)・q＞(k+1)+2が成立することを示したい。

これで整式同士で比べるためには2^k・q＞k+2の両辺に2をかけて
2^(k+1)・q
の形を作ると、

2^(k+1)・q＞2k+4

これで(k+1)+2と2k+4を比べるねん。

2k+4-((k+1)+2)
=k+1＞0

よって

2^(k+1)・q＞(k+1)+2

が示せました。


さすがに疲れたな。

はよモンスターハンターやりたい。


京都大学の入試の数学の過去問の解説

整数問題の解法の解説と問題演習

わんこら式数学の勉強法を解説したDVDが買えます。

以下の申し込みフォームから、購入できます。

わんこら式DVDお申し込みフォーム


ブログの文章だけと違って、実際動いて説明する動画の方が印象に残ってわかりやすいってことがあるみたいなので、良かった購入してください。