UyHiP趣题：100囚犯之黑白手套

上个月的 UyHiP 趣题非常妙，个人认为是近几个月里最漂亮的一道谜题了。

典狱长要和 100 个囚犯玩这么一个游戏。典狱长给每个囚犯发两个手套，一个黑色的，一个白色的。之后，每个囚犯的额头上都会写上一个实数，所有这 100 个实数互不相同。每个囚犯都能看到其他 99 个囚犯前额上所写的数，但不能看到自己的数。接下来，每个囚犯必须独立地决定把哪个手套戴在哪只手上。等到所有囚犯都戴好了手套，典狱长会把他们按照前额上所写的数从小到大地排好，并要求他们手牵着手站成一横排。如果每两只握在一起的手都戴着相同颜色的手套，那么所有 100 个囚犯都可以被释放。

在游戏开始前，他们可以聚在一起，商量一个对策。游戏开始后，囚犯与囚犯之间不允许有任何交流。囚犯们能够保证全部释放吗？

答案：真的有这么一个策略，使得囚犯们保证能被释放。为了便于叙述，我们换一种方式来描述这个游戏：囚犯们需要根据自己看到的情况，独立地在一张小纸条上写下字母 A 或 B （对应着“左黑右白”和“左白右黑”两种决策）；然后，把囚犯按前额的数从小到大排序，依次念出囚犯所写的字母，如果 A 和 B 自始至终一直交替出现，囚犯们就能被释放。

完美策略的存在性并不太令人吃惊。如果只有两个囚犯，显然有一个必胜的方案：只需要事先约定不管怎样都是你写 A 我写 B 就行了。如果有更多的囚犯，下面的策略可以保证他们获胜。

不妨把囚犯们从 1 到 n 进行编号（这个编号可以由囚犯们在游戏开始前约定好）。把囚犯们按额头上的数重新排序后，我们就得到了一个从 1 到 n 的排列。比方说有 8 个囚犯，他们额头上的数分别是：

囚犯编号：1    2    3    4    5    6    7    8

额上实数：0.1    0.4    0.6    0.2    0.8    1.1    0.5    1.5

那么重新排序后得到的排列是：

1, 4, 2, 7, 3, 5, 6, 8

但是，由于囚犯不知道自己额头上的数，因此每个囚犯只能“看见”这个排列除他之外剩下的部分。比方说，囚犯 2 就只能看到另外 7 个人形成的不完整排列：

1, 4, 7, 3, 5, 6, 8

如果在一个序列中，位于前面的某个数比位于后面的某个数更大，我们就说这两个数是一对“逆序对”。囚犯们的策略是，数一数自己看到的序列中有多少逆序对，如果逆序对的个数与他自己的编号同奇偶，则回答字母 A ，否则回答字母 B 。比方说，例子中囚犯 2 能看到的逆序对有 (4,3), (7,3), (7,5), (7,6) 共 4 个，自己的编号是 2 ，因此他将回答 A 。而囚犯 7 将看到序列

1, 4, 2, 3, 5, 6, 8

他只能看到 (4,2), (4,3) 两个逆序对，自己的编号却是奇数 7 ，因此他将回答 B 。你会发现，囚犯 2 和囚犯 7 这两个位置相邻的人恰好一个回答了 A 一个回答了 B 。这并不是一个巧合。我们将以这两个囚犯为例，说明位置相邻的囚犯看到的逆序对个数的奇偶性相同，当且仅当他们编号的奇偶性不同。

注意到，两个囚犯看到的序列都形如

1, 4, ?, 3, 5, 6, 8

其中问号处就是对方的编号。在此序列中，不含问号项的逆序对是囚犯 2 和囚犯 7 都能看见的。囚犯 2 能看见的额外的逆序对，一定是在数字 7 和别的数之间产生的；而囚犯 7 能看见的额外的逆序对，则是在数字 2 和别的数之间产生。注意到，对于所有小于 2 或者大于 7 的数 k ，不管 k 在序列中的什么位置， 2 和 k 、 7 和 k 要么都是逆序对，要么都不是逆序对；而对于序列中那些大小严格介于 2 和 7 之间的数 k ，要么 2 和 k 构成一对逆序对，要么 7 和 k 构成一对逆序对。也就是说，囚犯 2 和囚犯 7 看到的逆序对个数是否同奇偶，取决于位于 2 和 7 之间的数是否有偶数个，也就是取决于 2 和 7 是否不同奇偶。

类似地，我们可以说明，按照额上的实数排序后，相邻两个囚犯一定都写下了不同的字母。因此，他们能保证 100% 地通过游戏，获得释放。