不等式評価

Texも長らく使っていなかったので,勘を戻すために作ってみる.
問題は複素解析(東大出版会)の本から.
不等式評価の問題だけど個人的にすぐ考えつかなかったので,参考程度に.

不等式評価

大学入試問題において不等式評価が問題になる時は
大抵難しいこと(シビアな評価を訊いていること)が多い.
[nは正の整数です。不等式(n!)^2≧n^nが成り立つことを示してください。(06,新潟大)]
不等式評価の定石は
数学的帰納法/式変形/関数の形を用いる
の三つに分類することができる.
この問題の前に次の不等式の評価を行っておくと便利である.
自然数nに対して
n^n≧(n+1)^(n-1)
まず,自然数nを実数xに拡張した次の関数の評価を行う
f(x)=xlog(x)-(x-1)log(x+1)
微分して
f'(x)=log(x)+1-log(x+1)-(x-1)/(x+1)
=log(x/(x+1))+2/(x+1)
もう一回微分して
f''(x)=1/x-1/(x+1)-2/(x+1)^2
=(x-1)/x(x+1)^2

従ってf'(x)はx≧1で単調増加するので,
f'(x)≧f'(1)=log(e)-log(2)>0
となるので,
f(x)はx≧1で単調増加である.

よってf(n)≧f(1)=0であるので,
nlog(n)-(n-1)log(n+1)≧0であり,
n^n≧(n+1)^(n-1)を得る.

この不等式評価を利用して,
最初の問題を解いてみよう.
まずn=1では自明に成立する.
n=kの時の成立を仮定すると,
(k!)^2≧(k)^k
上の式の両辺に
(k+1)^2を掛けても不等式評価は変化しないので,
(k+1)^2*(k!)^2≧(k+1)^2*(k^k)
(k+1!)^2≧(k+1)^2*(k^k)
ここで左辺に対してn^n≧(n+1)^(n-1)の評価を行うと,
(k+1!)^2≧(k+1)^2*(k^k)≧(k+1)^2*(k+1)^(k-1)
よって
(k+1!)^2≧(k+1)^(k+1).
kの時仮定してk+1での成立も示せたので数学的帰納法より
任意の自然数nについて成立することがいえる.

個人的にはn^n≧(n+1)^(n-1)という不等式評価が
なかなか好きですね〜.

整数はおまかせ

京都大学2006年度理系第一問
[Q(x)を2次式とする.整式P(x)はQ(x)では割り切れないが,{P(x)}^2は
Q(x)で割り切れるという.このとき2次方程式Q(x)=0は重解をもつことを示せ.]
代数学の基本定理より
Q(x)は複素根を2つ持つ.
P(x)が整数係数多項式なので,
一意分解整域(素因数分解の一意性が成り立つ)である.
ここでの既約元(素因数)とはそれ以上割り切れない
整数係数多項式である.
ここでQ(x)が重解でないと仮定すると,
b≠cの複素数を利用して
Q(x)=a(x-b)(x-c)と書ける.
一方,P(x)=Π{n}{i=1}Pi(x)と素因数分解する.
Q(x)|P(x)^2より
(x-b)|Pi(x)^2 and (x-c)|Pj(x)^2
1≦i,j≦n
である.
ここでPiを複素根を用いて分解すると,
(x-b)がそのどれかの二乗と一致せねばならず,
結果的に(x-b)|Pi(x)と(x-c)|Pj(x)
が成立しなければならないが,
これはQ(x)|P(x)と同じことなので矛盾する.

整数係数多項式は素因数分解の一意性が成立するという
ことを知っていれば上のようにうまくいくけど,
実数係数の多項式は解を複素数まで拡大してやると
一次式の積で書けるという事実も利用している.
これが一番最初に書いた代数学の基本定理.
この証明に関しても時間があれば載せたいなぁ….

ヨセフスの問題

問題
[4000枚のカードが1から順に並んでいます.一番上のカードを一番下にもっていき,次のカードを捨てるという作業を繰り返した時,最後に残るカードは何番か]
たけしのコマ大数学科で出題された問題が元ネタらしい.
偶数番号のカードを全て削除した状態毎に
一番上のカードと一番下のカードを考えてみる.

まず元のカードは1...4000と順に並んでいる.
次に偶数番目のカードを全て削除した時,
奇数が書かれているカードが残る.
次にこの状態から偶数番目のカードを全て削除したとき,
4で割って1余る数が書かれているカードが残る.
次にこの状態から…という操作を考えたとき,
カードの枚数が偶数枚だと一番上のカードは変化しないこと
一番下にあるカードは削除されること
に気付く.
これがカードの枚数が奇数枚の時,削除を行うと
一番上のカードはその前の状態の一番最後のカードに変わる.

そしてこの状態では
その前の状態まで一番上にあったカードが
削除されてしまう.
このことに注意しながら
カードの枚数と一番上のカードと一番下のカードが
どのように変化するかを調べてみると
枚数 上 下
4000 1 4000
2000 1 3999
1000 1 3997
500 1 3993
250 1 3985
125 1 3969　 …カードの枚数が奇数
63 3969 3905 …カードの枚数が奇数
32 3905 ////
16 3905 ////
8 3905 ////
4 3905 ////
2 3905 ////
1 3905
というわけでめでたく3905が最後に残ることが分かる.
一番下のカードを調べる際に
前に一番下にあったカードに書かれていた番号との差が
2のべき乗になっていることに注意すれば
間違えること無く追っていけるはず.
原題では200枚だったらしいので注意深く追っていけば,
番組終了時間内に解答出来るかもしれないけど,
なかなか難しいなぁという印象.

ちなみにHaskellでのコーディングを試みた.
elim (x:xs) = if length xs == 1 then [x] else elim $ tail xs ++ [x]
停止条件をリストの長さが1になると設定して
再帰を利用する.
えっと,Haskellを長らく使っていなかったので
すっかり忘れていた(涙
このプログラムによると
200枚で最後に残るのは145
4000枚で最後に残るのは3905
10000枚で最後に残るのは3617らしい.

評価すること

院試向けに微積分の復習をしています.
Stirling's approximation(スターリングの公式)

は,n!を近似で評価しようというものです.
階乗はnがそれほど大きくなくてもすぐ発散してしまうので
計算が難しいです.ですから
比較的手に追える式に落としこんで評価することが
できると嬉しいことが多い…ﾊｽﾞﾃﾞｽ.
スターリングの公式の肝は,
logxという関数の積分の評価です.
ざっくりと天下り式な証明を紹介します.
スターリングの公式を導くにはウォリスの公式を使う形に
なんとしても持っていくという方針に従えば
証明を見失うことはないと思います.
天下り的に次の数列の評価を行います

この数列は(n!)をn^(n+1/2)*e^(-n)で評価することを考えて出てきます.
この時,

であり,

を利用してやると,

を得ます.
ここで更に二つの数列a_n,b_nを次のように定義してやります.

a_n < b_n
であり,
d_n -d_(n+1)の不等式評価より,
a_1 < a_2 < a_3 < ... < a_n < ... < b_n < ... < b_1
を得る.
ここで,
b_n = a_n * exp(1/12n)なので
b_n - a_n -> 0(n -> 0)である.
よってカントールの公理より二つの数列は収束することになる.
ここで,a_n,b_nの収束性より0<θ<1となるθを用いて

と表せる.
ここまで来たらウォリスの公式

にαの式を代入してやって,
α=1を得る.
ゆえに,b_nの収束値がαであることから,
スターリングの公式を得る.
うはぁ…結構厳しいのね.

確率論ではそこそこ使われたりするので覚えておいて損はないかも…

ちなみにこの評価の相対誤差は,
(1-exp(-1/12n))です.(上の評価式から直ちに導けます.)

2010/3/15の日記の転載:Brachistochrone curve

つい先日お台場にあるPanasonicセンター東京内のRisuPiaに行った際に,
「決まった二点間で曲線に沿ってものを落とした時に
最下点まで一番早く到達する曲線は何か？」
という問題に出くわしました.
答えはあまりなじみのない曲線に行きつくのですが,
変分法を用いて導き出すことができます。
便宜上二点間をA(0,0)B(x,y)ただしy>0と置く.
xの関数yの汎関数I[y]が極値を取る場合に
オイラー・ラグランジュ方程式を満たすことを思い出します.
この場合の汎関数はAからBまでかかる時間として、
時間がs(曲線の長さ)/v(速度)を積分したもので与えらるので,

と表わされます.
ここでv(x,y)はエネルギー保存則よりyの関数として与えられます.
この積分の中のFをオイラー・ラグランジュ方程式に代入して解いていきます.
Fがxに陽に依存しないために,
オイラー・ラグランジュ方程式は簡単になって,次のように解けます.
上の式の前半はベルトラミの定理というもので,
Fがxに陽に依存しない場合に
オイラー・ラグランジュ方程式が簡単になるので比較的有効な手段です.
下の微分方程式を満たす曲線が求めるべき曲線ですが,
これはサイクロイドと呼ばれる曲線の満たす微分方程式となります.
サイクロイドは媒介変数で表わされる曲線で,θを媒介変数とすると,
という風に表わせます.
この曲線が最速降下曲線となるのですが,
実はサイクロイドには面白い性質があり,
どこから落としても最下点に辿り着く時間は一定となります.
東京大阪間がだいたい400kmとして,
一番初めのT[y]の式を解くと,

ここでAは定数で2Aπ=xで
東京大阪間に摩擦の無いサイクロイド型のトンネルを作ったならば,
約500秒(8.3分)で東京まで着くことになります.
この時最下点での物体の速度はエネルギー保存則より
約1.6[km/s]ということになり,
海面上で気温15℃の時に音速が340[m/s]なので
音速の4倍以上ということになります.
もともと上記の問題は
手元のE.ハイラー/G.ヴェンナーの[解析教程]

解析教程〈上〉

によると
ヨハン・ベルヌーイがコンテストとして公に提示した問題で、
締め切りまでには多数の解答が寄せられたそうですが,
自らの解答が最もエレガントだったそうです.
その方法はフェルマーの原理のアナロジーを利用するというものでした。
それは速さが物体の速さがv=sqrt(2gy)で与えられるような層を
いくつも考えるというものでした.
ところで、このヨハン・ベルヌーイという人は
天下のベルヌーイ一族の中でもくせものだったらしく,
微分についてのニュートンVSライプニッツ論争が起こっている際には
率先してライプニッツに加担したり,
兄のヤコブ・ベルヌーイとは常に衝突ばかり.
挙句の果てには息子のダニエル・ベルヌーイの業績を盗もうとしたとか.
もちろん何が真実で何が嘘なのかは今となっては分かりませんが,
天才にはスキャンダルやルーマーはつきものですね。
ところで,抵抗・摩擦を含めた際の最速降下曲線はどんな形になるのでしょうか？
気になるところですね.

周期性

数学オリンピック予選問題（2000年1月10日）
[40C20(Cはコンビネーションを表す)を41 で割った余りを求めよ]
というシンプルな問題.
今朝解いて面白かったので掲載.
手に負えなそうな数が出てきた場合は身近なところから計算してみると
答えにたどりつきやすいかも？
40C0 = 1 は41で割ると1
40C1 = 40は41で割ると40
40C2 = 780は41で割ると1
40C3 = 9880は41で割ると40
この辺で不思議な周期性に気づくと解答に近づく(と個人的に思います)
コンビネーションの性質
nCm = (n-1)Cm + (n-1)C(m-1)を思い出すと,
41C1 = 40C0+40C1
41C2 = 40C1+40C2
…
41C20 = 40C19+40C20

ところで41Cn(nは1以上40以下)は41で割りきれるので
この周期が出てくる.つまり40C0 = 1　mod 41なので
40Cnを41で割った数の列は隣同士足した数が41で割り切れなければなりません.
この数列は初項が1なのでこの数列は
{1,40,1,40,1,40,…}という形になり,
従って答えは1となります.

注：41Cnが41で割り切れるというものは一般のp(素数)に対して
示すことができます.
rを1≦r≦p-1となる自然数とすると
r * pCr = p * (p-1)C(r-1)
より右辺がpで割りきれ,rはpで割り切れないために
pCrはpで割り切れなければならない.
つまり,この性質により,
一般の素数pに対して(p-1)Cr mod p が分かります.

注:n mod mとは,nをmで割った時の余りを表します.