趣题：用 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 上看到的。

46 条评论

发表评论




Enter Captcha Here :