博士たちの愛する組合せ論 徳山 豪 東北大学 Combinatorics that professors love

Presentation on theme: "博士たちの愛する組合せ論 徳山 豪 東北大学 Combinatorics that professors love"— Presentation transcript:

1 博士たちの愛する組合せ論 徳山 豪 東北大学 Combinatorics that professors love
Mathematics that the professor loved 徳山　豪 東北大学 Combinatorics that professors love 博士たちの愛する組合せ論

2 内容 組合せ数学の美しさ 『当たり前のこと』の威力 Paul Erdosが天才を探すときの質問 Pigeon hole (鳩の巣）原理
　Double Counting：　二通りに数えてみよう　 Paul　Erdosが天才を探すときの質問 　２００以下の自然数が１０１個あるとしよう。以下の2つの命題は正しいか？ 互いに素(公約数が１）な2つの数が必ずある 約数の関係(小さい方が大きい方を割り切れる）にある2つの数が必ずある。

3 鳩の巣原理 Ｎ羽の鳩がM個の巣箱に入っていると N/M 以上の鳩が入っている巣がある
（数学的に言うと）有限集合Sから有限集合Tへの写像Fがあり、|S|=N,　|T|=Mなら 　　F-1 (t) = { s ∈ S： F(s)=t }　とすると、 　 |F-1(t)|≧N/Mであるｔ∈Tが存在する

4 鳩の巣原理を使おう：１ ２００以下の自然数が１０１個あるとしよう。 鳩＝101個の自然数。 N=１0１ 巣をどうするかが腕の見せ所。
互いに疎な2つの数が必ずあることを示せ 鳩＝101個の自然数。　N=１0１ 巣をどうするかが腕の見せ所。 　（1，2), (3，4),…, ( i, i+1),…,(199,200) 100 個の巣。　　M=100 　N=M+1なので、２羽以上が入っている巣がある 　（k, k+1) この二つは互いに素。

5 鳩の巣原理を使おう：２ ２００以下の自然数が１０１個あるとしよう。 鳩＝101個の自然数。 N=１0１
　２００以下の自然数が１０１個あるとしよう。 約数の関係(小さい方が大きい方を割り切れる）にある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のべき乗倍）にある。　

6 鳩の巣原理：上級編 長さｎの(異なった）実数の列 a1,a2,…,anがある。
　このとき、長さｎ１/2　以上の部分列で、単調増加あるいは単調減少であるものが必ず存在することを示せ。　（Erdos-Szekeresの定理） 　徳山は大学院時代に証明に四苦八苦した。 　数多くの高度な応用がある（講義では紹介しない） 　面白い「鳩の巣」を作る。

7 Erdos-Szekeresの定理の証明
長さｎの実数列　a1,a2,…,anがある。 ｑ　= n ½ 未満の最大整数 L(j)：aj から始まる増加列の最大長 S(ｋ）＝｛aj: L(j)=k } S(1), S(2),..,S(q): 鳩の巣 巣に入らない鳩が居れば、長さq+１以上の増加列がある。 全部の鳩が巣に入れば、q+１羽以上が入る巣がある。 その巣に入る要素からなる部分列は単調減少列になる なぜでしょう？ よって証明終了　(判ったかな？）

8 二重数え上げ法 同じものを２通りに数えることで定理を証明する
例題１：　自然数ｍの約数の数をｆ（ｍ）とする。（１/ｎ）∑１≦ｍ≦ｎｆ（ｍ）を(誤差２の範囲で）求めよ 例題２：　グラフの次数とは、その頂点から出る辺の数である。　５頂点のグラフで、全ての次数が３であるグラフは存在するか？存在するのなら構成せよ。

9 二重数え上げ法 例題１： 自然数ｍの約数の数をｆ（ｍ）とする。（１/ｎ）∑１≦ｍ≦ｎｆ（ｍ）を(誤差２の範囲で）求めよ
例題１：　自然数ｍの約数の数をｆ（ｍ）とする。（１/ｎ）∑１≦ｍ≦ｎｆ（ｍ）を(誤差２の範囲で）求めよ 　（k,ｍ）　ｋはｍの約数、m≦ｎである対の数を２通りに数える。 　ｍでまとめると、 ∑１≦ｍ≦ｎｆ（ｍ） 　ｋでまとめると、どうなりますか？

10 二重数え上げ法 例題２：　グラフの次数とは、その頂点から出る辺の数である。　５頂点のグラフで、全ての次数が３であるグラフは存在するか？存在するのなら構成せよ。 「頂点と辺の対(v, e): 頂点vは辺eの端点」を２通りに数える 　ｖでまとめると、次数の和 　e でまとめると、何ですか？

11 二重数え上げ法(上級編） 　問題３：　ｎ個の単位円(半径１の円）がある。円たちの交点のうちで、次数（交わっている円の数）の多い方からｎ点の集合Sを選ぶ。　このとき、次数の和がｎ3/2以上にならないことを示せ。 使うべき事実：　2点を通る単位円は高々2個しかない 数えるべきもの（p, C1,C2)　pはSの要素、C1,C2はpを通る円

12 二重数え上げ法(上級編）の利用 　Erdosの距離重複度問題：　平面上にｎ点がある。これらの点の点対で同一の距離ｄにあるものは最大いくつあるか？？？ 　先ほどの問題から：　ｎ3/2　以下 　現在知られている最善：　ｎ4/3　以下 　もっと少ないはず。（ｎの定数倍よりは大きい）

13 二重数え上げ法(上級編）の利用 平面上にｎ点が正方格子状に配置してある。 1点から距離1の点はいくつ？ 1点から距離５の点はいくつ？
　平面上にｎ点が正方格子状に配置してある。 　1点から距離1の点はいくつ？ 　1点から距離５の点はいくつ？ 　1点から距離６５の点はいくつ？ 　ラグランジュの整数二次形式の理論 　一般に、大きい距離はたくさん出てくる 　問題：　正方格子より本質的に距離重複度の大きい配置はあるだろうか？ 　誰かチャレンジしませんか？　(博士号＋海外留学は保証します）。

14 組合せ論の美の典型 Brouwerの不動点定理(1912) Ｄ次元の球BからBへの連続写像ｆは必ず不動点（ｆ（ｘ）＝ｘである点ｘ）を持つ。
　「中間値の定理」　の一般化 　幾何、解析、プログラム基礎理論、情報理論などの基本定理 Ｄ次元の球BからBへの連続写像ｆは必ず不動点（ｆ（ｘ）＝ｘである点ｘ）を持つ。 オリジナルの証明：高等な解析と幾何を利用 天才Sperner(23歳）の初等的証明（１９２８） これは来週（二次元の場合のみ。乞うご期待）