Mathematics that the professor loved 徳山豪東北大学 Combinatorics that professors love 博士たちの愛する組合せ論内容 • 組合せ数学の美しさ • 『当たり前のこと』の威力 – Pigeon hole (鳩の巣）原理 – Double Counting：二通りに数えてみよう • Paul Erdosが天才を探すときの質問 – ２００以下の自然数が１０１個あるとしよう。以下の2つの命題は正しいか？ • 互いに素(公約数が１）な2つの数が必ずある • 約数の関係(小さい方が大きい方を割り切れる）にある2つの数が必ずある。鳩の巣原理 • Ｎ羽の鳩がM個の巣箱に入っていると • N/M 以上の鳩が入っている巣がある – N=M+1だと、(整数なので）2羽以上の鳩が入っている巣がある • （数学的に言うと）有限集合Sから有限集合T への写像Fがあり、|S|=N, |T|=Mなら F-1 (t) = { s ∈ S： F(s)=t } とすると、 |F-1(t)|≧N/Mであるｔ∈Tが存在する鳩の巣原理を使おう：１ • ２００以下の自然数が１０１個あるとしよう。 – 互いに疎な2つの数が必ずあることを示せ • 鳩＝101個の自然数。 N=１0１ • 巣をどうするかが腕の見せ所。 – （1，2), (3，4),…, ( i, i+1),…,(199,200) – 100 個の巣。 M=100 – N=M+1なので、２羽以上が入っている巣がある – （k, k+1) この二つは互いに素。鳩の巣原理を使おう：２ • ２００以下の自然数が１０１個あるとしよう。 – 約数の関係(小さい方が大きい方を割り切れる）にある2つの数が必ずあることを示せ。 • 鳩＝101個の自然数。 N=１0１ • 巣：（1,2,4,8,..), (3,6,12,24,..),(5,10,20,..), ( 2i+1, 2(2i+1),4(2i+1),…),…, (197), (199) – 200以下の奇数は100個なので100 個の巣。 – 同じ巣に入る2羽の鳩が居る。 – 約数の関係（実際は2のべき乗倍）にある。鳩の巣原理：上級編 • 長さｎの(異なった）実数の列 a1,a2,…,anがある。このとき、長さｎ１/2 以上の部分列で、単調増加あるいは単調減少であるものが必ず存在することを示せ。（Erdos-Szekeresの定理） – 徳山は大学院時代に証明に四苦八苦した。 – 数多くの高度な応用がある（講義では紹介しない） – 面白い「鳩の巣」を作る。 Erdos-Szekeresの定理の証明 • • • • • 長さｎの実数列 a1,a2,…,anがある。ｑ = n ½ 未満の最大整数 L(j)：aj から始まる増加列の最大長 S(ｋ）＝｛aj: L(j)=k } S(1), S(2),..,S(q): 鳩の巣 – 巣に入らない鳩が居れば、長さq+１以上の増加列がある。 – 全部の鳩が巣に入れば、q+１羽以上が入る巣がある。 • その巣に入る要素からなる部分列は単調減少列になる – なぜでしょう？ – よって証明終了 (判ったかな？）二重数え上げ法 • 同じものを２通りに数えることで定理を証明する • 例題１：自然数ｍの約数の数をｆ（ｍ）とする。（１/ｎ）∑１≦ｍ≦ｎｆ（ｍ）を(誤差２の範囲で）求めよ • 例題２：グラフの次数とは、その頂点から出る辺の数である。５頂点のグラフで、全ての次数が３であるグラフは存在するか？存在するのなら構成せよ。二重数え上げ法 • 例題１：自然数ｍの約数の数をｆ（ｍ）とする。（１/ｎ）∑１≦ｍ≦ｎｆ（ｍ）を(誤差２の範囲で）求めよ • （k,ｍ）ｋはｍの約数、m≦ｎである対の数を２通りに数える。 – ｍでまとめると、 ∑１≦ｍ≦ｎｆ（ｍ） – ｋでまとめると、どうなりますか？二重数え上げ法例題２：グラフの次数とは、その頂点から出る辺の数である。５頂点のグラフで、全ての次数が３であるグラフは存在するか？存在するのなら構成せよ。 • 「頂点と辺の対(v, e): 頂点vは辺eの端点」を２通りに数える – ｖでまとめると、次数の和 – e でまとめると、何ですか？二重数え上げ法(上級編）問題３：ｎ個の単位円(半径１の円）がある。円たちの交点のうちで、次数（交わっている円の数）の多い方からｎ点の集合Sを選ぶ。このとき、次数の和がｎ3/2以上にならないことを示せ。 • 使うべき事実： 2点を通る単位円は高々2個しかない • 数えるべきもの（p, C1,C2) pはSの要素、C1,C2 はpを通る円二重数え上げ法(上級編）の利用 Erdosの距離重複度問題：平面上にｎ点がある。これらの点の点対で同一の距離ｄにあるものは最大いくつあるか？？？先ほどの問題から：ｎ3/2 以下現在知られている最善：ｎ4/3 以下もっと少ないはず。（ｎの定数倍よりは大きい）二重数え上げ法(上級編）の利用平面上にｎ点が正方格子状に配置してある。 1点から距離1の点はいくつ？ 1点から距離５の点はいくつ？ 1点から距離６５の点はいくつ？ラグランジュの整数二次形式の理論一般に、大きい距離はたくさん出てくる問題：正方格子より本質的に距離重複度の大きい配置はあるだろうか？誰かチャレンジしませんか？ (博士号＋海外留学は保証します）。組合せ論の美の典型 • Brouwerの不動点定理(1912) – 「中間値の定理」の一般化 – 幾何、解析、プログラム基礎理論、情報理論などの基本定理 • Ｄ次元の球BからBへの連続写像ｆは必ず不動点（ｆ（ｘ）＝ｘである点ｘ）を持つ。 • オリジナルの証明：高等な解析と幾何を利用 • 天才Sperner(23歳）の初等的証明（１９２８） – これは来週（二次元の場合のみ。乞うご期待）