[项目背景简介]最“经济”的直尺

fwjmath

最“经济”的直尺

by fwjmath

注：本文遵守CC版权声明，转载请注明作者与出处，谢谢！



直尺算是一样非常常用的工具了，要想线画得直，不请直尺出场恐怕是不行的。但它的主要用途还不在这里。画直线，IC卡也可以，但是如果要在纸上量度一段距离的话，还是要等直尺出马，因为IC卡没有刻度。这样说来，如果说刻度是直尺的灵魂，相信没有人会有异议。数学家们说得好，一把有刻度的直尺顶得上一把圆规，因为我们只需要一把有刻度的直尺就能完成任何尺规几何作图。

扯得有点远了，还是回到刻度上来。我们平时用的直尺大概有刻度的范围有 15厘米，每厘米有一个大刻度，每毫米有一个小刻度，用起来的确相当方便。但是在数学家（更确切地来说是组合学家）眼中看来，这种标记刻度的方法未免太浪费。如果一把直尺有8个刻度的话，刻度之间两两组合最多能量出28种距离，而如果沿用普通直尺的刻度方法的话，我们只能量出从1到7一共7种距离。为什么会这样呢？想想看，有7种组合可以量出距离为1的线段，这样的话就浪费了6种刻度组合了。这当然算不上是一个很经济的办法。

于是自然而然，这些多事的数学家们就开始考虑一个问题了：要怎么样标记刻度才能使每对刻度的组合量出的距离都不同，从而避免浪费呢？当然，在这里0的刻度是肯定要标的，毕竟是自然数的起点嘛。如果没有别的限制的话，这个问题是不难解决的。还是举刚才8个刻度的例子，如果我们分别把刻度标在0、1、3、7、15、 31、63、127的话，容易验证每对刻度组合量出的距离都不相同。一般地说，对于有n个刻度的直尺，如果我们把刻度分别刻在2的k次方减1（k可以从0 到n-1）的话，这把直尺就满足这些数学家提出的条件了。

但是这时候，造直尺的商人就开始有异议了。数学家们很奇怪，我们不是帮你们节省了刻度的费用么，这个建议不是挺好么，为什么不接受呢？

商人也不多说，直接拿出了两把尺子。

“你们自己看看，同样是8个刻度，我的直尺只需要7厘米的材料，你们的方案却需要一米有余。原材料不要钱啊？”

于是数学家们被迫在他们的问题中加上一个补充条件，现在他们要寻找的刻度方案既要是“经济”的，也就是说每对刻度组合量出来的距离都不同；又要是最小化的，也就是说在满足这个条件的所有刻度数相同的刻度方案之中尺子长度最小的。这样一来，这个问题的答案就远非显然了。

当然，上面的对话是我虚构的。即使没有商人的要求，数学家们也会以一种类似自虐的方式不停给自己提难题，或者是将已经解决的问题加大难度。事实上，第一个考虑这种尺子的是美国数学家Solomon W. Golomb，这是个颇为严肃的，没啥花边新闻的组合学家。而这种尺子很自然也以他的名字命名，叫做Golomb尺，毕竟是他第一个提出这个问题的。一个刻度方案只需要满足“经济”的条件就可以被称为Golomb尺，也可以叫优化尺。如果这个刻度方案同时满足最小化条件的话，它就被称为最优Golomb尺，也可以叫最简优化尺。

进行了这样的限制之后，问题明显变难了，但是到底有多难呢？答案可能会令你很惊讶：目前为止我们仅仅确定了含有25个或以下刻度的最简优化尺方案，而含有25个刻度的最简优化尺还是昨天才通过大规模的全球志愿者电脑联网计算确定下来的。

完成这个计算的是一个叫Distributed.net的分布式计算项目，经过了全球志愿者共三千零六天的计算才最终决定了含有25个刻度的最简优化尺方案，而它的运算能力相当于7500个英特尔的酷睿处理器。也就是说，要找到含有25个刻度的最简优化尺方案，需要7500个英特尔的酷睿处理器同时工作 3006天才能完成这个任务！可见这个任务是多么艰难。

现在有人猜测，确定含有n个刻度的最优简化尺是一个NP-难问题，也就是说我们不可能找到一个有效的算法来对这个问题进行计算！为什么问题会突然间难了这么多呢？罪魁祸首就是最小化的条件。如果没有最小化的条件的话，我们就已经有了答案了。加上最小化的条件之后，我们要证明一个优化尺是最简的话，就需要检查每一个长度比它小的刻度方案，并且证明它们都不是优化尺。但是，只要学过组合数学就会知道，当刻度个数一定的时候，长度一定的刻度方案的个数是以阶乘速度增长的！



这样的话，当刻度增加，长度也会增加，从而对于每一个长度要检查的刻度方案数量也会呈阶乘速度增长。由于我们要检查的长度不止一个，所以难度增加的速度就更加大了。这样的话就不难解释为什么直到现在人们只确认了刻度数目不高于25的最简优化尺方案了。

虽然要确认一个优化尺方案是否最简是很困难的，但要给出一个很接近最简方案的优化尺还是可以做到的。实际上，数学家们早就对一种与优化尺相似的数学对象相当熟悉了，这东西有一个很唬人的名字：循环差集。虽然名字听起来比较吓人，但是循环差集其实并不难理解，它其实就是优化尺的环形版。当然啦，直尺不能弯成一个圈，除非是广告商用塑料或者纸做的那种满大街派发的便宜货。既然这样，我们就要寻找另一个比较贴近实际生活的模型了。

大家对和尚用的念珠比较熟悉吧，对对，就是唐僧那种。当然我也不排除某些同学对念珠菌比较熟悉，但别搞错，我们现在说的是环形的那种念珠。通常和尚用的念珠都是单调的黄色组成的，这跟他们念的经也比较适合，但对于那些只想买念珠来炫耀一下的游客来说这就未免太无趣了。那就加点蓝色的珠子吧，为了不无聊，我们规定每对蓝色珠子的距离都不相同。这样的话，这些蓝色珠子排布的方案就可以组成一个循环差集了。循环，是因为念珠可以随便旋转，而“差”来源于对距离的要求，因为距离实际上就是位置差。



好了，在我们上面描述循环差集的模型中，你有没有发现些熟悉的东西？“每对蓝色珠子的距离都不相同”，这跟优化尺的定义不是一模一样么？这样说来，循环差集跟优化尺的差别仅仅在于循环差集是可以“循环”的，而优化尺不能。现在我们要找的是最简优化尺，自然而然，我们就会想到，怎么样才能把循环差集转化为优化尺呢？很简单，循环差集比优化尺要多一个“循环”的对称性，我们只要把这种对称性给破坏了不就得了！

于是，某邪恶人士拿出一把剪刀，对着方丈刚串好的黄蓝相间的念珠一剪子……念珠怨念地撒了个满地都是……

唉，所以说做人不要那么心急，先听清楚怎么剪再下手，这才是严谨的精神嘛。首先，剪好之后要平摊在桌子上，两头各打个结，这样不就不会散开了嘛。然后因为我们看的是蓝色珠子，所以打结两头如果有黄色珠子的话就扔掉吧，反正也没用。做好之后，观察一下蓝色珠子的位置，这是不是相当于一个优化尺？只不过它量度的单位是珠子的直径而已。



可以证明，无论我们怎么剪，得到的一串东西之中，蓝色珠子的位置方案都相当于一个优化尺，这样的话我们就完成了刚才的任务了。

不过话又说回来，这还是不够的。既然随便剪都可以的话，有没有办法剪得巧妙一点，使最后得到的优化尺尽量短呢？回想一下，既然在剪断念珠之后我们要扔掉两头那些没用的黄色珠子，而一串念珠的个数又是有限的，那么我们扔掉越多，剩下的珠子不就越少，优化尺不就越短了？要想扔掉尽量多的黄色念珠，我们在两颗相邻的但是距离最远的蓝色珠子之间剪一刀不就行了！

这样的话，我们把念珠重新接好再剪一次，对比一下：



嗯，看来这是个好办法。如果我们对于正整数n能够找到含有n个蓝色珠子的循环差集，而使这个集合里边包含的念珠尽量少的话，剪一刀我们不就可以得到相当接近最简优化尺的一个优化尺方案了么？这看起来的确不错，然则有一个问题我们还没有想到。如果寻找符合条件的循环差集比寻找最简优化尺还要困难的话，我们这么麻烦绕这么大一个圈不是浪费生命么？

幸好，由于循环差集比优化尺的性质好得多（循环总是很讨数学家的欢心，嗯），寻找循环差集比寻找最简优化尺要容易得多。事实上，数学家们已经有一种方法可以直接生成那些可能是最符合条件的循环差集。这种方法一时半会是说不清的，大概就是将循环差集和一个所谓的“有限半线性空间”联系起来，这个“空间”里边有一些“点”和“直线”，分别代表了念珠编号和循环差集的一种读法，它们满足一些限定这个空间性质的公理，而通过这个“空间”数学家们就能找出最符合条件的那些循环差集。有趣的是，虽然名为“空间”，这东西和我们平时的观念可是大不相同，比如说“直线” 上面只有有限个“点”等等。只有脑子学得迷迷糊糊连常识都忘掉了的那些数学家才能完全掌握它们的性质，当然为了这个他们也牺牲了不少东西……

那么，这种方法的威力有多大呢？早在1984年，数学家Atkinson和Hassenklover就已经用这种方法给出了直到100个刻度的优化尺方案，而之后的验证证明，即使这些优化尺方案不是最简的也相当接近，比如说这次，Distributed.net验证得到含有25个刻度的最简优化尺就是当年他们给出的那个：

0 12 29 39 72 91 146 157 160 161 166 191 207 214 258 290 316 354 372 394 396 431 459 467 480
这些是刻度的位置。这个优化尺方案的总长度是480。

但很可惜的是，虽然这些优化尺方案非常接近最简的方案，但现在数学家们仍然没能证明用循环差集给出的优化尺方案就是最简的，所以数学家仍然需要用大规模计算的方式来验证一个最简优化尺方案。不过，因为已经知道一个非常接近答案的方案，所以搜索起来相对来说也容易多了，尽管与电脑游戏相比还是相当相当的难。

这么难的问题，到底有什么实际意义呢？要知道，计算这个问题所需的计算量足以做好几年的天气预报了，如果一点实际用途都没有的话那看起来还真是有点浪费。

不过你还真的别说，这东西除了在天线中和编码理论有点实际用途之外，就剩下理论上的趣味性了。在射电望远镜的天线阵列中，天线的排布就常常是排成 0-1-4-6的样子，可能也是为了尽可能好地利用天线位置测量吧。至于在编码理论中的用途嘛……我也不清楚……反正在信息交流越来越多的今天，编码理论的地位已经变得相当重要了，能有点用也算不错了。

那么，为什么那些数学家会对这样一个没多大用处的东西投入这么多的精力，连智商过人的 Golomb也是如此呢？又是为什么全球的志愿者都肯为这个东西投入如此多的计算能力呢？问题的答案在于两个字：“有趣”。已故的陈省身老先生说过，“数学有趣”，正是这个“有趣”使他们情不自禁不能自拔，也正是这个“有趣”使他们具有了一种对付越来越难的问题的勇气和信心。

所以说，有时候做研究不一定因为有用才去做，兴趣有时候是更好的导师。

延伸阅读：

这里有一个关于最简优化尺和Distributed.net的中文介绍：http://www.equn.com/forum/thread-4312-1-1.html

Distributed.net官方网站：http://www.distributed.net/

关于循环差集的一个很有趣的英文介绍：http://www.inference.phy.cam.ac.uk/cds/index.htm

Bismarck

头大的数学

Youth

好文~~

// 是不是放到数学类项目版面比较好？

fwjmath

已经在新发的帖子里边放了链接了~~~
关键是如果不放在这里的话没人看~~~放在这里了也还是没人看~~~

Youth

呵呵，我承认是在google reader里直接看过你space的rss了：）

20080030成电

非常好的文章

BiscuiT

我看了我看了～不然我不会加精的～～（虽然l连什么⑨的想法都说不出来。。

Julian_Yuen

看了两次....但吐不出槽的感觉还真是糟糕....好憋
泪目....哦的数学啊.....

fwjmath

不会困难到这个程度吧~~~至少我觉得还是应该可以理解的~~~
反正这种文章如果看不明白就是作者的错~~~

[ 本帖最后由 fwjmath 于 2008-10-26 22:49 编辑 ]

cnchina

是fwj原创的吗？写得很好吖。

Julian_Yuen

你可以理解为无法产生有趣的感觉（本人已经堕落了的说

昂宿星团人

虽然有的内容看不懂,但是感觉文章的语言很吸引人

20080030成电

于是数学家们被迫在他们的问题中加上一个补充条件，现在他们要寻找的刻度方案既要是“经济”的，也就是说每对刻度组合量出来的距离都不同；又要是最小化的，也就是说在满足这个条件的所有刻度数相同的刻度方案之中尺子长度最小的。

-------------------------------------
这个我看了几次不太明白 我的理解是任意3个刻度的距离都不同的最短的尺 对吗

gengli00

已经忘光数学常识的,飘过!

fwjmath

把 3 改成 2 就对了~~~