永兴感知技术论坛

标题: 这道像是奥数题的“填色问题”,至今无人能解决 [打印本页]

作者: admin    时间: 2018-8-16 18:03
标题: 这道像是奥数题的“填色问题”,至今无人能解决
如果给平面上所有的点都赋予一个颜色,那么至少需要多少种颜色才能保证存在一种着色方法,使得任意两个距离为1的点不同色?
想象一下,如果你要用矩形完全覆盖一个8*8的棋盘,每一个矩形覆盖棋盘上的两个正方形。容易想到的是,你可以这么做:你可以将四个矩形横着排或者竖着排。你可以将它们排列成楼梯状、同心正方形或者交错的牙齿形状。一共有大约一千三百万种排列方式,每种方式都需要32个矩形,因为整个棋盘包含64个正方形而每个矩形包含两个正方形。
但是如果我们拿掉棋盘对角上的两个正方形会发生什么?如果我们想用2*1的矩形覆盖新的棋盘有多少种方式?答案是零,你不可能用2*1的矩形完全覆盖这样的棋盘。是什么让可能性从一千三百万如此迅速的变成零?如果我们知道如何去考察这个问题,原因是很容易发现的。
把棋盘上的矩形交替的涂上亮暗两种色块。将会出现两种重要的结果:1、一定有数量相同的亮暗色块,2、关于中心对称的两个矩形一定具有相同的颜色。这意味着我们拿走位置相反的两个正方形那么亮暗色块的数量将不再相等。但是每个2*1的矩形一定覆盖一个亮色块和一个暗色块,也就是说想要2*1的矩形完全覆盖棋盘,棋盘一定要包含相同数量的亮暗色块才行。所以,我们的改变过的棋盘不可能被矩形完全覆盖。
在众多的棋盘数学题中,这是我最喜欢的一个,因为它能用令人惊奇的方式解决。谁能想到将正方形涂色是解决这个难题的关键?但是数学家很久之前已经利用将正方形涂色的方式解决问题。最近,平面涂色的进展使困扰数学家超过60年的问题焕发新的生机。
想象一个标准的几何平面,沿着两个方向无限延伸。你的任务是将面上的的无数个点涂色。你可能想把整个平面涂成红色,或者一半红色一半蓝色,或者将色彩洒在平面上,像JacksonPollack的绘画一样。但是在我们涂色的过程中要遵循一个原则:如果两个点相距一个单位长度,他们就不能涂成相同的颜色。你可以完成平面的涂色并且不打破这个规则吗?
“当然!”你也许会说,“我可以利用无数种颜色来涂色。”这当然是一种解决方案,但是你能用有限多种颜色做到这一点吗?进一步的,你需要多少种颜色?寻找至少需要多少种颜色的问题被称为Hadwiger-Nelson问题,它也经常被描述为寻找平面的“色彩数”。 Hadwiger-Nelson问题在70年前最早被提出,但是至今我们也不知道最少需要多少颜色。
首先,让我们看一下使用有限多种颜色可以做到什么。
上面的正方形边长2/3,想象两个在正方形中的点,他们的距离可以是多少?正方形中 任意两点之间的最长距离是正方形的对角线长,我们可以用勾股定理计算得到:
又因为:
我们知道正方形中任意两点之间的距离小于1.这意味着将整个正方形涂成红色并不违反我们的涂色原则。
接下来我们用九个这样的小正方形组成一个大正方形,并且每个小正方形拥有它自己的颜色。
因为每个正方形颜色不同,我们依然没有违反涂色规则。当然,因为大正方形的边长是2 ,所以它只覆盖4平方单位的面积、但我们可以通过复制粘贴来做出其他的部分。
我们可以像这样覆盖整个平面,但是这满足相距为1的点涂不同颜色的规则吗?只考虑红色正方形。我们证明了红色正方形内任意两点之间的距离都不是1。现在,因为每个小正方形的边长都是2/3,两个红色正方形之间的最小距离是2/3+2/3=4/3 。这意味着不同红色正方形中的两点之间的距离都大于1.结果就是,平面上没有哪两个红色的点之间的距离是1。这证明了不但色彩数是有限的,而且最大是9。
稍微复杂的情况是用正六边形来分割整个平面,这种情况下,7种颜色就足够了。你可以用六个六边形包围一个六边形并把他们涂成不同的颜色。
利用上面的构造,你可以把图形沿着任意方向扩展。
通过合适选择六边形的大小,并且按照正确的方式扩展图形,我们可以保证任意两个相同颜色的点之间的距离都不是1。
通过上面的例子我们可以确定色彩数的上限是7,我们是都可以找到更小的色彩数?
容易看出,色彩数一定大于1,在平面上放置一个点并把它涂成蓝色。
因为平面是无限延伸的,所以一定可以找到一个距离P点为1的点。
Q点需要另一种颜色,我们把它涂成红色:
因此,平面的色彩数至少是2,那么,两种颜色是足够的吗?因为平面是无限延伸的,因此距离P为1的点有无数个。
因为P是蓝色且圆上的点距离P都是1,所以圆上的点都不能是蓝色。如果只使用两种颜色意味着圆上的点都是红色的。
现在开始考虑Q点:距离Q为1的点不能是红色。就像P点那样,Q点周围有一个圆,它上面的点距离Q都是1。
Q周围新的圆和P周围的圆有两个交点,我们把它们称为R和S。R和S不能是蓝色,因为它们距离P是1。同时它们不能是红色,因为它们距离Q点也是1。
我们注意到PRQ和PSQ都是正三角形且PRQS是菱形,通过平面几何的知识可以发现RS之间的距离大于1,所以让它们的颜色都是绿色是没有问题的。
这表明色彩数至少是3,有一个办法可以证明这个数至少是4。考虑我们刚才得到的菱形:
想象我们有两个形同的矩形并让它们的一个顶点重合,再用一枚针固定在一起,如图所示。我们转动其中一个矩形并让他们渐渐分开。
菱形在转动过程中保持形状不变。随着分开的距离越来越大,底部的两个顶点之间的距离最终可以是1。
现在有一个问题。底部的两个顶点不能都是绿色,因为它们的距离是1。它们也不能是蓝色或者红色。我们需要第四种颜色!这个图形被称为Moser纺锤,它是以Leo和William Moser的名字命名,并且它证明了色彩数至少是4。
作为总结,我们知道色彩数至少是4,最大是7。在接近60年的时间内,这是我们关于这个问题所知道一切,直到Aubrey de Grey 在2018年4月发表了他的工作。
就像Moser 纺锤利用7个点证明需要至少四种颜色那样,Grey利用1581个点证明了四种颜色也是不够用的,就像上图显示的那样。但是不同的是,这不能直接看出来,事实上,证明过程借助了计算机的帮助。借助Grey的发现,我们发现色彩数至少是5。结合之前的论证,色彩数一定是5、6、7中的一个,但是我们并不知道是哪一个。
毫无疑问,Grey让我们距离这个答案的最终结果又更近一步。我们能发现最终的答案吗?
原文链接:
https://www.quantamagazine.org/the-numbers-and-geometry-behind-a-math-coloring-puzzle-20180618/
本文转载自《中科院物理所》微信公众号






欢迎光临 永兴感知技术论坛 (http://bbs.yxsensing.net/) Powered by Discuz! X3.3