题意
看守打算和 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。
注意到编号为 $x$ 的牌一定会在位于左起第 $x$ 张牌所在的环中,因为编号为 $x$ 的牌指向了位置 $x$。
假设左起第 $x$ 张牌所在的环长度为 $l$,那么刚好往后找 $l - 1$ 次的牌就是 $x$,总共经过了 $l$ 张牌。
那么如果囚犯 A 可以把每个环的长度都控制在 26 以内,那么他们按照上述方法就一定可以找到。
而囚犯 A 有方法把每个环的长度都控制在 26 以内。
如果左起第 $a_1$ 张牌上写有 $a_2$,左起第 $a_2$ 张牌上写有 $a_3$,以此类推,一直到左起第 $a_n$ 张牌上写有 $a_1$,那么交换左起第 $a_1$ 张牌和左起第 $a_k$ 张牌,结果会怎么样呢?注意到,左起第 $a_1$ 张牌上现在写的就是 $a_{k + 1}$ 了,左起第 $a_k$ 张牌上现在写的就是 $a_2$ 了。于是,这个长度为 $n$ 的圈会被打断成长度分别为 $n - k + 1$ 和 $k - 1$ 的两个小圈。
1 到 52 的排列中,长度超过 26 的圈最多只能有 1 个。适当选择 k 的值,便能把它变成两个长度均小于等于 26 的小圈。