上个月的 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% 地通过游戏，获得释放。
SF啊
没看懂= =
真的看不懂
有道理
Sen Gu (8 September 21:38)
Lewei Weng (9 September 12:03)
Phil Hu (14 September 01:39)
GuangDa HuZhang (14 September 17:18)
Hongcheng Zhu (18 September 18:10)
Song Lin (21 September 12:55)
好多国人解答…
精彩!
cnphil的一篇文章：http://www.cnphil.com/archives/293
好像matrix解释有点问题
似乎是先乱序排列，戴手套，后按实数大小排列，最后握手
不懂，真的不懂。
其他囚犯难道不能告诉某个囚犯他额头上的数字吗？这样奇偶数字带相反的手套不就行了？
这囚犯得是数学家吧
哇，原来答案真的是100%啊。
这道题我想了好几天也没有想出来，真是太精彩了！
我去，我也是这个方法，发过去被驳回了
。。。。我错了，不一样….
好像我条件看错了
也就是说不能看见别人是怎么戴手套的？
我杯具啊。
我是这样的，以1号为指向标，他戴手套方法反映了他看到的逆序对的奇偶性，然后其他囚犯按他们自己看到的，除了1号以外囚犯的逆序对的奇偶性和1号所反映的奇偶性对比结果来戴手套。
现在想想，增加一个假想的负无穷囚犯就可以按我的方法解决这个问题
漂亮！
我居然看懂了，以前有个台湾的学校老师说魔方说过这个算法的。真没想到不仅仅可以用于魔方，还可以用于这个。
好像是我们线代上刚刚开始讲的逆序数的概念哇。。
勉强算是看懂了吧。。。
线性代数没白学
82最近很勤劳嘛
看得蛋疼……
觉得自己是一头不懂数学的牛……
先让一个囚犯帮忙按从小到大的顺序排N-1个囚犯。在从排好的N-1个囚犯里选择编号最大（或最小）的囚犯并且先前帮助排序的囚犯入队，让第一次序号最大或者最小的囚犯帮助排N-1。如果第一次帮排序的囚犯不在队尾或者队首则排序成功。否则在任意挑选一个人出来帮助排列先前最大号（最小号）与第一次帮助排列的那人的位置，此时排列结束。再按照A,B策略即可~
逆序对啊，有意思~
乱入……囚犯都很可怜……
叙述的好混乱啊，看的头疼
这个有看过，俺那天也算了好久
呃
22楼的，说好囚犯之间不能交流的，你还让人家帮忙排队。。。
这道题还是挺强的，不过M67没说不能看别人怎么戴手套啊。
期待看到这个月的题目的解答……
想了半个月也没想出来呢。
挺巧妙的，但是对囚犯的要求很高啊
没看懂证明。。自己尝试的证明了一下～
方案为：
将囚犯编号如下
1，2，…，n，n+1，…，100
打乱编号之后
除却自身看到的逆序对与自身序号的奇偶性一致，左黑右白
除却自身看到的逆序对与自身序号的奇偶性不一致，左白右黑
证明：
不失一般性，设打乱后数列如下：
…，n，…，n+1，…
X：：：Y：：：：Z (X，Y，Z分别指代上面的省略号范围)
1.假设在X和Z中，共（x+z）个数与n构成逆序对，那么这些数与n+1也构成了逆序对
2.假设在Y范围中的数共有y个，则这y个数要么与n构成逆序对，要么与n+1构成逆序对
3.假设与n，n+1都无关的逆序对共有l对。
则依据以上三个假设有：
1.当n除却自身看到的逆序对为奇数，n+1除却自身看到的逆序对为奇数，则有
两者看到的逆序对之和为2（x+z）+2l+y=偶数
即y为偶数，即混乱后的n和n+1间隔偶数个数，所以二者应该不同的方案，而n和n+1奇偶性不同，满足方案
2.当n除却自身看到的逆序对为偶数，n+1除却自身看到的逆序对为奇数
3.当n除却自身看到的逆序对为奇数，n+1除却自身看到的逆序对为偶数
4.当n除却自身看到的逆序对为偶数，n+1除却自身看到的逆序对为偶数
2，3，4类似可证明。
我揉脸我揉脸 我什么都不带,策略三 双手都是透明的手套. 我开外挂来了~
精妙的证法, 我该复习线代去了.
囚犯们的策略是，数一数自己看到的序列中有多少逆序对，如果逆序对的个数与他自己的编号同奇偶，则回答字母 A ，否则回答字母 B
假设囚犯排列如下：1,2,3,4,8,6,7,5,9,10
编号为4的囚犯看到的逆序对(8,6),(8,7),(8,5),(6,5),(7,5)为奇数，选择B
编号为5的囚犯看到的逆序对(8,6),(8,7)为偶数，选择B
4,5囚犯是相邻的，似乎出现矛盾了
蛮精妙的，喜欢这类型的人！
这个有看过
个人觉得原文给出的证明更巧妙一点，
首先根据囚犯的名字将囚犯排序，这是事先就已经做好的，这样每个囚犯就对应序数1-100中的某一个数字，设根据额头上的数字对囚犯排序后得到的序列为a1,a2,…,a100，ai表示第i位囚犯所对应的序数，而他所需要采取的策略就是计算序列Πi:ai,a1,a2,…,ai-1,ai+1,…,a100的逆序数t(Πi)，对于第i+1位所需要采取的策略就是计算序列Πi+1:ai+1,a1,a2,…,ai,ai+2,…,a100的逆序数t(Πi+1)，很容易证明序列t(Πi)与t(Πi+1)不同奇偶，从而保证采用的策略也不相同。
为了证明M大牛的方案，需要在此基础上另外说明一个序列的两个子序列之间的关系。
首先Π’i:a1,a2,…,ai-1,ai+1,…,a100的逆序数等于t(Πi)+(ai)-1，而Π’i+1:a1,a2,…,ai,ai+2,…,a100的逆序数等于t(Πi+1)+(ai+1)-1，M大牛的方案要求第i位囚犯根据Π’i+ai的值来决定自己的策略（即t(Πi)+2(ai)-1），而第i+1位囚犯的值为t(Πi+1)+2(ai+1)-1，显然也能够保证与第i位囚犯的策略相反。
首先根据囚犯的名字将囚犯排序，这是事先就已经做好的，这样每个囚犯就对应序数1-100中的某一个数字，设根据额头上的数字对囚犯排序后得到的序列为a1,a2,…,a100，ai表示第i位囚犯所对应的序数，而他所需要采取的策略就是计算序列Πi:ai,a1,a2,…,ai-1,ai+1,…,a100的逆序数t(Πi)，对于第i+1位所需要采取的策略就是计算序列Πi+1:ai+1,a1,a2,…,ai,ai+2,…,a100的逆序数t(Πi+1)，很容易证明序列t(Πi)与t(Πi+1)不同奇偶，从而保证采用的策略也不相同。
为了证明M大牛的方案，需要在此基础上另外说明一个序列的两个子序列之间的关系。
首先Π’i:a1,a2,…,ai-1,ai+1,…,a100的逆序数等于t(Πi)+(ai)-1，而Π’i+1:a1,a2,…,ai,ai+2,…,a100的逆序数等于t(Πi+1)+(ai+1)-1，M大牛的方案要求第i位囚犯根据Π’i+ai的值来决定自己的策略（即t(Πi)+2(ai)-1），而第i+1位囚犯的值为t(Πi+1)+2(ai+1)-1，显然也能够保证与第i位囚犯的策略相反。
数论啥的…完全不会啊…见过好多逆序对的问题,完全搞不懂啊~[/掀桌]
不过我倒是想到一个类似的问题,不知有人看到过没有,描述如下:
有100个囚犯,有一个暗室内有100个暗盒,每个暗盒内分别有一个从0~99(including)不重复整数
游戏开始后,犯人不可以相互交流,然后犯人会被分配0~99的不重复编号,然后每个犯人单独进入暗室,可以打开他/她选的至多50个盒子,如果所有犯人都在他/她在盒子内找到他/她自己的编号,则所有犯人可获释.
是否有一个概率超过50%的解(我没记错的话有)?
犯人都有完美记忆力啥的这些条件都具备,如果没看过这个问题能解出来是大神哦~
常见错误解就不要说了,比如每个人都随机,这个概率不是50%,是0%(2^-100),等
点击回复给我自己,居然会刷新页面…嗯,用惯了ajax,js的我果然很不习惯…
另外其实我本来是想说,评论居然不需要审核…嗯,突然呼吸到了自由的空气.
这两天突然又能上去youtube了,学到了好多,心情好,废话比较多…
捉摸着什么时候也建个博客呢…苦于没有稳定的服务器啊,抠门的我舍不得花钱租=..=
31.18%
柔情似水，佳期如梦，忍顾鹊桥归路。
认真看了第二遍居然看懂了。。。看懂以后真有种卧槽这都可以的感觉
牛逼啊