上个月的 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%
柔情似水，佳期如梦，忍顾鹊桥归路。
认真看了第二遍居然看懂了。。。看懂以后真有种卧槽这都可以的感觉
牛逼啊
Hello everyone, it’s my first visit at this site, and paragraph is genuinely fruitful in favor of me,
keep up posting these types of content.
Here is my web page; vpn special coupon