约瑟夫问题与魔术（一）——数学模型求解

约瑟夫问题，相信对有一点数学或者信息学竞赛背景的同学应该都不会很陌生，这是数学竞赛中常见的一个考题背景以及数据结构中用循环链表建模的一个代表性应用。而我懵懂地第一次接触到它居然是在一个魔术流程里，那是我小学时候的事了。而当我很多年以后再在数学和计算机的书上看到它时，竟然有一种从心头涌动的兴奋。于是，我决定从多个视角来回顾一番，并从数学模型，数据结构，数学推导，以及用到这个原理的若干魔术几个角度，来共同探讨这一古老又迷人的议题。

问题定义和历史沿革

约瑟夫斯问题（有时也称为约瑟夫斯置换，但严格来讲这并不是一个集合到自身的映射，所以不是置换，需要推广到集合的序列到集合的序列的映射才行。），是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。

问题描述：

人们站在一个等待被处决的圈子里。计数从圆圈中的指定点开始，并沿指定方向围绕圆圈进行。在跳过指定数量的人之后，执行下一个人。对剩下的人重复该过程，从下一个人开始，朝同一方向跳过相同数量的人，然后执行，直到只剩下一个人，并被释放。

问题：给定人数、起点、方向和要跳过的数字，选择初始圆圈中的位置以避免被处决。

大家一定很好奇这个问题名字的由来。这个问题是以弗拉维奥·约瑟夫命名的，他是1世纪的一名犹太历史学家。他在自己的日记中写道，他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘，最终决定自杀，并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人，他们将向罗马军队投降，不再自杀。约瑟夫斯把他的存活归因于运气或天意，他不知道是哪一个。

哈哈，这么个数学味浓厚的问题居然是个历史学家发明了，真是有趣。

数学模型

我们需要对实际对象用数学结构来描述，进而翻译在这个对象上做的实际操作为某种数学操作，进而在数学框架下完成整个模型推导。这里天然地，站成一圈的人们这整个对象可以建模成一个环（cycle）的结构。即一个仅首尾顶点相同的回（curcuit）。若首位不封闭相连，那就直接是一个全序关系的链（chain）。每一次的行动，相当于在这个环上逐个遍历下一个元素，并对操作序数能整除某值的元素进行删除（整除的值恰好比跳过数量大1），生成一个新的环，直到此环称为一个只有一个元素的自环（loop）。如果把这个过程看作一个元素的遍历，也就相当于求这个遍历过程遍历的最后一个元素。

下面用m表示跳过人数，n表示初始总人数。则整个环结构表达为一个二元关系：

S1 = ({(a_i(mod n), a_(i + 1)(mod n)) | i in 0:(n - 1)})

另外需要记录的两个状态是按照mod(m + 1)每次递增1的计数器c，还有一个是初始的考察元素p，初始状态为：

Q1 = (S1, c1, p1)，其中c1 = 0，p1 = a_0.

当走到第k次行动的时候，得到状态Q(k + 1)的结果：

Q(k + 1) = (S_k - {a_(pk)} if c_(k + 1) = k(mod(m + 1)) == m else S_k, k(mod(m + 1)), next(S_k))

其中，S_k - {a_(pk)}表示原环结构删除对应元素，并重新拼接该元素前后元素的结果，不是普通的集合相减，是规定了对应结构变化方式的，有点像序列去掉子序列重新拼接的只去掉一个长度为1的子序列的最简单特例。

以上就是对我们观察对象以及在其上做的操作的数学模型了，接下来，我们加上数据结构，形成完整的算法。

数据结构

从数学结构到代码还差一步，即用什么样的数据结构来表达我们的研究对象，能够使得仅能表达全序关系序列和地址映射的计算机来模拟我们的数学结构。计算机并不懂什么环，但是存其数学结构还是有办法的。因为环的本质是个特殊的二元关系罢了，计算机上的最基本的地址到值的映射就能够模拟这个关系。这里，把明明直观的一圈人变成一个抽象的二元关系集合，虽然破坏了其完整，可理解的性质，但是却是最本质的，没有遗漏什么信息，也没有多存什么，一切刚刚好。

具体到这个问题，因为我们不太需要对环上元素进行像数组那样的随机下标访问，而比较看重“下一个”这个环上的核心关系，中间还涉及很多删除元素，也就是修改这个映射的操作。下一个这个映射，恰好就用一个结构体上存的下一个元素的地址来代表就可以了，也即我们把大脑里抽象出来的“下一个”这个映射，具体化为了，从某标识符指向的结构体上找到存的地址，再取这个地址的元素这一计算机给我们提供的编程接口。另外，因为是环，不是一般的序列，最后一个元素要存上第一个元素的地址。此时，整个数学模型就存储在了这样的数据结构上，自此以后，我们只需要列出公式，计算机就能够帮我们模拟计算，得到我们想要的答案。当然，这里的这个结构，叫循环单链表。

当然，也可以用普通数组来表达序列，再辅助一个取余数操作，就可以得到循环数组的数据结构来表达这个环的模型了。能这么做的根本原因是，取余数的加法对应着循环群的基本生成操作，和前面构造的首尾相接的链表是一个结构，都是循环群。只不过，这里的下一个映射，是附着在内存本身这个线性序列上的，我们用数值的加法接口来求下一个元素，依赖于内存序列本身，而不是临时构造。这样其实可以省不少空间，比如存地址的空间就不需要了。但可惜的是，这个内存序列的索引早就写死了，不能够随便增改删，不然复杂度会很高，自然也就不是适合我们这个场景的数据结构了。

相关代码可以后台联系我获取。

模型应用

在数学模型的层面，我们抽象出环（也叫圈，cycle）这样一个数学结构，并且可以在很多表面上看起来完全不同的场合找到背后统一的数学结构。比如一群小伙伴围成一圈，玩丢手绢，击鼓传花，或者夺命狼人杀之类的游戏，当然也可以直接在上面用约瑟夫过程选人上台唱歌等等。

当然，在魔术里，我们应用的重点自然是扑克牌叠了。扑克牌叠按理来说并不是环，是个首尾不相接的序列，但是我们可以人为地认为底牌和顶牌的关系和任意牌叠里两张相邻的上下牌一样，也算一种特殊的相邻。这样看待有个好处，就是可以用研究环的方式来研究扑克牌了，这种看待方式只要没有和原结构矛盾，有时有着意想不到的效果。如是，拿起扑克牌叠，每次切下去若干张，再扔掉一张，最后只剩下一张，那么整个过程的结构就和约瑟夫过程是一模一样的。不过扑克牌这种循环链表，还要实时去维护一个头指针，以指向牌叠顶端，还保留一下这层牌叠顶部张的索引的信息，以免需要的时候找不回来。实际上，如果从序列角度看，把一次执行理解为一轮序列遍历，那么在扑克牌叠序列上执行约瑟夫问题，就会多出一点这叠牌的序列是如何变化，以及移除的牌叠会如何重新排列的过程，这个我们日后还会给出相应模型来描述。

这个过程在扑克牌的术语里面还专门有个名字，叫down and under deal，也叫the Australian deal，实际上就是每次跳过1张，且第一次直接剔除错位了一个相位的约瑟夫过程。

整体来看，扑克牌上的约瑟夫问题，其实也是一系列切牌，完成切牌动作的组合，并没有什么新意，完全可以用扩展的置换群上的运算来描述。但是这个问题由于其处理过程的周期性，很特殊，使得其结构暗含在其他数学描述中，虽然不如置换群通用，但是有更表达此过程本质的数学结构。因此，我们在文章中会着重介绍这样处理的过程意味着怎样的数学规律。还有，利用这一过程看似的不可预见性和混乱性，引入魔术中，和其他效果配合一起，去完成不可思议的效果。