じぶん更新日記・隠居の日々
1997年5月6日開設
Copyright(C)長谷川芳典



08月のインデックスへ戻る
最新版へ戻る


クリックで全体表示。
 ウォーキングに出かけたところ、法界院駅近くの踏切で偶然「キハ120形気動車」を目撃した。津山線の各車両の中では最も新しい列車であり、こちらに前面展望の動画がある。
 津山線を運行している車両はオレンジ色のタイプや、「みまさかノスタルジー」などがあり、日によって使用される車両が入れ替わっているが、津山発4時48分発の岡山方面への始発列車は、私が目撃した限りではかならずキハ120形が使われているようだ。何か理由があるはずだが未確認。

2022年8月17日(水)



【連載】最近視聴したYouTube動画「巨大数」(4)

 8月14日に続いて、

宇宙がいくつあっても足りない数!?「巨大数」を紹介【ゆっくり解説。2021年11月7日】

についてのメモと感想。

 今回は、前回取り上げたグラハム数についての補足。リンク先によれば、グラハム数はラムゼー理論に関する未解決問題の解の推定値の上限として得られた自然数であると記されているが、ここで言及されているラムゼー理論は、私にとっては難解だが、なかなか奥が深く興味深い世界に繋がっているよううに直観される。
  • ラムゼー理論(ラムゼーりろん、英: Ramsey theory)は、一定の秩序がどのような条件の下で必ず現れるかを研究する数学の一分野である。名前はイギリスの数学者・哲学者であるフランク・ラムゼイ (Frank P. Ramsey) に因んでいる。
  • ラムゼー理論の問題は、典型的には「ある構造がある性質を持つことを保証するには、その構造にはどのくらい元が必要か」という形のものである。
 ラムゼーの定理の例としてあげられているのは、

「6人いれば、互いに知り合いである3人組か、互いに知り合いでない3人組が存在する」

また、ラムゼー理論に関連して、いくつか興味深い定理がある。
  • ファン・デル・ヴェルデンの定理: 任意に c と n が与えられたとき、ある自然数 V が存在して、以下の条件を満たす: V 個の連続する自然数が c 色に塗り分けられているならば、どの元も同じ色で塗られている、長さ n の等差数列が含まれている。
  • Hales-Jewettの定理(英語版): 任意に c と n が与えられたとき、ある自然数 H が存在して、以下の条件を満たす: n×n×...×n の H 次元超立方体のセルを c 色で塗り分けると、ある長さnの行や列などが存在して、それに属する全てのセルが同じ色で塗り分けられている。すなわち、一列に n マスある多人数まるばつは、どれほど n が大きくても、どれほど多人数で遊んだとしても、十分次元の大きい盤面で遊ぶ際、引き分けに終わることがない。Hales-Jewettの定理はファン・デル・ヴェルデンの定理を含む。
 ウィキペディア【一部省略、改変】によれば、
ラムゼー理論の結果は二つの主要な特徴がある。
  • 第一に、構成的ではないことである。結果は、ある構造が存在することは示しているが、(力まかせ探索を除いて)この構造を見つけるための手段は与えていない。例えば、鳩の巣原理はこの形式に属する。
  • 第二に、ラムゼー理論の結果は十分大きな対象がある与えられた構造を必ず持つことを示す一方、この結果の証明にはその大きさが莫大であることがしばしば要求される。その大きさの上界は、指数関数的に、あるいは、アッカーマン関数と同じくらいの速さで増大することさえ珍しくはない。多くの場合このような上界は証明に用いられる人為的なものであり、その上界を十分に改善できるかどうかは知られていない。またある場合にはどのような上界も莫大でなければならず、ときにはどのような原始再帰関数よりさえも大きい。グラハム数は、正式な数学の証明において使われた最大の数であり、ラムゼー理論に関する問題の上界である。
この2番目の特徴がグラハム数に関連している。

 余談だが、上記の第一の特徴で言及されていた、鳩の巣原理も興味深い。リンク先には次のような例が挙げられていた。
「ロンドンには、同じ本数の髪の毛を持った少なくとも2人の人間が存在する」を証明してみよう。ふつう、髪の毛の本数は15万本ほどであるから、100万本以上の髪の毛を持っている人間はいないと考えることができる。一方で、ロンドンの人口は100万を超える。もし、髪の毛の本数ごとに鳩の巣を割り当て、巣にロンドンの人々を割り当てるなら、(当然の下限である0本から上限として置いた99万9999本までの巣に100万を超える人々を割り当てるのだから)少なくとも同じ髪の毛の本数を持った2人の人間が必ず存在する。

 上記の引用文の中でも指摘されているが、「鳩の巣原理」は何かが存在することは証明できるが、それがどこにどういう構造で存在するのかは明らかにできないようだ。例えば、11人の若者が無人島に漂着し、共同生活を始めたとする。この場合、男が6人、女が5人で、あくまで一夫一妻制(同性婚は無かったとする)を守るとすると、男性1名は結婚できないことになる。結婚できない男が必ず存在することは証明できるが、誰が結婚できないのかは分からないし、どういうプロセスで夫婦が形成されるのかも不明。

 次回に続く。