尼古拉斯·德布鲁因的序列

答案就在荷兰数学家尼古拉斯·霍弗特·德布鲁因（也叫迪克·德布鲁因）研究过的一个数学概念之中。这位数学家出生于1918年，于2012年逝世，他的研究工作主要关于图论、分析、非周期性镶嵌、自动定理证明的方法和今天被称为“德布鲁因序列”的数列，用这些序列就能解开上面介绍的奇妙的扑克魔术。

但这些序列和相关的图在数学和应用上的重要性远远超出了魔术领域，因为这些概念在生物信息学中也占有一席之地，在将脱氧核糖核酸（以下简称DNA）测序仪分解出来的众多短小的遗传序列重新拼起来的时候，它们就能派上用场。

1．魔术师的表格

如果你将32张一套的扑克牌按照的顺序排好，那么对于连续的五张牌，只要知道它们的颜色（黑色或者），就能知道这些牌是什么。这就是文章中提到的魔术的关键所在。

这个表格能让我们实现这个魔术。根据黑色和组成的五元组（左列中的32种可能性），表格能告诉你它们代表的那五张牌。

我们思考一下那个需要5位观众的扑克牌魔术。你大概已经发现了，整叠牌从来没有被洗过，只是被人检查过，然后第一位观众进行了切牌。5位观众并没有独立选择这5张牌，而是选择了5张连续的牌，它们是由第一位观众的切牌决定的，当然，我们不知道他是怎么切牌的。

这个魔术的技巧让魔术师知道，5位观众中分别由谁拿到了红牌或黑牌。拿到黑牌的观众有可能一位也没有，也有可能有一位、两位，等等。魔术师知道的不仅仅是人数，还有到底是谁拿到了黑牌，又是谁拿到了红牌。这里一共有32种可能性：第一位观众可能拿到红牌或黑牌（2种情况），第二位观众同理（2种情况），如此等等，最后一共有2×2×2×2×2 = 32种不同的情况。下面就是这些情况的列表：

借着花言巧语，魔术师知道了32种五元组中到底哪个是正确的（上面以粗体表示）。魔术用到的这套32张扑克牌，预先按照特定的顺序排好（后文会细说），我们有32种方法对这32张牌进行切牌。魔术师不知道切牌的具体位置，而这就是他需要得知的信息。简单来说，魔术师在表演魔术的过程中，得到了在32个元素中出现了哪一个元素的信息（相当于5比特的信息），这正是他要弄清第一位观众的切牌位置所需的信息。

从信息量来说，这不算什么奇迹：他需要5比特的信息（切牌的位置），也得到了5比特的信息。剩下的就是要知道具体怎么做才能用收到的5比特信息确定切牌位置。现在问题在于，要找到32张牌的一个次序，使得魔术师只要知道5张连续的牌的花色（红色或者黑色），就一定能知道这5张牌是什么，也就是第一位观众的切牌位置。

这等价于下面的问题：找出一个由32个符号“黑”和“”组成的序列，其中有16个黑、16个红，而且在序列中取出5个连续元素的32种方法各不相同，正好对应用5个黑或红符号组成序列的32种方法。需要注意的是，当说到连续的扑克牌时，这里指的是在取出一叠牌中的最后一张牌之后，自然要回到第一张牌，所以，第30、第31、第32、第1和第2张牌就相当于五张连续的扑克牌。

这个问题的解答之一就是。这样一串32个符号也叫5阶德布鲁因序列。在1946年，尼古拉斯·德布鲁因正是在寻找和研究这样的序列，当时他正在解决另一位数学家此前提出的一个猜想。

3．二维的德布鲁因序列问题

在二维的情况中，德布鲁因序列就变成了“德布鲁因环面”。对于，由0和1组成的2×2方阵一共有16种（图a）。

现在的问题就是，有没有办法在4×4的方阵中填入0和1，使得在将它看成环面（将顶部和底部、左边和右边分别粘在一起）的时候，只要考虑2×2大小的滑动窗口的所有16种位置，就能找到上面列出的16种2×2方阵？图b给出了一种解答。

如果我们考虑的不是2种，而是4种符号的话，那么2×2的方阵就会一共有种可能性，而我们（至多）可以指望用由16×16方阵构成的环面，通过滑动窗口的方式得到在4种符号的情况下所有可能的2×2方阵。图c用颜色给出了一种解答。

如果我们填入的不是四种颜色，而是用四种将正方形沿对角线分割再涂上黑白色的方法，那么我们就得到了一个有趣的抽象图（图d）。

这样的曲面密铺有现实应用的意义。在一个画满这种图案的房间中，机器人仅凭观察脚下的四个方格，再利用一个合适的表格（就像魔术师偷偷用的表格那样），就能知道自身的确切位置。