数学家教你铺能得诺贝尔奖的地砖

标签: 数学 家教 得诺 | 发表时间:2011-10-26 18:06 | 作者:(author unknown) 远
出处:http://www.guokr.com/
作者:matrix67

2011年诺贝尔化学奖授予以色列人丹尼尔·舍特曼(Daniel Shechtman),他观察到自然界中基本粒子存在非周期性排列的现象。这个 准晶模型 的发现,拓展了整个晶体学界的知识域和审美视野。

但其实,在此之前数学界就已经研究过这个问题,并且持续探索了半个世纪之久,到今天虽然依旧留有悬念,不过结果已然精彩纷呈。问题的起源可以非常简单,不妨让我们从地板砖说起。

http://img1.guokr.com/gkimage/s3/ja/g4/s3jag4.png

你注意过脚下的地板砖是什么形状吗?它们通常都是正三角形、正方形和正六边形。事实上,如果想要用单一的一种正多边形铺满整个平面,那么正三角形、正方形和正六边形是仅有的三种选择。这是因为,这三种图形的内角分别是 60° 、90° 和 120° ,它们都是 360 的约数。如果换作内角为 108° 的正五边形,那么它无论如何也没法既无重复又无遗漏地铺满整个平面——三个正五边形相接,不能摆满 360° ;四个正五边形相接,又超过 360° 了。

http://img1.guokr.com/gkimage/ly/ky/8w/lyky8w.png

正多边形平铺平面的能力

不过,如果允许多种形状不同的砖块组合,我们就能得到几乎是无穷无尽的地板砖设计方案。我们甚至能构造出这么一种极端的情况:单看每一种砖块都不是平铺平面的料,但把它们合在一起,就能得到一个漂亮的平铺方案。在下图中,基本的砖块只有四种,正五边形、正十边形、正五角星和一个包含 16 条边的 8 字形砖块。这四种砖块都没法单独平铺平面,但彼此合作就能得出一个不错的平铺图:

http://img1.guokr.com/gkimage/om/wo/0i/omwo0i.png

一个非周期性的平铺方案

请注意,这个平铺方案和我们之前的那些方案有一个很大的不同:它不是周期性的!换句话说,它不是某一种基本模式的重复排列,不管怎样对整个平面进行平移,图案都不能和原来重合。但这其实有些故弄玄虚的味道。因为事实上,我们可以用这四种砖块实现一个简单的周期性平铺:

http://img1.guokr.com/gkimage/c0/u5/c5/c0u5c5.png

一个周期性的平铺方案

于是我们想问:存在一组砖块,它可以平铺整个平面,但只能用非周期性的方法才能平铺整个平面吗?其实,为了给这个问题找出一个完美的回答,数学家们已经奋斗了整整半个世纪。

故事的起点:王氏砖块

1961 年,美籍华裔数学家王浩考虑了这么一个有趣的问题:大小相同的正方形砖块可以无限地平铺整个平面,但如果增加一些额外的限制呢?王浩设想了一种边上涂有颜色的正方形砖块,并要求摆放砖块时只有相同颜色的边才能挨在一起(砖块不能旋转、翻折)。我们通常把这样的砖块叫做王氏砖块(Wang tile)。任意给定一组王氏砖块,能否用它们摆满整个平面呢?如果砖块数量一多,这就不容易看出来了,就连计算机也不见得有简单的判断方法。寻找一种简洁有效的判断方法,成为了王氏砖块研究的核心问题。

http://img1.guokr.com/gkimage/rf/jj/zw/rfjjzw.png

一个可以平铺平面的王氏砖块组,以及一个不能平铺平面的王氏砖块组

在研究过程中,王浩找到了一种算法,它能够列举出所有可以周期性平铺平面的砖块组,同时也能列举出所有不可以平铺平面的砖块组。因此,如果任意一个砖块组都只可能属于上述两种情况之一,那么我们就能保证在有限长的时间里等到答案。这样看来,王浩似乎成功找到了一种判断给定的王氏砖块是否能平铺平面的算法。

但五年之后,事情突然发生了 180 度大逆转。数学家罗伯特•贝格(Robert Berger)在 1966 年证明了,王氏砖块问题事实上是一个不可判定问题。这听上去似乎很不合逻辑,但经过严格推导后,事实就摆在眼前:判断一组给定的王氏砖块能否平铺整个平面,这不但没有简洁有效的算法,而且事实上根本就没有任何算法。再天才、再有耐心的程序员,也不可能编写出一个自动判断一组王氏砖块有无平铺方案的程序,因为这在理论上就是不可能实现的。

把两人得出的结论一对比,我们立即可知,一定存在一组王氏砖块,它只能非周期性地平铺平面!人们通常把这样的砖块组简称为“非周期性砖块组”。在 1966 年的论文中,罗伯特•贝格给出了第一个非周期性砖块组,它由 20426 个砖块构成。没多久,贝格本人又给出了一个含有 104 个砖块的非周期性砖块组。经过其他数学家的努力,这个数目不断地减小,最终在 1996 年减小到了 13 块。

http://img1.guokr.com/gkimage/jx/mb/lp/jxmblp.png

只含有 13 个砖块的非周期性砖块组

http://img1.guokr.com/gkimage/i5/n5/bb/i5n5bb.png

上述非周期性砖块组的平铺方案

罗宾逊砖块组

既然王氏砖块中存在非周期性砖块组,那么对于其他类型的砖块,存在非周期性砖块组也不足为奇了。1971 年,美国数学家拉斐尔•罗宾逊(Raphael M. Robinson)发现了一个只含 6 个砖块的非周期性砖块组。不过,这里“砖块组”的意义和王氏砖块却有很大的区别:这里的砖块都可以旋转或者翻转,另外除了边上有匹配规则以外,角上也有相应的规则。下图就是罗宾逊砖块组,其中边上和角上的匹配规则都巧妙地用拼图的形式表示了出来。

http://img1.guokr.com/gkimage/up/4g/n4/up4gn4.png

罗宾逊砖块组

为了便于研究,我们通常会在罗宾逊砖块中加上两种颜色的线条。罗宾逊砖块组可以平铺平面,但只能非周期性地平铺平面。下图就是一种平铺方案,注意两种颜色的线条将会产生尺度越来越大的正方形,这说明这种平铺方案是非周期的。

http://img1.guokr.com/gkimage/vg/4t/yt/vg4tyt.png

罗宾逊砖块组的平铺方案,除右下角外,其他部分都省略了具体的砖块形状,只保留了由线条构成的“骨架”

彭罗斯砖块组

砖块的数目还能继续减少吗?答案是肯定的。1974 年,英国数学家罗杰•彭罗斯(Roger Penrose)跳出了正方形砖块的圈子,巧妙地构造出了一系列非周期性砖块组。其中最简单的一个砖块组只含两个砖块,它们分别是 36 度菱形和 72 度菱形:

http://img1.guokr.com/gkimage/la/ni/03/lani03.png

彭罗斯砖块组,其中边界上的匹配规则已经用拼图的形式给出

在边界规则的限定下,我们只能用它们非周期性地平铺整个平面:

http://img1.guokr.com/gkimage/oj/xs/3z/ojxs3z.png

彭罗斯砖块组的平铺方案

现在,我们的问题就只剩下一个了:是否存在由单个砖块构成的非周期性砖块组呢?

泰勒砖块组

2010 年 9 月,非周期性砖块组的问题终于有了一个大突破。琼•泰勒(Joan M. Taylor)发现了第一个只含单个砖块的非周期性砖块组。

http://img1.guokr.com/gkimage/px/6h/4b/px6h4b.png

泰勒砖块组

这是一个六边形的砖块。在摆放的时候,我们可以任意旋转或者翻转砖块,但有两点限制。第一,黑色的线条必须连在一起(这也就相当于是边界匹配规则);第二,一条边两端的紫色小旗必须朝向相同的方向。

http://img1.guokr.com/gkimage/cv/v8/kf/cvv8kf.png

其中规则二中的两个小旗来自于两个不相邻的砖块。可以证明,用这种六边形砖块是能够平铺整个平面的,但方案是唯一的。拼接的限制很巧妙地迫使黑色线条构成规模越来越大的三角形,从而使得整个图形不具有周期性。

http://img1.guokr.com/gkimage/ej/nb/uv/ejnbuv.png

泰勒砖块组的平铺方案

不过,泰勒砖块组有一个明显不尽人意的地方:它的第二条规则是对不相邻砖块的摆放限制,这显得有些“过”了。因此,非周期性砖块组的问题仍然不能算作是彻底解决。是否存在一个更常规的单个非周期性砖块呢?这个问题至今仍未解决。


想让你的地板更酷更炫更骚更帅更靓更有型更与众不同更 geek 更 math 吗?用这些图块铺地板吧。


参考资料:

维基百科: Aperiodic tiling

了解更多:

【2011诺贝尔化学奖解读】准晶:似晶非晶

相关 [数学 家教 得诺] 推荐:

数学家教你铺能得诺贝尔奖的地砖

- 远 - 果壳网 guokr.com - 果壳网
作者:matrix67 2011年诺贝尔化学奖授予以色列人丹尼尔·舍特曼(Daniel Shechtman),他观察到自然界中基本粒子存在非周期性排列的现象. 这个 准晶模型 的发现,拓展了整个晶体学界的知识域和审美视野. 但其实,在此之前数学界就已经研究过这个问题,并且持续探索了半个世纪之久,到今天虽然依旧留有悬念,不过结果已然精彩纷呈.

数学,传奇?

- cindy - 粉红小猪
   在国内就老是听到传奇,说是中国的数学有多么多么的好,国外的数学有多么多么的撇,还把这里的学生的数学,说得跟弱智一样,过来一看,都哪跟哪啊,这边的人还啭中国高中生呢:“微积分都不懂.   这边的数学书,搞得跟百科全书一样厚,都基本上没办法带回家,只能放学校个人的柜子里,是国内数学书的3-5倍厚重,从测量的历史开始写,图片跟历史地理一样漂亮,不大像数学书……我带回家给我爸看了一眼,他说:难怪学生不能自己拥有书,只能用完了下届学生继续用,这得多高的成本啊.

数学是数学家的墓志铭

- 李龑 - 果壳网 guokr.com - 果壳网
作者:严酷的魔王 你想在自己的墓碑上刻下什么文字. 也许对于我们来说,考虑这个问题为时尚早,但是许许多多的前辈数学家已经用自己的实际行动告诉了我们:墓碑上书写着自己的荣耀. “他生命的六分之一是幸福的童年;再活了他的生命的十二分之一,两颊长起了细细的胡子;他结了婚,又度过了一生的七分之一;再过五年,他有了儿子,感到很幸福;可是儿子只活了他全部年龄的一半;儿子死后,他在极度悲痛中度过了四年,也与世长辞了.

篮球的数学

- 猫 - Solidot
是当机立断投篮还是等待更佳良机,职员篮球运动员每场比赛都要面临多次类似的困境. 现在,明尼苏达大学理论物理学研究生Brian Skinner在arXiv.org上发表了一篇论文,向球员提供了投篮最佳时机的数学建议. Skinner是一位狂热的篮球迷,他发现篮球运动类似于交通网络中的汽车驾驶,每辆车相当于一个被球员持有的篮球,通过在网络中运动实现得分目的.

林语堂未得诺贝尔奖是因为用英文创作

- Morely - 东西
    50年前林语堂曾被赛珍珠提名参评诺贝尔文学奖,没有成功的原因居然是林的作品是用英文写的.      用国人的观点看,中国人用英文写的中国小说更能直接地“打入”西方社会和文学圈,“外宣效果”更强啊. 可诺贝尔奖评奖标准里居然还有这么个不成文的规定,妨碍了林大作家得奖.    林语堂是成也赛珍珠败也赛珍珠:是赛珍珠把林推介给西方,好象林的作品都是赛的或着赛与别人合伙开的出版社推出的,林在英语世界大获成功,出版社也赚了钱;林却用自己辛苦的稿费投入拼音打汉字的机器,花费颇高,据说基本上成功,但那种打字机造价太高,没人买得起,结果就放弃了.

数学公式生成器

- ArBing - 阮一峰的网络日志
上一篇文章《数学常数e的含义》,有很多数学公式. 但是,在网页上显示数学公式,是一件非常麻烦的事情. 怎样才能把这个公式放到网页上呢. 传统的方式是,先在相关软件中把公式做出来,然后截图,再把图片贴到网页上,这样既麻烦又耗时. 我就在想,有没有便捷的方法,可以生成数学公式. 我知道,Google Chart接受TeX语言,实时返回数学公式的图片.

改变思想的数学

- 我要发芽 - Solidot
观点将随事实的改变而改变,这是贝叶斯定理的真谛. 贝叶斯定理以18世纪的长老教会牧师Thomas Bayes的名字命名,目的是为了解决一些本质问题:当更多信息涌入时我们如何改变信仰. 是顽固的直到旧有假说完全站不住脚. 还是在怀疑第一次出现后立即抛弃旧观念. 贝叶斯的推导已经变成了无价的科学工具,它帮助我们一步步认清现实.

谷歌背后的数学

- 欲望道人 - 卢昌海个人主页
站长撰写的介绍谷歌公司的网页排序算法的文章.

数学家 vs. 上帝

- 虫虫 - 科学松鼠会
原作地址:http://abstrusegoose.com/395.

Hadoop背后的数学

- - 灰色的灵魂
自从 Nathan Marz同学写了那篇著名的 How to beat the CAP theorem的Blog,以及 Storm发布之后,俨然成为了技术界新偶像. 顺着他本人的blog,翻了一下他过去几年的写的技术文章,发现老美的牛人们都爱总结,能够把技术实践提升到理论高度,然后抽象出新的设计和产品,比起我等只能每天苦逼苦逼应对实际需求的人来说,还是强出很多.