インテジャーズ

INTEGERS

数、特に整数に関する記事。

ハッピーエンド問題

次の定理のことをハッピーエンド問題と言います:

定理 (ハッピーエンド問題)
平面上の一般の位置にあるような5点からなる任意の集合に対して、凸四角形をなすような4点からなる部分集合が必ず存在する。

平面上の点の集合が一般の位置にあるとはどの3点をとっても同一直線上にないときに言います。

この定理を発見し証明したのはハンガリーの女性数学者Esther Kleinです(1931年)。Ramsey理論の最初期の結果ですが、証明もかなり美しいです。凸包という概念を導入しておきます:

定義
平面(一般に\mathbb{R}^{N})内の集合Sに対し、Sの凸包\mathrm{CONV}(S)Sを含む最小の凸集合として定義する。

平面内の有限個の点からなるような集合の凸包は凸多角形になります。

ハッピーエンド問題の証明

与えられた5点からなる集合の凸包によって場合分けを行う:

凸包が五角形の場合

f:id:integers:20160119232854p:plain
この場合は5点のうち任意の1点を選べば、残りの4点が凸四角形をなす。

凸包が四角形の場合

f:id:integers:20160119233222p:plain
言うまでもなく定理は成立する。

凸包が三角形の場合

f:id:integers:20160119233717p:plain
内部の2点を通る直線を考えると、一般の位置にあるという仮定からこの直線は凸包をなす三角形の二辺と交わる。このとき、その直線と交わらないような凸包をなす三角形の辺の両端にある2点および三角形の内部にある2点の計4点は凸四角形をなすことがわかる。 Q.E.D.

この美しい証明を私はPaul Hoffman著、平石律子訳『放浪の天才数学者エルデシュ』(草思社、2000年)で知りました。これを知っていたことが役に立った経験があるのですが、それは別の記事で紹介しようと思います。

ハッピーエンド問題の一般化については次の定理が証明されています:

定理 (Erdős-Szekeres, 1935)
任意の整数N\geq 3に対して、ある十分大きい整数Mが存在して次が成り立つ:
「一般の位置にあるようなM個以上の点からなる任意の集合は凸N角形をなすようなN点からなる部分集合をもつ。」-⊛

⊛が成り立つようなMとして取りうる最小の値をHE(N)としましょう。ハッピーエンド問題によって、HE(4)=5であることが分かります(この記事のタイトルに"5"を選んだ理由)。HE(3)=3は明らかで、HE(5)=9はMakaiが証明しました(未出版)。上で紹介した本が出版された時点ではHE(6)=17は未解決でしたが、SzekeresとPetersによって2006年に(コンピュータを用いて)証明されたそうです。一般にHE(N)=1+2^{N-2}であるかどうかは未だにわかっていません。

ちなみに、Erdős-Szekeresの定理にKleinはとても感動したようで、この問題がきっかけとなってSzekeresとKleinが結婚したことにちなんでErdősによってハッピーエンド問題という名前が付けられたようです。