幸福结局问题

这是一个小故事，一个结局很幸福的小故事。

1933年，匈牙利数学家乔治·塞凯赖什（George Szekeres）只有 22 岁。那时，他常常和朋友们在匈牙利的首都布达佩斯讨论数学。这群人里面还有同样生于匈牙利的数学怪才埃尔德什大神。不过当时，埃尔德什只有20岁。

在一次数学聚会上，一位叫埃丝特·克莱因（Esther Klein）的美女同学提出了这么一个结论：在平面上随便画 5个点（其中任意三点不共线），那么一定有 4个点，它们构成一个凸四边形。塞凯赖什和埃尔德什等人想了好一会儿，依然不知道该怎么证明这个结论。于是，美女同学得意地宣布了她的证明：如图1，这5个点的凸包（覆盖整个点集的最小凸多边形）只可能是五边形、四边形和三角形。前两种情况都已经不用再讨论了，而对于第三种情况，把三角形内的两个点连成一条直线，则三角形的3个顶点中一定有2个顶点在这条直线的同一侧，这4个点便构成了一个凸四边形。

图1

众人大呼精彩。之后，埃尔德什和塞凯赖什仍然对这个问题念念不忘，于是尝试对其进行推广。最终，他们于 1935年发表论文，成功地证明了一个更强的结论：对于任意一个正整数n≥3，总存在一个正整数m，使得只要平面上的点有m个（并且任意三点不共线），那么一定能从中找到一个凸n边形。埃尔德什把这个问题命名为“幸福结局问题”（Happy Ending problem），因为这个问题让塞凯赖什和美女同学克莱因走到了一起，两人在1936年喜结良缘。

对于一个给定的n，不妨把需要的最少点数记作 f（n）。求出 f（n）的准确值是一个不小的挑战。由于平面上任意不共线三点都能确定一个三角形，因此 f（3）＝3。克莱因的结论则可以简单地表示为 f（4）＝5。

当n＝5时，8个点是不够的。图2就是8个不含凸五边形的点。

图2

利用一些稍显复杂的方法可以证明，任意9个点都包含一个凸五边形，因此 f（5）等于9。

2006年，利用计算机，人们终于证明了 f（6）＝17。目前，对于更大的n，f（n）的值仍然都是未知的。人们猜测f（n）＝2^n-2﹢1，这个猜想是否正确，短时间内恐怕也无从得知了。

不管怎样，最后的结局真的很幸福。塞凯赖什和克莱因在结婚后的近 70年里，先后到过上海和阿德莱德，最终在悉尼定居，期间从未分开过。2005年8月28日，塞凯赖什和克莱因相继离开人世，相隔不到一个小时。