ＭＥＮＳＡ测验题【转帖】

雄伟

ＭＥＮＳＡ是个智商超出平均值两个均方差的人的团体。这样的人约占总人口２．２％，平均每四十五个人里有一个，算是很聪明的人了。这些题目大部分有图，转贴不易；有时也有文字题，但是我们的英语词汇量往往不够，做不出来。比如，下面这一道，有没有愿意试试的？
图一：　ＦＩＹＪＳ

　　　　ＧＮＬＡＨ

　　　　ＤＫＣＸＰ

　　　　ＴＲＷＥＵ

　　　　ＢＶＯＭＱ

　　二十五个不同的字母排成正方形。从任何一个字母出发，可以横行、竖行或斜行到下一个字母，如果字母不重复的话，能够组成的最长的英语单词是什么？

　　这是一个文字题。但是，在不少科学研究领域里，特别是做计算机模拟的时候，我们经常使用类似的系统。假设每一个字母是放在一个５×５的正方晶格的格点上。一个格点的上下左右四个格点，相距为１，称为最近邻（ＮＮ，Ｎｅａｒｅｓｔ　Ｎｅｉｇｈｂｏｒ）；斜向的四个格点，距离是√２，称为次近邻（ＮＮＮ，Ｎｅｘｔ　Ｎｅａｒｅｓｔ　Ｎｅｉｇｈｂｏｒ）。如果在计算机上解这个题，一个等价的叙述可以是这样的：某人从任一格点出发，每一步随机地走向ＮＮ或是ＮＮＮ，一个格点只能经过一次，当他在某一格点终止时，他走过的路径可以标记为一串字母，在所有可能的字母串中，哪一个构成了最长的英文单词？

　　这是一个所谓的"随机游动"（ＲＭ，Ｒａｎｄｏｍ　Ｗａｌｋ）的例子。一个更有趣、更一般的问题是：把二十五个不同的字母任意放在５×５正方晶格的格点上，有多少种配置，它们的所有符合上述规定的ＲＭ都不是英文单词？

　　为什么说这个推广了的问题有趣呢？英文单词可以看作是客观外界的规则（比如有机大分子的结构）；放在晶格上的字母可以看作无序的原子，但就是这样任意的摆放，突然从无序造成了有序的自组织现象--出现了与外界规则契合的单词。

　　复杂的现象就可以这样从很简单的现象里产生出来。或许生命就是通过类似的过程从无机物里产生的。比如，关于生命在地球的起源，有一种假设是最初的有机分子来自外太空。观察到有机分子，是六十年代四大天文发现之一（其它三个是发现脉冲星、类星体和微波背景辐射）。但是至今为止的太空探索都未发现别的星球有生命。我们所处的是四维时空，但是现在"超弦理论"认为物质可以处在更高维的时空。这样，对外太空的有机分子，就可以有进一步的设想：它们原来处在高维时空里，高维空间的复杂性使得原子易于结合成复杂的结构。但在高维时空中，相对而言，这仍然是有序程度很低的"简单"结构。只有当投射到四维时空后，它们才成了可以缓慢地进化到生命的有机分子。

　　怎么试验这种想法？上面的文字题就是个有启发的例子。在一维空间（直线）里，每个字母只有两个邻居，随意的字母排列很难组成单词。但在平面上，较复杂的空间引入了较多的邻居，在随意的字母配置里就可以很容易地发现一条"随机游走"的路径，把它拉直后放到一维空间，它就成了英语单词--高维空间里似乎无序的配置给出了在低维空间里有序的排列。

　　问题是有单词的配置的比例是多少？如果占配置总数的比例很低，那么复杂现象就很难自发地产生。比如图一显然是出题人有心摆弄的结果。如果比例很高，找个不识字的小孩随手一撒，都可以产生英文单词。

　　这个计算比例的问题，现在的计算机大概还解决不了，至少用穷举法解决不了。可能的配置总数是２６的价乘，Ｓｔｉｒｌｉｎｇ公式（当ｎ足够大）

　　给出的近似值是４乘上１０的２６次方。面对这样的计算量，电脑只能干瞪眼。

　　严格地讲，由于正方晶格的对称性，我们只要计算八分之一的配置就行了。图二是把图一沿顺时针方向旋转了９０度；图三是对图一作了个镜面反射，以左上角至右下角的斜线为对称轴。它们（及从它们的旋转而产生的图）包含与图一同样的单词。

图二：　ＢＴＤＧＦ　　　图三：　ＦＧＤＴＢ

　　　　ＶＲＫＮＩ　　　　　　　ＩＮＫＲＶ

　　　　ＯＷＣＬＹ　　　　　　　ＹＬＣＷＯ

　　　　ＭＥＸＡＪ　　　　　　　ＪＡＸＥＭ

　　　　ＱＵＰＨＳ　　　　　　　ＳＨＰＵＱ

　　八分之一的配置数是５乘上１０的２５次方，这仍然是一个大到无法处理的数目。而且如何构造这八分之一的配置，本身就不是一个容易的问题。

　　由布鲁斯·威利（Ｂｒｕｃｅ　Ｗｉｌｌｉｓ）主演的电影《Ｍｅｒｃｕｒｙ　Ｒｉｓｉｎｇ》中，美国安全局（ＮＳＡ）把发往驻外机构的指令藏在密密麻麻的字母里，他们认为这是任何计算机都无法破译的。但是一个患自闭症的孩子却有本事把指令读出来。于是，围绕着这个孩子的生与死，正派与反派明争暗斗厮杀了一场。

　　不过，这样的天才大概只有电影里才有。实际情况是：你能把图一中的单词找出来，也就不太简单了。

柳泪

哇塞··好专业··不玩

蓝忧无泪

{:2_26:}好长,找时间再看~