longyangjing的个人博客分享 http://blog.sciencenet.cn/u/longyangjing

博文

圆满结局问题 精选

已有 3372 次阅读 2018-1-11 21:24 |系统分类:科普集锦


https://plus.maths.org/content/happy-ending-problem


The happy ending problem

圆满结局问题

作者:Marianne Freiberger

翻译:龙旸靖

《数学文化》 约稿


译者注:


1. 在圆满结局问题提出70年后的2005年8月28日,Szekeres和Klein两夫妻在一小时内相继离世,某种程度上不求同日生,但求同日死,也算是圆满结局。

2. 在Szekeres和Klein去世12年后, 在2017年的如下文章中,Andrew Suk 给出了圆满结局问题一个几乎紧的界,几乎完全解决了圆满结局问题。

http://www.ams.org/journals/jams/2017-30-04/S0894-0347-2016-00869-X/home.html


以下为正文:



圆满结局问题是一个很容易阐释的数学问题,但它仍然没有被完全解答。世界上最好的一些数学家一直试图解决它,但是没有成功。它涉及到绘制在纸上的点和点所连接而成的图形。


我们先从三个不共线的点开始,将它们连接起来,形成一个三角形,使得三个点为三角形的三个角:


Triangles


平面上的三点形成一个三角形(只要它们不共线)。


当有四个点(任意三点不共线)会发生什么?连接它们,可以创建一个四边形,其中四个点为四边形的角:



Quadrilaterals


一些四边形。



但是,根据点的分布情况,某些四边形可能看起来有点奇怪(如上图中间的矩形),它们包含凹痕和尖峰,与那些整齐而规则的矩形毫不相似,矩形往往是我们所能想到的第一种四边形。因此,让我们来作进一步的限制。我们来看看是否可以四个点绘制一个凸四边形,即一个所有内角都在180度以下的四边形。这确保该形状不包含向内推的角和凹痕。下图中的四边形不是凸的,但是上图中的左右两边都是。



Non-convex quadrilateral


非凸四边形。


一些简单的例子表明,给定四点,并不总能画出一个凸四边形:

Non-convex quadrilaterals

给定四点,并不总是可以将它们连接起来形成一个凸四边形。



但是,当再增加一点时,情况会改变。当在一张纸上绘制五个点(任意三点不共线)时,总是可以连接四个点,以形成一个凸四边形。额外的点给你足够的灵活性来做到这一点。这里有一些例子(你可能可以用相同的五个点绘制几个不同的凸四边形):


Quadrilaterals

给定五个点(任意三点不共线),总是可以找到一个凸四边形,其中四点为其角。


这个结果被数学家保罗·埃尔多斯(PaulErdős)命名为圆满结局定理,因为与他一起研究这一问题的两位朋友GeorgeSzekeresEsther Klein婚了。您可以在下面看到此结果的证明梗概。


添加边


下一个自然的问题是需要多少点才能确保您可以连接五个点以形成凸五边形(五面图)。答案是9(任意三点不共线)。这里有两个例子:


Pentagons


给定九点(没有三个点在同一条线上),你总是可以找到一个凸五边形,其中五个点为其角。


要确保画一个凸六边形(六面),你需要17点。这里有一个例子:


Hexagon

给定17点(没有任意三个点在同一条线上),你总是可以找到一个凸六边形,其中六个点为其角。


需要多少个点才能确保可以绘制一个凸七边形?答案还未知。对于  8 9 10 或任意 n 条边也同样如此。 ErdősSzekeres认为,给定一个自然数$n \ geq 3 $,需要确保可以连接n 个点以形成一个凸n多边形的点数是,

\[ 1+2^{n-2}. \]


对于$n=3$(三角形),结果的确如此

\[ 1+2^{n-2} = 1+2^{3-2} = 1+2 = 3. \]


它也适用于$n=4$, $n=5$ $n=6$, 因为



\[ 1+2^{4-2} = 1+2^{2} = 1+4 = 5, \]



\[ 1+2^{5-2} = 1+2^{3} = 1+8 = 9, \]




\[ 1+2^{6-2} = 1+2^{4} = 1+16 = 17. \]



但是,n> 6 的结果是否正确是未知的。ErdősSzekeres能够证明,需要保证一个凸 n多边形的点数总是至少为1+ 2 ^ {n-2} ,他们也证明了点数是有限的:换句话说,通过绘制足够的点,可以确定它们中将有一个凸n多边形。但是有多少个点就够了还没有被证明。


圆满结局问题说明了一个有趣的现象:如果系统足够大(例如足够多的点),那么有望在其内找到一些秩序(例如凸图形),即使系统整体无序。拉姆齐理论这一数学领域正是研究这一现象的。你可以在Plus杂志的Friendsand stranger一文中找到更多关于这一问题的讨论。


n = 4的圆满结局定理的证明梗概。


假设平面上有五个点。我们首先假设其中三个点可以连接起来形成三角形,使得三角形内包含两个剩下的点,记为A B 。连接这两个内部点的线将三角形分割成两部分。其中一部分只包含三角形的一个角,另一部分包含两个角:记这两个角为C D


Proof


三角形分割成两部分。



使用一些初等的几何知识,就能说明,四边形ABCD (见下图)没有内角大于180度。这意味着它是凸四边形。





Proof


至少有一点位于三角形之外。


如果三角形内部不包含其五个点中的两个呢?那么其中至少有一个点位于三角形的外面(见下图)。将三角线上的三个点和三角形外的一个点连接起来从而构造一个四边形,并证明该四边形的所有内角都小于180 度,即它是凸四边形。


Proof





http://blog.sciencenet.cn/blog-3353914-1094379.html

上一篇:Polymath
下一篇:[转载]隐形马尔可夫模型
收藏 分享 举报

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备14006957 )

GMT+8, 2018-1-22 12:15

Powered by ScienceNet.cn

Copyright © 2007-2017 中国科学报社

返回顶部