趣题:用 26 次机会找出任意一张对方想要的牌

看守打算和 A 、 B 两名囚犯做一个游戏。首先,看守从一副牌中取出大小王,将剩余的 52 张牌洗好,并在桌子上从左至右地把它们摆成一排,每张牌都是正面朝上。然后,看守让囚犯 A 来到桌前,允许囚犯 A 观察牌面,并交换其中两张牌的位置。接着,看守将囚犯 A 关回牢房,把所有牌全都翻到背面朝上(但位置不变),让囚犯 B 来到桌前。看守随便报出一张牌的花色和点数(比如“梅花 3”),要求囚犯 B 找出这张牌。囚犯 B 每次可以翻开任意一张尚未翻开的牌,但一共只有 26 次机会。如果囚犯 B 在这 26 次机会之内找到了看守想要的牌,则两名囚犯赢得游戏,无罪释放;如果囚犯 B 翻开了 26 张牌之后,还没找到看守想要的牌,则两名囚犯输掉游戏,立即死刑。在整个游戏开始之前,两名囚犯可以商量一个策略;游戏开始后,两人就不能有任何其他形式的交流。果不其然,这又是一个关满了数学天才的监狱。两名囚犯碰头后,很快就商量出了一种必胜的策略。这种必胜的策略是什么?

 

 

 

 

 

 

 

两名囚犯可以约定一种用 1 到 52 给扑克牌进行编号的方案。于是,桌上的扑克牌就相当于是写有 1 到 52 的卡片形成的一个排列了。假设现在所有的牌都是背面朝上的。想一想,如果你翻开某张牌,看看牌上写的是几,然后就去翻左起第几张牌,并不断地这样做下去,最后的结果是什么?最后的结果是,你迟早会回到出发点。假如你翻开了左起第 5 张牌,牌上写的是 34 ;你又翻开了左起第 34 张牌,结果牌上写的是 18 ;你又翻开了左起第 18 张牌,结果牌上写的是 13 ……总有一个时候,你会翻到一张写着 5 的牌,于是你就回到了出发点,得到了一个“圈”。这个圈并不一定涵盖了桌上的所有牌,换句话说,这个圈的长度并不一定是 52 。那么,再随便翻开一张尚未涉及到的牌,并不断根据牌上的信息翻开下一张牌,最终又会得到一个新的圈……也就是说,不管桌上的扑克牌是怎样排列的,它都可以被分解成若干个这样的圈。

所以,倘若看守想要的牌的编号是 15 ,那么囚犯 B 就可以翻开左起第 15 张牌,然后让牌上的数指引他继续往下翻牌。只要 15 所在的圈的长度小于等于 26 ,囚犯 B 就能在 26 步之内翻到写有 15 的牌,从而赢得游戏。而囚犯 A 的任务就是,想办法交换其中两张牌,让任何一张牌所在的圈的长度都不超过 26 。这确实是总能办到的。如果左起第 a1 张牌上写有 a2 ,左起第 a2 张牌上写有 a3 ,以此类推,一直到左起第 an 张牌上写有 a1 ,那么交换左起第 a1 张牌和左起第 ak 张牌,结果会怎么样呢?注意到,左起第 a1 张牌上现在写的就是 ak+1 了,左起第 ak 张牌上现在写的就是 a2 了。于是,这个长度为 n 的圈会被打断成长度分别为 n – k + 1 和 k – 1 的两个小圈:

  • 左起第 a1 张牌上写有 ak+1
  • 左起第 ak+1 张牌上写有 ak+2
  • …… ……
  • 左起第 an-1 张牌上写有 an
  • 左起第 an 张牌上写有 a1
  • 左起第 ak 张牌上写有 a2
  • 左起第 a2 张牌上写有 a3
  • …… ……
  • 左起第 ak-2 张牌上写有 ak-1
  • 左起第 ak-1 张牌上写有 ak

1 到 52 的排列中,长度超过 26 的圈最多只能有 1 个。适当选择 k 的值,便能把它变成两个长度均小于等于 26 的小圈。这样,囚犯 B 便能保证在 26 次之内找到看守想要的牌,两人也就必胜了。

这个题目是我在 reddit 上看到的。

发表评论

  +  87  =  91