序列周期性与魔术（四）——周期序列数学性质深入探秘

在上一讲中&＃xff0c;我们提到的《同花顺or金刚》这个魔术里&＃xff0c;有一个非常令人惊讶的操作&＃xff0c;把一叠牌依次发成两叠&＃xff0c;却不改变其以3为周期的周期性。相关内容和更早内容请戳&＃xff1a;

传送门&＃xff1a;

序列周期性与魔术&＃xff08;三&＃xff09;——经典应用与改良

序列周期性与魔术&＃xff08;二&＃xff09;——扑克牌叠里的周期性

序列周期性与魔术&＃xff08;一&＃xff09;——数学里的函数周期性

以下是相关表演的视频&＃xff1a;

视频1 同花or金刚

今天我们接着上一讲&＃xff0c;来抽象一下这个问题以及给出相应的建模和证明。

同花顺or金刚中的核心数学结构

我们首先抽象一下这个流程的起始状态和过程&＃xff1a;

假设有一个m个人参加&＃xff0c;每人依次发牌&＃xff0c;每人总共n张牌游戏&＃xff0c;总共需要mn张牌&＃xff0c;编号为1:mn。任何一个人所发得的牌构成一个牌组&＃xff08;集合&＃xff09;&＃xff0c;我们只关心其组合&＃xff0c;不关心其排列。

这样&＃xff0c;在发m叠牌的操作下&＃xff0c;每个人的牌处在牌叠的模m同余位置。而对每张牌属于的玩家这个性质而言&＃xff0c;具有m长度的子周期性&＃xff0c;周期数量是n个&＃xff0c;即真实的集合内牌的张数。依据前面文章的结论&＃xff0c;牌属于哪个玩家的性质满足关于切牌操作的Cm群结构&＃xff0c;而切n张则满足Cn群结构的对称不变性。

我们知道&＃xff0c;对其进行m叠发牌再合起来会变成同整除n位置&＃xff0c;看起来是个不错的结果&＃xff0c;实现了同余位置合成一叠相邻牌的作用。可是如果发成k叠再按照指定或者任意顺序合起来&＃xff0c;那么&＃xff0c;牌叠还有可能保持某些特殊的性质&＃xff0c;比如&＃xff0c;仍然满足是一个m长的n个真实周期的序列吗&＃xff1f;

这个问题&＃xff0c;要从两个方面来看。首先&＃xff0c;每个发k叠牌发出的子牌叠&＃xff0c;是否一定都是同一个周期序列的子串&＃xff08;即其一定可以补齐成一个真的同一个周期序列的若干周期加上一些余项&＃xff09;&＃xff0c;且每个周期本身恰好是原m长周期元素的重排&＃xff1b;另外&＃xff0c;最后要像整除m牌叠发m叠后随便顺序合起来那样保持周期性。后者其实估计很难做到&＃xff0c;极端的例子是直接发mn叠&＃xff0c;那随机合起来就相当于在Smn空间内洗牌了。

所以&＃xff0c;我们先尝试说明&＃xff0c;每一个子牌叠是同一个周期序列的子串&＃xff1b;再取一个若保持周期性&＃xff0c;不同合起来牌叠的方法仅相差一个二切&＃xff0c;也就是一定同时保持或者不保持周期性的k &＃61; 2的特例来说明当m&＃xff0c;n满足怎样的条件的时候&＃xff0c;允许这样的二分发牌。

每一次发k叠牌都相当于进行子群&＃xff0c;陪集的划分以及形成新的表现为周期序列的群。我们这里忽略发牌中产生的reverse操作&＃xff0c;因为其对同余性质没有本质影响仅改变同余位置的值而已。特别的&＃xff0c;k &＃61; 2的时候&＃xff0c;相当于一次anti-faro shuffle。

1. 证明&＃xff1a;当m是质数&＃xff0c;且(m, k) &＃61; 1&＃xff0c;每一个发出的子牌叠都是一个长度为m的周期序列的子串。

这个问题在《Mathematical Card Magic》一书中提到&＃xff0c;叫做Reduced Residues Modulo A

Prime&＃xff0c;由此发明出的魔术原理是Sands’ Luck Principle。实际上&＃xff0c;这里的性质和大名鼎鼎的费马小定理的一个等价形式&＃xff08;跨越千年的RSA算法一文中有提到&＃xff09;极其相像。即&＃xff0c;对于质数m&＃xff0c;任意的k为底数的幂具有m - 1长度的周期性&＃xff08;恰是因为k ^ m &＃61;&＃61; k (mod m)&＃xff0c;周期性由此而来&＃xff0c;其等价形式k ^ m &＃61;&＃61; 1 (mod m)要求k不是m的倍数&＃xff0c;即除掉的k要和质数m互质即可&＃xff09;&＃xff0c;但不一定是最小周期。只不过这里是乘积&＃xff0c;费马定理那里是乘方。这里我们也进行一下证明&＃xff0c;除去跑马灯模型的证明外&＃xff0c;一般思路也是极其相似的&＃xff1a;

m是质数&＃xff0c;(k, m) &＃61; 1&＃xff0c;即k不是m的倍数。发出去的牌即为a, k &＃43; a, 2k &＃43; a, ……, (m - 1)k &＃43; a, ……。显然&＃xff0c;下一项mk &＃43; a &＃61;&＃61; a (mod m)&＃xff0c;序列具有m长度的周期性。此时&＃xff0c;我们希望能够说明&＃xff0c;对于l in 0:(m - 1)&＃xff0c;有{a | l in 0:(m - 1), lk &＃61;&＃61; a(mod m), a <&＃61; m - 1} &＃61; 0:(m - 1)&＃xff0c;如果这个命题成立&＃xff0c;那么&＃xff0c;相当于证明了m是这个子序列的最小周期。

该证明如下&＃xff1a;m是质数&＃xff0c;所以(l, m) &＃61; 1&＃xff0c;故(lk, m) &＃61; 1&＃xff0c;对任意l&＃61;1:(m - 1)成立。而lk | m的余数一共仅有1:(m - 1)种。&＃xff08;lk &＃43; a将仅仅对所有的余数进行模加法的平移&＃xff0c;不改变性质&＃xff0c;当l &＃61; 0的时候&＃xff0c;取整除的余数为0&＃xff09;若不存在l1, l2&＃xff0c;使得l1k &＃61;&＃61; l2k(mod m)&＃xff0c;则所有lk | m的余数将取遍所有1:(m - 1)。否则&＃xff0c;根据容斥原理&＃xff0c;若l1k &＃61;&＃61; l2k(mod m)&＃xff0c;则(l2 - l1)k &＃61;&＃61; 0 (mod m)&＃xff0c;与最开始的假设矛盾&＃xff0c;故原命题成立。

最后其实我们发现&＃xff0c;m可以不是质数&＃xff0c;只要满足(m, k) &＃61; 1&＃xff0c;而m | l不成立&＃xff0c;所以&＃xff0c;m | lk不成立&＃xff0c;不一定需要m是质数这么强的条件&＃xff0c;以上推导过程就成立了。而m是质数的条件只不过使得k的选择可以只要不是m的倍数就可以&＃xff0c;变得更简单罢了。

而这样的发牌方式究竟会把一个原本1:m排列的牌变换成什么序列呢&＃xff1f;看起来&＃xff0c;它是由一系列k’ &＃61; k mod m的同余的序列连接而成的&＃xff0c;取值范围是0:(k’ - 1)。仍然考察长度为m的序列&＃xff0c;那么每个同余序列的长度就是(m -1) / k’ &＃43; 1。而同余的余数变化遵循的规律是&＃xff0c;以余a1 &＃61; 1起始&＃xff0c;下一个余数值为ai &＃43; 1 &＃61; kl &＃43; ai mod m&＃xff0c;l是使得kl &＃43; ai > m的最小值的l&＃xff0c;这里从l &＃61; 0到lmin也恰好对应上一个同余序列完成到下一个开始&＃xff0c;长度为lmin - 1&＃xff0c;取到lmin的时候恰好是下一个同余序列的开始。所以这个序列的变换只能够证明必然会是一个全排列&＃xff0c;受到m&＃xff0c;k两个值的影响&＃xff0c;具体的变换策略根据以上递推关系式子得来&＃xff0c;而这恰是一个同余加法下的等差数列。

2. k &＃61; 2时&＃xff0c;当且仅当m&＃xff0c;n均为奇数时&＃xff0c;发k叠牌不影响周期性。

根据前面的证明&＃xff0c;要求(m, k) &＃61; 1&＃xff0c;所以m必须为奇数&＃xff0c;设m &＃61; 2p - 1。显然&＃xff0c;对k &＃61; 2的情况&＃xff0c;其两个子牌叠取得的周期索引序列的情况为&＃xff1a;

第1叠&＃xff1a;1, 3, ......, 2p - 1, 2, 4, ......, 2p - 2, 1,3, ......

第2叠&＃xff1a;2, 4, ......, 2p - 2, 1,3, ......, 2p - 1, 2, 4, ......

显然&＃xff0c;第二叠的起点&＃xff0c;落后第一叠的距离是p张牌。我们假设均将第1叠放在第二叠上&＃xff0c;因为反过来二者仅相差一个二切&＃xff0c;不改变周期属性。

若n为偶数&＃xff0c;n &＃61; 2q&＃xff0c;那么发出的每叠牌张数均要和延迟的距离q模n意义下相等。满足第一叠张数q(2p - 1) &＃61;&＃61; p(mod 2p - 1)&＃xff0c;这显然不成立&＃xff08;左边是整除&＃xff0c;右边显然互质&＃xff0c;由相邻两数互质以及除法原理&＃xff09;&＃xff0c;或者直观上看&＃xff0c;(2p - 1) | q(2p - 1)&＃xff0c;两叠牌都是两个完整周期&＃xff0c;容不得半点错乱。

若n为奇数&＃xff0c;n &＃61; 2q - 1&＃xff0c;则第一叠张数((2q - 1)(2p - 1) &＃43; 1) / 2 &＃61;&＃61; p(mod 2p - 1)要求成立&＃xff0c;即要求&＃xff08;2p - 1) | (q - 1)(2p - 1)&＃xff0c;这显然成立&＃xff0c;故此时&＃xff0c;原命题成立。

至此&＃xff0c;终于完成了整个同花顺魔术的数学分析&＃xff0c;也得到了其拓展法则&＃xff0c;除了最开始说明的发n叠过程再任意收拢切牌&＃xff0c;是整除n集合向同余m集合的转化&＃xff0c;最后这个任意发k叠牌收拢的规律也进行了根本性的说明&＃xff1a;只有当k &＃61; 2的anti-faro shuffle以及周期大小m和周期数n均为奇数的时候才成立。另外&＃xff0c;(k, m) &＃61; 1时&＃xff0c;任何一个子牌叠都是周期子序列而m为质数的时候可简化为k只要不是m的倍数即可。最后&＃xff0c;对m的理解其实是周期集合的大小&＃xff0c;而n是实体扑克牌的周期个数,它们也分别对应两个循环群的结构。如果n张也构成一个集合&＃xff0c;那仅仅是用属于关系表示的一种集合性质&＃xff0c;是表达切n张不变性的Cn群&＃xff0c;而m对应的才是真的作为一般切牌对牌叠变化规律的周期来存在&＃xff0c;有着Cm群性质的集合。

数学就是这么干净&＃xff0c;这么美&＃xff0c;感谢上帝&＃xff0c;让我此生能遇到你&＃xff0c;了解你&＃xff0c;爱上你。

有了这个结论&＃xff0c;再去设计相关的操作流程的时候&＃xff0c;关于到底是否满足周期不变性就一目了然了。在一些并不满足上述条件的m, n, k中就需要避免这个操作。在读《Magical Mathematics》一书中看到类似论述部分的时候&＃xff0c;边读边在书边记录下了这么一个流程&＃xff0c;和本流程的周期&＃xff0c;同余&＃xff0c;整除性质的应用方法及其相似&＃xff0c;而且几乎浑然天成地应用了约瑟夫问题的结论&＃xff0c;在一些数学不好处理的地方也巧妙地利用了魔术表演的方法处理&＃xff0c;其妙处令我心中很是惊喜。关于约瑟夫问题&＃xff0c;我们会再后面写文章单独介绍&＃xff0c;这边先放表演给大家&＃xff0c;详细解释就不写了&＃xff0c;相信你能看懂。

老规矩&＃xff0c;再放一个下期即将分析的魔术&＃xff0c;先睹为快。

视频2 春字术

我们是谁&＃xff1a;MatheMagician&＃xff0c;中文“数学魔术师”&＃xff0c;原指用数学设计魔术的魔术师和数学家。既取其用数学来变魔术的本义&＃xff0c;也取像魔术一样玩数学的意思。文章内容涵盖互联网&＃xff0c;计算机&＃xff0c;统计&＃xff0c;算法&＃xff0c;NLP等前沿的数学及应用领域&＃xff1b;也包括魔术思想&＃xff0c;流程鉴赏等魔术内容&＃xff1b;以及结合二者的数学魔术分享&＃xff0c;还有一些思辨性的谈天说地的随笔。希望你能和我一起&＃xff0c;既能感性思考又保持理性思维&＃xff0c;享受人生乐趣。欢迎扫码关注和在文末或公众号留言与我交流&＃xff01;
扫描二维码关注更多精彩序列周期性与魔术&＃xff08;三&＃xff09;——经典应用与改良
《猫和老鼠》里的魔术艺术&＃xff08;五&＃xff09;——一定要合理&＃xff01;
扔硬币中的思考——隐含变量建模魔术里的集合、映射和关系&＃xff08;十&＃xff09;——天才之作《Tiny Berglas Effect》我和Double Lift的故事&＃xff08;五&＃xff09;——升华篇点击阅读原文&＃xff0c;往期精彩不错过!