ハッピーエンド問題
どの 3 点も一直線に並ばない 5 点を置くと、必ず凸四角形ができる。凸五角形なら 9 点、凸六角形なら 17 点が必要。
解説
5 つの点の不思議
平面上に、どの 3 点も一直線に並ばない 5 つの点を置く。
すると必ず、そのうち 4 点で凸四角形（へこみのない四角形）が作れる。
これを証明したのはエスター・クラインだ。
もっと大きな多角形
凸 n 角形が必ずできる最小の点の数を N(n) と書く。
N(3) ＝ 3、N(4) ＝ 5、N(5) ＝ 9、N(6) ＝ 17 がわかっている。
N(5) ＝ 9 を最初に証明したのはマカイ・エンドレで、最初に発表された証明は 1970 年のカルブフライシュらによる。
N(6) ＝ 17 は 2006 年、セケレシュとピーターズがコンピューターで 17 点のあらゆる並べ方を調べて証明した。
このツールの「凸 5 角形がない 8 点」は、8 点では凸五角形を避けられる例で、N(5) が 8 より大きいことを示す。
エルデシュ–セケレシュ予想
エルデシュとセケレシュは、N(n) ＝ 2^(n−2) ＋ 1 と予想した。
1961 年に 2 人は、2^(n−2) 個の点で凸 n 角形ができない並べ方を作り、N(n) ≧ 2^(n−2) ＋ 1 を示した。
上からの評価は 2016 年にスクがおよそ 2^n まで下げたが、予想そのものはまだ証明されておらず、7 角形以上の正確な点の数はわかっていない。
名前の由来
この問題がきっかけで、ジョージ・セケレシュとエスター・クラインが結婚した。
そこでポール・エルデシュが「ハッピーエンド問題」と名付けた。