牌堆「不动点」

这个魔术受启发于我的室友@Rachel [1] 某天晚上给我表演的一个纸牌魔术,后来我们发现这魔术背后的数学原理可以进一步推广,于是我们两人花了一晚上 py 推导出了通用公式,并想出了对应的流程。为了让读者(好吧其实没什么读者)没那么乏味,我先描述一下魔术的最终效果。

「不动点」效果

  • 准备:任意一副纸牌(最好没有重复的牌),不需要任何额外准备
  • 流程:(依然是常规的选牌&找牌)
    • 观众选牌

      表演者「这里有一副牌,你现在可以切出一些牌,大概 ⅓ 到 ½」
      观众切牌,表演者展示观众切出的这些牌,证明牌很乱没有重复的牌没有任何问题(剩余的牌已经没有用了可以扔掉)
      可以把牌交给观众进一步打乱,越乱越好
      观众把牌交还给表演者,表演者直接请观众任意选出一张牌
      请观众记住这张牌,不要给表演者看到牌面,然后将选中的牌放回牌堆中间

    • 表演者找牌

      「现在我把这些牌你一张、我一张地分发成两叠」边说边发牌
      发牌完毕「现在你选的牌既可能在你那一叠,也可能在我这一叠。我们来打个赌,如果牌在我这一叠,你请我吃顿饭 :) 」
      观众犹豫
      「作为魔术师,我这样是不是有点欺负你了哈哈。这样吧,我把我这一叠再分发一次(每次发牌都是一人一张地发,下同),这样你就拥有 ¾ 的牌,而你选的牌只有 ¼ 的概率在我这边」
      观众…
      「没关系,我们再继续这样发,给你更多的牌」边说边发,一直重复,直至表演者这边只剩一张牌,其余所有牌都在观众那边(这个过程中表演者讲的话大可自由发挥)
      「如果我这边这一张牌就是你选的牌,我只需要5秒钟的掌声好吧」
      接下来享受掌声吧哈哈哈

数学原理

细节

上面所描述的流程,基本是以观众的体验来写的,也就是说,刻意模糊了一些表演者需要操作的细节

  • 观众切的牌确实是随机、顺序混乱的,但表演者需要知道观众切出的牌的张数
    • 如果你牌性足够好,手一拿一放就可以知道一叠牌的张数,那自然是极好的,但请确保准确率是100%,不然还是考虑下面两种方法;
    • 如果有多个观众,你可以把牌分发给几个观众洗牌,分发时进行计数,时间宽裕,不容易出错,前提是你小学数学加法很好
    • 我表演时一般会在展牌证明这些牌很乱的时候,同时计数。因为要计数,所以展牌动作可能会不流畅,时间也会稍微有点长(尤其是数量20+的情形),观众可能会怀疑你在记牌之类的,没关系,数量确认后可以大方地把牌交给观众让其打乱,彻底打消他们的疑虑(其实我觉得上一条是各个情形下都比较好的解决方案,但我为什么没用过呢?因为第二条是写文章时刚想到的= =)
  • 观众选牌后,牌的放回位置不是原位也不是随机的,而需要表演者控制到某一确定位置。(观众os:我天呐人与人之间最基本的信任呢???)
    • 因为不是常规的控顶(Top Control)控底(Bottom Control),所以找时机做Pinky Break进行控牌是可行的,或者我比较喜欢直接展牌、选牌、放回一气呵成:

      比如牌堆共有18张牌,我想让观众随机选一张牌,然后放回到第8张。
      双手展牌(Spread),展牌同时注意数第8张牌的位置,观众抽出一张牌后,你的左右手会自然把牌分成两叠,你只需要根据情况调整一边的牌张数为7即可(观众注意力完全在他所选的牌上)。
      放回时仍然保持展牌时的动作,但实际上你已调整了左右手牌的数量,观众潜意识里会认为他把牌放回了原位(你不需要用语言强调「放回原处」之类的),将7张牌盖在上方合上整叠牌,观众的牌就被控在了第8张。

  • 每次发牌确实是一人一张,而且没有使用任何手法,要注意的是每次开始发牌时,请先给观众发第一张

关键的细节就是以上三条,至此大家应该明白了这个魔术对应的数学问题就是:

对于总数为$N$的一叠牌,每次只保留第偶数位的牌,并将留下的牌逆序,重新从1开始编号。
重复以上操作,直至只剩下最后一张牌。
求最后这张牌在最初牌堆中的位置。

  • 偶数位很好解释:因为你每次都先给观众发第一张牌,所以你这边留下牌的序号总是2, 4, 6, …
  • 逆序很关键,因为是发牌到桌面上,所以你先发出的牌会被后续的牌压在下面,而你下一次发牌还是会从最上面一张开始发,因此相当于逆序操作。

我首先想到的是写代码看输出找规律,于是:

1
2
3
4
5
6
7
def fixedCard(n):
deck = list(range(1, n+1));
while len(deck) != 1:
deck = deck[1:][::2];
deck.reverse();
return deck[0];

然后我惊喜地发现,当$N$从2变化至54时,结果竟然没什么肉眼可见的规律。。

其实奇偶讨论并不麻烦,可怕的是逆序,用数学语言不是很好描述。但是注意到如果逆序和取偶数位两个过程可以交换,那这次逆序和下一次逆序不就互相抵消了吗?我真是太TM机智了!!!

推导过程

这部分看不下去的观众可以随时直接跳到快速心算部分,包教包会

  1. 将这$N$张牌从$1$到$N$编号,毫无疑问,第一次操作后剩下的牌的序号是$2n\quad(n=1,2,3\cdots)$
  2. 第一次取完牌后我们还没有进行逆序操作,不妨把第一次操作的逆序与第二次取牌结合,会擦出 爱情的 火花:
    • 如果剩下的这些序号为$2n$的牌如果数量为奇数,那么逆序后再取偶数位的结果与直接取偶数位再逆序的结果是相同的!

      比如现在剩下的牌是2,4,6,8,10 共5张
      讲道理应该先逆序:10,8,6,4,2
      然后取偶数位:8,4
      但我们不讲道理直接取偶数位:4,8
      再逆序:8,4
      实际上很显然,奇数张牌,偶数位的牌正着数反着数都是偶数位

    • 而如果数量为偶数,也类似,只需要取奇数位再逆序

      比如现在剩下的牌是2,4,6,8,10,12 共6张
      讲道理应该先逆序:12,10,8,6,4,2
      然后取偶数位:10,6,2
      但我们不讲道理直接取奇数位:2,6,10
      再逆序:10,6,2

  3. 现在我们仿佛看到了一些规律,整个过程变成了:
    1. 第1次取牌直接取了偶数位;原本第1步的逆序并入第2步
    2. 第2次取牌根据当前剩余牌数量的奇偶性取奇数位或偶数位;原本第1步的逆序被交换至第2次取牌后,并和原本第2步的逆序相互抵消
    3. 第3次取牌直接取偶数位;逆序并入第4步
    4. $\cdots$
  4. 消除了逆序操作,现在我们需要确定每一步当前剩余牌数量的奇偶性,卧槽这不就是二进制表示吗哈哈哈哈哈哈(读者os:MDZZ)
    • 初中数学老师教过我们一种十进制转二进制的方法:不断地除以2取商取余数,而这个余数正是当前剩余牌数量奇偶性的标志:

      23(10)=10111(2)
      定义二进制右数第一位为最低位
      1,1,1,0,1分别表示了23,11,5,2,1的奇偶性
      即第1,2,3,4,5次取牌时当前剩余牌数量的奇偶性

  5. 把$N$的二进制表示记为$a_k$,$a_0$表示最低位。下面$n$的取值总是$n=1,2,3\cdots$

    第一次取牌后剩余序号为$2n$
    第二次取牌后剩余序号为$2(2n-(1-a_1))$ (把上一步的 $n$ 代换成 $2n-(1-a_1)$ ,即根据当前剩余牌的奇偶性取奇数位或偶数位)
    第三次取牌后剩余序号为$2(2*2n-(1-a_1))$

  6. 偶数次取牌和奇数次取牌时的代换表达式还是不同,为了方便推导,干脆全部写成$2n-(1-c_k)$的形式。注意这里$k$从0开始,即第一次取牌对应的是$c_0$。只需要保证$c_0,c_2,c_4\cdots$均为1即可。
  7. 于是在第$m+1$次取牌后,剩余序号为
    $$
    2*(2*(\cdots2*(2*n-(1-c_m))-(1-c_{m-1})\cdots)-(1-c_1))-(1-c_0) \\
    =2^{m+1}n + 2^m (c_m-1) + 2^{m-1}(c_{m-1}-1) + \cdots + 2^0 (c_0 - 1) \\
    = 2^{m+1}(n-1) + 1 + \sum_{i=0}^m 2^i c_i
    $$
  8. 最后一次取牌后只剩一张牌,即$n=1$,故最后一张牌序号为
    $$
    r = 1 + \sum_{i=0}^m 2^i c_i, \quad 1 \le r \le N
    $$
  9. 考虑数列$\{a_n\}$与$\{c_n\}$的关系:
    $$
    c_n =
    \left\{\begin{matrix}
    1, \quad n=2k\\
    a_n, \quad n=2k+1
    \end{matrix}\right. \quad k=0,1,2\cdots
    $$
    • 构造二进制数$B=\cdots01010101_{(2)}$(位数与$N$相同),则$N|B$(按位或)即可得到$\{c_n\}$对应的二进制数$C$。显然有$C\ge N$
    • 接下来证明$N$的二进制码位数为$m+2$,即$N= \sum_{i=0}^{m+1} 2^i a_i$,且$a_{m+1}=1$
    • 也就是证明对于$m+2$位的$N$,在第$m+1$次取牌后只剩下一张牌:
      • 最后一张牌序号$r=1 + \sum_{i=0}^m 2^i c_i \le 1 + \sum_{i=0}^m 2^i = 2^{m+1} \le N$,满足条件;
      • 假设还剩有第二张牌,即令$n=2$,则其序号为$r_2 = 2^{m+1} + 1 + \sum_{i=0}^m 2^i c_i$,因为$a_{m+1}=1$,因此$c_{m+1}=a_{m+1}=1$。故$r_2 = 1 + \sum_{i=0}^{m+1} 2^i c_i = 1 + C \ge 1 + N$,不在整副牌序号范围内,因此不存在剩余的第二张牌。
  10. 其实作为一道15分的数学题,你写到这里已经可以拿到14分了。之所以扣掉一分,是因为结果貌似不那么直接明了。尤其是对于表演者来说,在表演情境下,很难一边保持与观众的互动,一边完成这几步复杂的计算。

快速心算

恭喜你跳过了不知所云的(其实充满了逻辑的力量2333)上一章节,接下来教大家如何3秒内心算出上述结果。

先举个栗子,$N=22$,先按照上面解出的公式结果走一遍流程,看看有什么可以优化的:

$N=22_{(10)}=10110_{(2)}$
按位或$C=10110|10101=10111$
去掉$C$的最高位,加1,即$r=1+7=8$
没错,22张牌的不动点就是第8张,不服你可以自己试一下

把$C$记作$C=2^{m+1} + S$,$S$表示去掉最高位的部分,那么$r = C - 2^{m+1} + 1 = 2^{m+1} - (2^{m+1} - 1 - S)$

(敲黑板)注意$(2^{m+1} - 1 - S)$这一部分,这个表达式实际上是对$S$进行按位取反

所以现在$r = 2^{m+1} - \overline{S}$,第一项很容易确定,重点在于确定$\overline{S}$

(敲黑板×2)回顾$S$的生成过程:

  • 与$\cdots01010101$按位或,也就是把$S$的这些位(从最低位开始数的所有奇数位)强行置为1,对应到$\overline{S}$,这些位全部为0;
  • 其余位(从最低位开始数的偶数位),若$N$中该位为1,则$\overline{S}$该位为0;
  • 所以,$\overline{S}$中为1的位,只有$N$偶数位为0的情况。

干货

  1. 更直白一些,首先把$N$拆分成2的幂次之和

    比如 54 = 32 + 16 + 4 + 2
    此时 $2^{m+1} = 32$

  2. $\cdots01010101$对应的实际上是$1+4+16+\cdots$,这些项在$\overline{S}$都不会出现
  3. $N$拆分项中出现的项在$\overline{S}$也不会出现,当然$\overline{S}$是小于最大项32的
  4. 因此$\overline{S}$= 1+4+ 8 +16
  5. 所以$r=32-8=24$

更进一步,在纸牌情形下($N\le 54$),$\overline{S}$含有的项只可能有2和8哪个不出现就(用最大项)减哪个,哪里不会点哪里,so easy…

  • $52 = 32 + 16 + 4, r = 32 - 8 - 2 = 22$
  • $34 = 32 + 2, r = 32 - 8 = 24$
  • $26 = 16 + 8 + 2, r = 16 - 0 = 16$
  • $24 = 16 + 8, r = 16 - 2 = 14$
  • $14 = 8 + 4 + 2, r = 8 - 0 = 8$
  • $12 = 8 + 4, r = 8 - 2 = 6$

其他讨论

  • 为什么让观众切牌时提示切「大概 ⅓ 到 ½」?

    这样可以保证表演流程的紧凑性。太多的牌整个流程被发牌动作占据,观众容易失去耐心;太少的牌观众看到最终效果不会觉得特别震撼。

  • 如果每次发牌都先给自己发,结果如何?

    当然也是可行的,结果应该是:除了要减去自身的较小项,还需减去1,4,16。
    但我不建议表演这个流程,因为发牌过程中观众所选的牌会很快收敛到你的牌堆顶部,经常会有观众怀疑他所选的牌始终在牌堆顶,被拆穿会比较尴尬。尽管原理不像他们所想那么浅显。
    而先给观众发牌则不同,观众所选的牌至少也是在第2张。

  • 还有一种不需要控牌到牌堆中间的方案:

    控顶或者控底,每次发牌时根据当前所剩牌数目的奇偶性决定先给谁发,保证观众的牌始终在自己这边。
    缺点之一:发牌过程中也要保持运算,容易表现地不自然,易出错。
    缺点之二:同上,观众所选牌经常出现在牌堆顶部。
    优点:每次发牌的顺序都不一样,更有迷惑性。

更完这一篇文章。。。竟然发现自己如此啰嗦。。。。

[1] 他坚持要把Rachel作为他的英文名(因为谐音),尽管我告诉他这是个女名。。参看wiki Rachel