最“经济”的直尺[修改稿1]

注:本文遵守首页上的CC版权声明,转载请注明作者与出处,谢谢!

直尺可谓是人人必备的文具,是抄笔记划重点的必备武器,平时要量度个什么距离也需要它出马。要是我说刻度是直尺的灵魂,恐怕没有多少人会反对。没有刻度的直尺好比没有字的书,形体还在,但是毫无用处。

我们平时用的直尺大概有刻度的范围有15厘米,每厘米有一个大刻度,每毫米有一个小刻度,用起来的确相当方便。但是在数学家(更确切地来说是组合学家)眼中看来,这种等间距标记刻度的方法未免太浪费,如果允许刻度不均匀分布的话,用同样数目的刻度能量度的不同距离会多得多。当然,直尺是肯定有零点的,所以我们要求最左边的刻度标记为0。

下面我们来看一个简单的例子。

考虑一把只有4个刻度的直尺。如果这4个刻度是等间距分布,相邻两个刻度之间间隔1厘米的话,我们只能量度从1厘米到3厘米一共3种距离。但如果我们将刻度刻在0, 1, 4, 6厘米处的话(如下图),数一数就能知道这样刻度的直尺能够量度从1厘米到6厘米一共6种距离,功能比刻度等间距分布的直尺要大上一倍。

 

所以说,要想挖掘直尺量度距离的能力,我们就需要合适的刻度方案,而不是以往的那种“平均主义”式的等间距刻度方案,因为这种方案的效率太低了。我们的目标就是在刻度数目一定的情况下使直尺能量度的距离尽量的多,最好每对刻度能量出来的距离都不同,这样就是最理想的情况了。我们把这个条件叫做直尺的“最经济”条件,因为在这种情况下直尺能够量出种类最多的距离,这样的话买这把直尺的人就会觉得物超所值了。

但是,满足这样的条件的刻度方案是否存在呢?回答是肯定的。如果我们要设计一个符合条件的包含4个刻度的直尺,除了刚才上面的做法之外,我们还可以把刻度分别刻在0, 9, 99, 999厘米处,这样的话也可以保证每对刻度能量出来的距离都不同。对于更多的刻度也可以照葫芦画瓢。这样的话,我们就可以确保“最经济”的刻度方案是存在的了。

虽说依照上面提到的刻度方案满足“最经济”的条件,看起来很不错,但是想象一下,一个人在街上带着一把长10米但是上面只有4个刻度的尺子,这个景象是多么的滑稽。于是,新的问题出现了:对于某个确定的刻度数量,有没有办法找到这样一个“最经济”的刻度方案,使得它对应的直尺长度在所有“最经济”的刻度方案中是最小的呢?

第一个考虑这种尺子的是美国数学家Solomon W. Golomb,这是个颇为严肃的,没啥花边新闻的组合学家。而这种尺子很自然也以他的名字命名,叫做Golomb尺,毕竟是他第一个提出这个问题的。一个刻度方案只需要满足“最经济”的条件就可以被称为Golomb尺,也可以叫优化尺。如果这个刻度方案同时满足最小化条件的话,它就被称为最优Golomb尺,也可以叫最简优化尺。

再加上这个条件之后,问题的答案就远非显然了。之前我们只需要随便找出一个可行的方案就可以了,现在我们需要检查每一个优化尺。二者的难度显然不在一个层次上。那么,聪明而固执的数学家们有没有什么好方法呢?

遗憾的是,没有。为了验证一个刻度方案是否最简优化尺,我们仍然需要对每一个可能的方案进行验证。由于可能的方案数目非常多,所以这种验证能力有限。为了验证含有25个刻度的最简优化尺,我们需要让7500个英特尔酷睿处理器连续不间断运行3000天!可见这个计算量是多么的大。

虽然要确认一个优化尺方案是否最简是很困难的,但要给出一个很接近最简方案的优化尺还是可以做到的。实际上,数学家们早就对一种与优化尺相似的数学对象相当熟悉了,这东西有一个很唬人的名字:循环差集。虽然名字听起来比较吓人,但它其实并不难理解,它其实就是优化尺的环形版。因为数学家对它比较熟悉,如果能把循环差集转化为优化尺的话,对于优化尺的研究是很有帮助的。

我们可以用念珠当作循环差集的一个模型。普通的念珠都是只有同一种颜色的,比方说是黄色吧。如果我们挑选其中的一些珠子,把它们染成另外一种颜色,比如说蓝色吧。然后我们考察蓝色念珠之间的距离,在这里我们定义两颗念珠之间的距离为它们之间相隔的其它念珠个数最小值再加1。如果每两颗蓝色念珠的距离都不同的话,我们就把这种染色方案称为一个循环差集。

你是否感到上面的描述似曾相识呢?“如果每两颗蓝色念珠的距离都不同的话”,这跟优化尺的“最经济”条件“每对刻度能量出来的距离都不同”几乎就是一模一样。如果我们把蓝色念珠看作整串念珠中的“刻度”的话,优化尺跟循环差集的定义是一模一样的。它们的差别在于,优化尺是定义在笔直的直尺上的,而循环差集是定义在环形的念珠上的。那么,如果我们能把念珠变成直的,循环差集会不会转化成优化尺呢?

我们来试一下。由于我们关注的对象只是蓝色的念珠,所以如果剪开的两头有黄色的念珠的话,我们大可以将它们去掉。下图是对上图的念珠随便剪了一刀之后得到的情景:

观察一下蓝色珠子的位置,这是不是相当于一个优化尺?只不过它量度的单位是珠子的直径而已。所以说,通过循环差集我们真的可以获得优化尺的方案。

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

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

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

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

幸好,由于循环差集比优化尺的性质好得多,寻找循环差集比寻找最简优化尺要容易得多。事实上,数学家们已经有一种方法可以直接生成那些可能是最符合条件的循环差集。这种方法一时半会是说不清的,大概就是将循环差集和一个所谓的“有限半线性空间”联系起来,这个“空间”里边有一些“点”和“直线”,分别代表了念珠编号和循环差集的一种读法,它们满足一些限定这个空间性质的公理,而通过这个“空间”数学家们就能找出最符合条件的那些循环差集。有趣的是,虽然名为“空间”,这东西和我们平时的观念可是大不相同,比如说“直线”上面只有有限个“点”等等。这代表了数学可以达到的一种抽象的高度,它颠覆了人们对“空间”的概念。

那么,这种方法的威力有多大呢?早在1984年,数学家Atkinson和Hassenklover就已经用这种方法给出了直到100个刻度的优化尺方案,而之后的验证证明,即使这些优化尺方案不是最简的也相当接近,比如说这次,人们验证得出的含有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。

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

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

不过你还真的别说,这东西除了在天线中和编码理论有点实际用途之外,就剩下理论上的趣味性了。那么,为什么那些数学家会对这样一个没多大用处的东西投入这么多的精力,连智商过人的 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

Advertisements

One thought on “最“经济”的直尺[修改稿1]

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s