A path to combinatorics 第６章前半(最初-Ex6.5) 京都大学情報学研究科 通信情報システム専攻 岩間・伊藤研究室 M１ 西田 尚平 Ex 6.1 番号のついた３つの箱と５つのボールがある。どの箱に も少なくとも１つのボールが入っているように、ボールを 箱に振り分ける振り分け方は何通り存在するか？ １ ３ ２ ２ ５ ３ １ ４ 振り分ける数を固定して、それにどの番号を割 り振るかを考えるという数え方もあるが・・・・ 振り分け方を集合として考えると・・・・ S V1 S=振り分け方全体の集合 → 個 Vi=少なくとも箱 i が空の 振り分け方の集合 V３ V２ → 個 ViかつVｊである集合 → 個 定理 6.1 任意の 集合族 で以下の式が 成立する。これを包除原理という。 n個の要素の空集合 以外の全てのサブ セットを取ってきて、 その要素数+1回-1を 掛けてやればよい A1 A３ A２ 定理 6.2 任意の 集合族 成立する。 で以下の式が A1 証明はSからAのcapを 引けばいい A３ A２ 定理 6.3 集合に対するある関数 f を以下が成り立つもの とする。 するとある集合Aと、和集合がAになる集合族 において以下が成立する。 証明は定理６．１の物の絶対値をｆに変更すればいい Ex 6.2 １１１以下の素数を全部求めて下さい 全ての数が素数かどうか判定するのもいいが・・・ そもそもどんな数が素数では無いのか → 以下の素数で割り切れる数か１ そんな数を数え上げて１１１から引けばよい 具体的には、２、３、５、７の倍数となっているもの を数え上げる S １ ２ A２ ３ A３ S=１１１までの自然数集合 Ai= i の倍数の自然数集合 ５ ７ A５ A７ が求めたい答え を１１１以下の i の倍数の集合と定義する 今求めたいのは 包除原理より → i の倍数かつ j の倍数で i と j が互いに素 → 答えは２９個 Ex 6.3 ３＊３のマス目があり、その各マスを赤か青で塗る。各 マスが等しい確率でどちらかに塗られたとき、２＊２の 赤のみで塗られたブロックができる確率はいくらか を赤の四角形ができた時 i がその右上端になっているような盤面の 集合とする を赤の四角形ができた時 が起きている確率とする 求めたいものは 包除原理より式をcapの式に分解して 計算する 計算式はそのままな上資料に 書いてある通りなので省略 答えは Ex 6.4 １５０＊３２４＊３７５のブロックをもつジャングルジムが ある。その対角線に線を引いた時、その線はいくつの ブロックをまたぐか？ (3,2,2) (0,0,0) 赤いライン上の点は数式で(150t,324t,175t) と書ける そもそもラインが通過しているブロックってどんなの 線が通過し終わる時の点は 少なくとも一つの座標が自然数 少なくとも一つの座標が自然数に なっている点は赤いラインが通過 してるブロック１つに対応する このような点を カウントしていく を k 座標が整数になっているライン上 の点の集合とする 我々の知りたいのはどれかの点が 整数になっている点集合の数 ←包除原理 ある点でxとyが同時に整数になったとし、そ のようなｘ座標最小の点を（a,b）とする、する とその点は150と324をそれらのGCDで割るこ とで求められる。かつ同時に座標が整数に なる点は（ka,kb）と表せる。 先ほどの式に代入すると・・・ 解の768個を得られる Ex 6.5 どの４点も同一平面上に無い２ｎ個の点 がある。 その点間の区間のうち 個の区間を選ぶ。すると どんな選び方をしたとしてもそれらの区間によってｎ個 以上の三角形が構成されることを示せ。 n=3の時 補題 6.5 どの４点も同一平面上に無い２ｎ個の点 がある。 その点間の区間のうち 個の区間を選ぶ。すると どんな選び方をしたとしてもそれらの区間によって少なく とも１個以上の三角形が構成される。 証明： n=2の時はすぐにわかる nに関する帰納法、nまでで補題が成立すると 仮定すると・・・・ (n+1)の時、 個の区間が 選ばれる。グラフから次数の最も少ない2点とその 点に結ばれている区間を全て取り除く。 取り除かれる辺の数は高々 （ を(n+1)で割ったもの、つまり平均を超えない） 残った辺は少なくとも と2n個の点 Ex 6.5の証明： n=2の時はすぐに検証可能 nに関する帰納法、nまでで補題が成立すると 仮定する。今n+1を考えるが、補題6．5より 少なくとも一つの三角形が生成されている その三角形の３点をノード番号１，２，３とする。 →選ばれた枝で i と繋がっているノード集合 かつ →三角形ができる 少なくとも の三角形が存在する。 ここで包除原理より という関係式から・・・ 個 となるときは、点１、２、３できる三角形の数がｎを 超える→三角形１，２，３を含めてn+1個の三角形 ができて再帰が成立 では問題は の時 のどれか1つは2n-1を下回る ↑ 平均値以下のものが少なくとも1つ存在 一般性を失わずそうなる組を とおく この状態で点１，２とそれにつながっている枝を取り 除くとどうなるのか 残っている枝と点の数を考える 点： 2n 個 枝： 仮定より点３以降の点群で既に n 個の三角形が できる →三角形１，２，３を含めて n+1 個の三角形が できる →再帰が成り立って任意のnで問は成立
© Copyright 2024 ExpyDoc
