De Bruijin序列与魔术（二）——魔术《De Bruijin序列》

早点关注我，精彩不错过！

上一篇我们介绍了De Bruijin序列的基本数学内容以及其如何应用在魔术上的一些基本内容，今天我们就来学习一下这个经典的《De Bruijin序列》魔术。

De bruijin序列魔术

先看视频。

视频1 De Bruijin序列的魔术

魔术来源

和这个魔术的缘分，要追溯到大约大学时候，疯狂地学习数学，魔术，以及零星地查到的一点点数学魔术相关的内容。在果壳网上，我看到了一个叫Albert_Jiao的作者，它一系列的数学魔术文章是我那时候难得获得的一点养料。其中一篇就是介绍De Bruijin序列的。后来，在Magical Mathematics一书中，有2~4共3个章节的篇幅都在讨论这个内容，细细去看里面的来龙去脉一定会有很多的收获。这里仅就De Bruijin序列本身以及其魔术应用来描述。

魔术原理分析

这个数学魔术里用的编码，是一套神奇的编码，可以仅由特定位置的一个二进制表达就能推断位置，进而推断出一叠序列固定扑克牌的全部点数和花色，这就是这个魔术的编码通信原理。因为De Bruijin序列的存在，使得这样的编码变得可行。那最后一个问题来了，我们怎么找到一条适合人记忆的Debruijin序列呢？

还是那个原则，人脑是不太善于去记忆没有什么相互联系和逻辑的事物的，因为它会判断，这些东西没有价值，就像我在大学时候死活听不进也背不了有些工科老师上课讲的内容，因为那明明是数理逻辑，泛函分析，欧拉定理，为什么偏偏要给你讲成数字逻辑电路，光学工程，模拟电路？还搞一些莫名其妙，不着本质的概念来包装？可能有人能够接受这样的方式，对不起，我真接受不了。

相反，人们善于记忆有一定规律，甚至美感的事物，它会觉得那是对的，值得记忆的。比如，这个魔术里，我们用n = 5的de bruijin序列为例，能编码长度为32的序列，然后用扑克牌的红色和黑色来代表0，1得到对应的De Bruijin序列，然后，一副只用32张，A~8的扑克牌，可以简单想到的是，恰好可以用其中两位来代表花色，另外两位来代表点数，刚刚好能很合理地用好所有的信息。可问题来了，难道每个位置是哪张牌，真的要靠纯记忆吗？

好在有人已经给出了答案，在上述编码系统里，除了满足De bruijin序列的基本要求（黑色为0，红色为1），是一个可行解，在连续五张牌的首牌上，恰好由前两位代表花色（第一位代表颜色，0为黑色，1为红色（这里和单个二进制的红黑编码对应），第二位是0表示梅花或方块，1表示黑桃或红桃），现在最后一个问题是，后面的牌以怎样的规律推演出来？

我们借鉴线性移位寄存器的做法，每个下一位都由前面的值计算得到：

a(n) = (a(n - 3) + a(n - 5)) % 2，其实就相当于是往前的3，5位取xor的亦或运算，或者是不进位的二进制加法了。

由此得到的De Bruijin序列为（随意选择一个起点即可，比如这里的00000，因为反正这是一个循环序列）：

0000100101100111110001101110101

如图所示：

图2 De Bruijin序列魔术编码表

不过遗憾的是，这并不是一个严格的De Bruijin序列，因为它只有31项，00000并没有出现，但是，我们很容易在上面这个序列开头再加上一个0，就得到了32项，也刚好得到了所有需要的编码，只不过在这个0这里，其编码规律被打破了，但此时却构成一个圈，是真的De Bruijin序列了。好在，我们也只需要记住这一个特例就够了。也因为这个原因，原本符合C32群描述的可以随意切牌的循环序列的性质没有了，我们得去记忆这个特殊的位点随着切牌不断移动。至于最后怎么往后推演更容易记忆，我的方案是直接看牌点是否大于等于4（注意这里8相当于0，可以记忆为进位以后溢出了，其底三位的编码就是000）以及颜色是否是黑色，其中一个成立为真，红色，同时真或假为假，黑色。这样记忆几遍以后，能够比较快速和熟练地把所有五张牌推演出来。唯一例外要记住的是，10000以后，得补一个本该是1，但是这里强行插入了一张梅花8，其余照旧。

不过，如果你实在懒得去背这些公式，直接把这个表打印下来去现场秘密地查找也可以，不过得想个理由，比如这里有上帝写给我的密码，或者偷偷地看。我长这么大，唯一看过别人表演这个魔术，就是Albert老师，在我去深大参加的一次数学魔术沙龙里。看来数学魔术日后如我所想，能够在数学家和魔术师中间都被认同和接受，并广泛流传开来，真的不是一件容易的事，至少，我这辈子是打算搭进去了。

不知道大家看了这个牌序花色点数的递推公式有没有些感觉，虽然这里写成了二进制的递推关系，但本质上也是一个牌序的递推关系，不妨我们从牌序本身的角度来理解下这个递推关系，我们有：

N_(i + 1) = Ni << 1 + ([Ni / 4] + [Si / 2]) % 2

S_(i + 1) = Si << 1 + [Ni / 4]

其中N为点数，是0~7之间的数（8的码点是0），Ni<<1是3位二进制数向左的逻辑移位，等价于2Ni % 8，Si << 1是2位二进制数向左的逻辑移位，等价于2Si % 4，因此这个式子又可以写为：

N_(i + 1) = 2Ni % 8 + ([Ni / 4] + [Si / 2]) % 2

S_(i + 1) = 2Si % 4 + [Ni / 4]

它和Richard Osterling序的结构的递推关系式已经很像了，都是一系列花色和点数交叉关联的递推关系，只不过这里限定在了数字8以内，我们到对应章节再详细介绍之。

不过估计熟悉数学魔术的你也想到了，这个数学原理很棒，但是作为一个成熟的魔术表演还远远不足，只拿着阉割的只有32张牌的一叠，而且还奇怪的只有8以内的数字，这数学雕琢和限制的痕迹也太过明显了。但这一切都苦于这个D(2, 5)序列本身的能量。一个简单的处理自然是利用软限制，补齐剩下的20张牌，只不过控制观众选牌的范围在这32张以内即可。

但这总归不完美，我希望能够找到一个接近51~55以内长度的De Bruijin序列，满足核心的一一对应的性质，并有简单的递推公式递推以及容易计算的编码和解码公式能够计算牌的值，方便记忆和使用。于是我开启了一次泛化之旅，看能不能用计算机再搜寻出一些其他的序列，这部分的成果，我们下篇文章来介绍，敬请期待。

我们是谁：

MatheMagician，中文“数学魔术师”，原指用数学设计魔术的魔术师和数学家。既取其用数学来变魔术的本义，也取像魔术一样玩数学的意思。文章内容涵盖互联网，计算机，统计，算法，NLP等前沿的数学及应用领域；也包括魔术思想，流程鉴赏等魔术内容；以及结合二者的数学魔术分享，还有一些思辨性的谈天说地的随笔。希望你能和我一起，既能感性思考又保持理性思维，享受人生乐趣。欢迎扫码关注和在文末或公众号留言与我交流！

扫描二维码

关注更多精彩

De Bruijin序列与魔术（一）——De Bruijin序列简介

这到底是怎么想到的！！！

一道北大强基题背后的故事（七）——特征根公式的来龙去脉

用排列组合来编码通信（七）——《我的5/4张牌的预言》

好魔术背后的秘密

点击阅读原文，往期精彩不错过！