完美洗牌的秘密（四）——（反）完美洗牌第三定理

教育 2024-08-23 18:08 广东

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

在前两篇文章中，我们介绍了完美洗牌定理和第二定理，传送门：

完美洗牌的秘密（三）——（反）完美洗牌第二定理续

完美洗牌的秘密（二）——完美洗牌第二定理

完美洗牌的秘密（一）——（反）完美洗牌定理

尤其是在完美洗牌第二定理中，我们尝试说明多次完美洗牌以后，牌的位置索引变化的规律的时候，采用了变换观察排列的方向来化归问题的角度。今天，还有另外一个角度今天打算介绍给大家，由此，还引出一个极为重要的结论。

奇数张完美洗牌过程机理探究

在上述完美洗牌第二定理的公式中，奇数的情况十分简明，而偶数情况十分复杂，所以一个可行的理解思路是，我们把奇数时候的公式理解透彻，然后再看偶数情况可否化归过来就好了。

那当牌叠张数为奇数的时候，到底有怎样的魔力呢？

我们试着观察在洗牌前的任意两个索引位置i和j（不妨设i < j），如果一次完美洗牌时，i和j处在同一个半叠中，那显然，i和j中间的每一张牌的左侧都插入了一张牌，最后一张牌的右侧也插入了一张。因此，他们的距离（缝隙个数，长度，或者算尾不头的牌张数）从原来的(j - i)变成了2(j - i - 1) + 1 + 1 = 2(j - i)。当然，直接理解为不算头部i的后面(j - i)张牌的每一张前面都多了一张，而j还是尾部，那自然距离就成了2倍了。

这一点倒是不难，直接根据完美洗牌定理也可以很方便地计算出来。但是，如果这两张牌原本并不在同一个半叠里，这个推导还能够成立吗？

如果我们强行去推导当i和j分别处在两个半叠时候它们之间距离的公式，分情况讨论，自然也可以得到，这是成立的。不过这里虽然算出来验证了，但不是最简洁的，可能就没有探寻到数学上最本质的结构。我们这里不妨换一个角度看，我们来仔细观察一下，当牌叠张数为奇数的时候，一次完美洗牌对于原本两张位置为i和j的牌之间的牌而言，重点看看当它们处在不同的半叠内的时候，发生了什么。

我们把多一张的那一叠叫A，少一张的叫B，i和j分别在这两叠里。我们顺着i的位置往后走，在到达底部，即A的最后一张之前，距离变两倍的规律显然成立，每往后走一张，都有一张在其上插入。我们接着看下一张，也就是B叠的第一张，在到达它以前，是A叠的第一张，等效地插入其中。而且，这次不光没有改变距离公式的规律，而且直接切换到了另一个半叠内的牌了！接着一马平川，整个牌叠内的牌，都满足这个距离边两倍的规律了！

当然你可能还在怀疑，如果i在B叠，也就是那叠少的牌叠的时候，一样成立？当然成立，无非是切换牌叠的时候插入的是A叠的底牌罢了，或者我们转化为计算从j到i的距离，又是一样的问题了。

神奇的是，这件事竟然只在牌的张数为奇数的时候成立，而且in和out都没什么关系。而当牌的张数为偶数，看似一个更加对称的结构，却在切换牌叠的地方发生了切换处并没有等效的扑克牌插入，反而导致了这个距离公示并不成立。

说着还有点抽象，给你们看个图就全明白了：

图1 奇数张时候faro shuffle示意图

可以看到，图片顶部两张牌分别是多一张的那一叠的顶牌和底牌，洗完以后相邻了。但是，正是它们的存在，使得在跨过这个牌叠的时候，每过一张插入一张的规律依旧成立。

图2 偶数张 faro shuffle示意图

可以看到，偶数张的faro示意图的对称性更好，看起来更加内外相连。但实际上，如果真的按照两张两张走，会发现，其轮回会限定在同一个半叠内。也就是说，某叠的最底下一张的下两张是自己这叠的下一张，跨不到另外一叠去。如果要跨过去，这个2倍的距离关系，也就被破坏了。

不知道大家在看到上面图的时候，有没有想起莫比乌斯带。奇数张的情况恰好对应于M1扭了180度的带子，沿着它剪开以后，还能是一个完整的环。而偶数的时候就是M0的没有扭的带子，剪开了，就完全分离了。

当我在脑海里想清楚这一切的时候，觉得数学真美。

（反）完美洗牌第三定理

有同学可能有疑问，这里距离加倍以后，逐渐超出了排列的长度怎么办？其实，这里我们这里的距离，是一个在环上，或者说在循环群上的有向距离，其值实在整数modn加法群上的，因此，不必担心这个问题。

于是，我们有如下定理：

完美洗牌第三定理

对一个m张牌的牌叠0:(n - 1)，n为奇数，进行一次Faro Shuffle后D2 = FaroShuffle(D)，那么，对任初始位置和牌值0 <= v1, v2 <= n - 1，v1.c.j – v2.c.j == 2(v1 - v2)(mod m)。

反完美洗牌第三定理

对一个m张牌的牌叠0:(n - 1)，n为奇数，进行一次Faro Shuffle后D2 = FaroShuffle(D)，那么，对任初始位置和牌值0 <= v1, v2 <= n - 1，2(v1.c.j – v2.c.j) == v1 - v2(mod m)。

这里反完美洗牌的规律和正的对应性是体现比较明显，不像第一定理中完全看不出，而第二定理直接就对称相同了。

注意，v1.c.j – v2.c.j可以看作是两张值为v1和v2的牌的新距离（我们又是以牌张的位置而非排列结果的位置上的牌张为视角来方便描述的，这已经成为一种默认的方式了），而旧的距离即为v1 - v2，由他们的值代表的原索引值算出。注意这里的距离是有向，本质上是个1维的向量。faro shuffle下，距离加倍，anti faro则减半。而且这里的乘积运算和除法运算都是在mod张数m下的，并不是一般的算术乘法和除法，这样才能保证算出来的距离有意义，也符合我们模型里循环群结构的设定。

于是，由此我们就可以更好地理解完美洗牌第二定理的内容了。我们可以一直把一张牌的位置看作是与第0张的距离，因为out faro shuffle时第0张位置不变，那么奇数的情况就是显然的了，in时把索引倒过来即可。如果是偶数2N张，这里有一个特别巧妙的转化，即当用的是out faro shuffle，那么相当于是一次去掉底牌2N - 1，剩下的奇数张2N - 1的out faro shuffle，于是底牌永远不变，可以看作是out faro shuffle的不变量（顶牌也是），然后剩下的牌遵循奇数张的规律；如果是in faro shuffle，可以等效为一个增加一张底牌到2N + 1张牌的 in faro shuffle，同理满足条件。这个等效方法完美洗牌第二定理的在偶数张的公式里已经体现出来并分析过了。

注意两张牌之间的距离对于切牌操作来说是常量，因此奇数张的完美洗牌经常和切牌混合使用，切牌作为性质保持操作（这甚至成为所谓周期性能在切牌下保持的根本结构原因，其上mod相等的关系不变，因此其等价类对应商集也是常量而使得其上的集合性质成立，比如4个Ace，同花顺等等，千万不要把排列抽象性质和牌值混淆，二者只是刚好有时候关联相同罢了），甚至偶数张的时候给定条件也可以使用，我们会在后面的魔术里聊到。

好了，以上就是完美洗牌第三定理的内容，下一篇我们会介绍一些变体的完美洗牌操作和性质，敬请期待！

精彩抢先看！

视频1 数学collector奇迹

视频2 （milk shuffle）位置巧合

视频3 方块8的预言

视频4 天天四条龙

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

扫描二维码
关注更多精彩

完美洗牌的秘密（三）——（反）完美洗牌第二定理续
易拉罐的奇迹（二）——《易拉罐平衡》与《气体转移》
2024阿里巴巴全球数学竞赛决赛中的数列题解析（分析与方程方向第4题）
CATO原理中的数学与魔术（十四）——流程设计思路与升华
魔术里的交代与暗交代（三）——暗交代是怎么做的？

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

http://mp.weixin.qq.com/s?__biz=MzI2NjQwNzQxMQ==&mid=2247491558&idx=1&sn=ca735a37aa387fcedb1afc868adfc494

MatheMagician

当数学遇上魔术，当理性遇上感性，不仅可以在艺术的殿堂里擦出火花，展现魅力；也能在科学的世界里无所不能，摧城拔寨。马上，就是实现梦想的瞬间。

万圣节cos最像幽灵的竟然是他？！

完美洗牌的秘密（十三）——（反）完美洗牌第二定理的应用（16张的Anti faro周期魔术）

科幻电影中的全息空间影像在现实中快实现了吗？

完美洗牌的秘密（十二）——反完美洗牌定理的应用扩展（三叠发牌巴格拉斯效果）

从《费曼讲义》中，我竟然读出了一部“玄幻”小说……

完美洗牌的秘密（十一）——反完美洗牌定理的应用五（茫茫人海魔术扩展版）

离大谱！居里夫人竟获得了诺贝尔文学奖？

完美洗牌的秘密（十）——反完美洗牌定理的应用四（16张茫茫人海魔术）

半年炫2篇SCI！研究生一定要试一下！SCI论文辅导真的太香！

听说抛个硬币就能拿10万亿奖金，今年搞笑诺贝尔奖花落谁家？

往期精彩20241005

完美洗牌的秘密（九）——反完美洗牌定理的应用三（anti faro shuffle的奇迹等）

调休哪有不疯的？！看物理系博士生如何带你绝地反击……

在国际学校当老师的一天——深圳爱文学校数学魔术授课和访校记录

从广义相对论到规范理论（下）

完美洗牌的秘密（八）——反完美洗牌定理的应用二（感应奇迹）

被朋友拉去听演唱会，可注意力全程被手里这个东西吸引

完美洗牌的秘密（七）——反完美洗牌定理的应用一（指引巴格拉斯效果）

近视眼的人年纪大了后会老花眼吗？

完美洗牌的秘密（六）——完美洗牌定理的应用（penehole's principle magic more等）

从《黑神话：悟空》爆火，看游戏史的第一话

完美洗牌的秘密（五）——完美洗牌的性质和变体

完蛋！我们在实验室里做出了“毒液”

完美洗牌的秘密（四）——（反）完美洗牌第三定理

科学吃瓜—“紫薯”、兴奋剂都是怎么回事儿？

完美洗牌的秘密（三）——（反）完美洗牌第二定理续

外国人念不对中国运动员的名字？科学的解释来了

完美洗牌的秘密（二）——完美洗牌第二定理

“莎头”组合夺冠，他们在赛场上的这个动作，你注意到了吗？

完美洗牌的秘密（一）——（反）完美洗牌定理

我们首次在月壤中发现了水！大家准备种点什么菜?

记2024深圳暑期吴如皓魔术数学研修班活动

从广义相对论到规范理论（中）

易拉罐的奇迹（二）——《易拉罐平衡》与《气体转移》

毕业季，我们的学位服是怎样发展而来的？

易拉罐的奇迹（一）——硬币入可乐

夏天到了，究竟怎样才能越吃越瘦？

2024阿里巴巴全球数学竞赛决赛中的数列题解析（分析与方程方向第4题）

盘点那些年你学不会的物理

2023阿里巴巴全球数学竞赛决赛中的LLM背景题解析（应用与计算数学部分第2题）

从广义相对论到规范理论（上）

CATO原理中的数学与魔术（十四）——流程设计思路与升华

期末复习不完了？助你成为时间管理大师！

CATO原理中的数学与魔术（十三）——综合应用

2024高考数学压轴题解析——数学 VS AI最后的倔强

为啥高考完，学了三年的东西立马忘干净了？

CATO原理中的数学与魔术（十二）——CATO与MAT principle

当练就火眼金睛，看到了一颗原子

CATO原理中的数学与魔术（十一）——Parity Principle及其应用二：集合的可视化

分类

时事

民生

政务

教育

文化

科技

财富

体娱

健康

情感

旅行

百科

职场

楼市

企业

乐活

学术

汽车

时尚

创业

美食

幽默

美体

文摘

原创标签

时事社会财经军事教育体育科技汽车科学房产搞笑综艺明星音乐动漫游戏时尚健康旅游美食生活摄影宠物职场育儿情感小说曲艺文化历史三农文学娱乐电影视频图片新闻宗教电视剧纪录片广告创意壁纸头像心灵鸡汤星座命理教育培训艺术文化金融财经健康医疗美妆时尚餐饮美食母婴育儿社会新闻工业农业时事政治星座占卜幽默笑话独立短篇连载作品文化历史科技互联网

发布位置

广东北京山东江苏河南浙江山西福建河北上海四川陕西湖南安徽湖北内蒙古江西云南广西甘肃辽宁黑龙江贵州新疆重庆吉林天津海南青海宁夏西藏香港澳门台湾美国加拿大澳大利亚日本新加坡英国西班牙新西兰韩国泰国法国德国意大利缅甸菲律宾马来西亚越南荷兰柬埔寨俄罗斯巴西智利卢森堡芬兰瑞典比利时瑞士土耳其斐济挪威朝鲜尼日利亚阿根廷匈牙利爱尔兰印度老挝葡萄牙乌克兰印度尼西亚哈萨克斯坦塔吉克斯坦希腊南非蒙古奥地利肯尼亚加纳丹麦津巴布韦埃及坦桑尼亚捷克阿联酋安哥拉