Complete GraphのHamilton cycle(path)への分割

Modern Graph Theory/Bela Bollobasからあまりウェブ上にないトピックをば.
・r-正則グラフとは
無向グラフで全ての頂点からr本の枝が出ているものを言います.
特に
頂点数をnとして(n-1)-正則グラフのことを完全グラフと言います.
・ハミルトン閉路/パス(Hamilton cycle)とは
全ての頂点を重複なく通過する閉路/パスのことを言います.
あるグラフ上にハミルトン閉路が存在するかという問題は
ハミルトン閉路問題と呼ばれ,それなりに難しいクラスの問題(NP-完全)であることが分かっています.
しかし完全グラフの場合そのグラフにハミルトン閉路/パスが存在するかどうかは次のように分かります.
(互いに辺素とは2つのグラフが同じ辺を使用していないことを言います)

定理:
任意のn に対して
nが3 以上の奇数ならばKn(n個の頂点
を持つ完全グラフ) は
(n-1)/2個のHamilton cycle に分割できる.n が2 以
上の偶数ならばKn はn/2 個のHamilton path に分割できる.


証明:
n が偶数(2k) の時を考える.各ノードに0,1,2,3,...,k,...,-3,-2,-1 と番号付
ける.この時s,s+1,s-1,s+2,s-2,s+3,s-3,...,s+k とパスを取ればこれはハミルトンパス
である.このパスを始点 を0 からk-1 まで変化させてk-1 個のパス を取る.

図1:n=6の時のハミルトンパスの取り方

(ノードの番号付けはなんだって構いません.)
各頂点 において
端点のノードの番号の差の絶対値の同じ枝は2つあり
それぞれ異なるパス に属するから,
このパスが辺素であることがわかりn が偶数の時には示せた.
n が奇数の時には一つの頂点を固定し
その頂点を除去したグラフはK(n-1)になる
このK(n-1)に対して同じようにHamiltonpath を取り,

図2:n=7の時のハミルトンサイクルの取り方

その始点
と終点に対して固定した頂点から枝 を張れば,
辺素なハミルトン閉路 になっている.

つまりnが偶数の時にギザギザにパスを取りハミルトンパスでかつ
互いに辺素であることを示し,
nが奇数の時は一本間引いて偶数の場合に帰着させれば良いという感じです.
ギザギザのパスはなかなか気づきません.

結婚式

サークルの先輩の結婚式・披露宴・二次会に参加させていただきました.
結婚式というものが(主体的に参加することが)初めてだったため,
何故か非常に緊張しましたが,
教会での厳かな式で結婚というものを改めて良い意味で考えさせられ,
お二方の晴れ姿がとても眩しかったです.
(ちょうど外での撮影の際に晴れ,虹が出ていたのは素晴らしい!)
披露宴は非常にフランクというかアットホームな感じで,
調子に乗って飲み過ぎてしまった感じが…
お二方とお話することもでき,
懐かしいというかなんというか,
輝かしいというかなんというか,
いろいろな感情が込み上げてきました.
披露宴会場で新郎新婦の先輩,ご両親のお言葉で思わず涙腺を刺激されましたね.
(そうなることはわかっていても,やはり素晴らしい.)
二次会はゲームで2つも景品を取ってしまい,
申し訳ないなと思いつつもとても嬉しかったですね.
もっと沢山の方とお話できたらなぁとは
このような場があるたびに思うのですが,
久しぶりに会う同期は頼もしくなっていたし,
先輩方は立派な社会人としてご活躍されているようで眩しかったです.
明日も早いため残念ながら三次会には出席できませんでしたが,
また近いうちに出会えたらなぁと本当にそう思います.

何故か,ブログで.

不等式評価

大学入試問題において不等式評価が問題になる時は
大抵難しいこと(シビアな評価を訊いていること)が多い.
[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らしい.