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% 地通过游戏,获得释放。

45 条评论

  • sybaboooon

    SF啊

  • yangff

    没看懂= =

  • leafye19950115

    真的看不懂

  • heyjo

    有道理
    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)
    好多国人解答…

  • wuzhengkai

    精彩!

  • naeioi

    cnphil的一篇文章:http://www.cnphil.com/archives/293

  • 为什么

    好像matrix解释有点问题

    似乎是先乱序排列,戴手套,后按实数大小排列,最后握手

  • coffey

    不懂,真的不懂。
    其他囚犯难道不能告诉某个囚犯他额头上的数字吗?这样奇偶数字带相反的手套不就行了?

  • bili

    这囚犯得是数学家吧

  • cgy4ever

    哇,原来答案真的是100%啊。
    这道题我想了好几天也没有想出来,真是太精彩了!

  • DarkRaven

    我去,我也是这个方法,发过去被驳回了

  • DarkRaven

    。。。。我错了,不一样….
    好像我条件看错了

  • DarkRaven

    也就是说不能看见别人是怎么戴手套的?
    我杯具啊。

  • DarkRaven

    我是这样的,以1号为指向标,他戴手套方法反映了他看到的逆序对的奇偶性,然后其他囚犯按他们自己看到的,除了1号以外囚犯的逆序对的奇偶性和1号所反映的奇偶性对比结果来戴手套。
    现在想想,增加一个假想的负无穷囚犯就可以按我的方法解决这个问题

  • vgcookie

    漂亮!

  • 武昌鱼

    我居然看懂了,以前有个台湾的学校老师说魔方说过这个算法的。真没想到不仅仅可以用于魔方,还可以用于这个。

  • dofine

    好像是我们线代上刚刚开始讲的逆序数的概念哇。。

  • biohu

    勉强算是看懂了吧。。。
    线性代数没白学

  • cat.s

    82最近很勤劳嘛

  • lyx15937

    看得蛋疼……
    觉得自己是一头不懂数学的牛……

  • my dear

    先让一个囚犯帮忙按从小到大的顺序排N-1个囚犯。在从排好的N-1个囚犯里选择编号最大(或最小)的囚犯并且先前帮助排序的囚犯入队,让第一次序号最大或者最小的囚犯帮助排N-1。如果第一次帮排序的囚犯不在队尾或者队首则排序成功。否则在任意挑选一个人出来帮助排列先前最大号(最小号)与第一次帮助排列的那人的位置,此时排列结束。再按照A,B策略即可~

  • hayate

    逆序对啊,有意思~

  • BenMQ

    乱入……囚犯都很可怜……

  • shanq

    叙述的好混乱啊,看的头疼

  • Firm

    这个有看过,俺那天也算了好久

  • easing

    22楼的,说好囚犯之间不能交流的,你还让人家帮忙排队。。。
    这道题还是挺强的,不过M67没说不能看别人怎么戴手套啊。

  • cgy4ever

    期待看到这个月的题目的解答……
    想了半个月也没想出来呢。

  • ljhljh235

    挺巧妙的,但是对囚犯的要求很高啊

  • 幻兰洚

    没看懂证明。。自己尝试的证明了一下~
    方案为:
    将囚犯编号如下
    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类似可证明。

  • zodiac1111

    我揉脸我揉脸 我什么都不带,策略三 双手都是透明的手套. 我开外挂来了~

  • amorphobia

    精妙的证法, 我该复习线代去了.

  • sharkmao

    囚犯们的策略是,数一数自己看到的序列中有多少逆序对,如果逆序对的个数与他自己的编号同奇偶,则回答字母 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囚犯是相邻的,似乎出现矛盾了

  • orbea jersey

    蛮精妙的,喜欢这类型的人!

  • 马戏班经理

    个人觉得原文给出的证明更巧妙一点,
    首先根据囚犯的名字将囚犯排序,这是事先就已经做好的,这样每个囚犯就对应序数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位囚犯的策略相反。

  • Revin

    数论啥的…完全不会啊…见过好多逆序对的问题,完全搞不懂啊~[/掀桌]
    不过我倒是想到一个类似的问题,不知有人看到过没有,描述如下:
    有100个囚犯,有一个暗室内有100个暗盒,每个暗盒内分别有一个从0~99(including)不重复整数
    游戏开始后,犯人不可以相互交流,然后犯人会被分配0~99的不重复编号,然后每个犯人单独进入暗室,可以打开他/她选的至多50个盒子,如果所有犯人都在他/她在盒子内找到他/她自己的编号,则所有犯人可获释.
    是否有一个概率超过50%的解(我没记错的话有)?
    犯人都有完美记忆力啥的这些条件都具备,如果没看过这个问题能解出来是大神哦~
    常见错误解就不要说了,比如每个人都随机,这个概率不是50%,是0%(2^-100),等

    • Revin

      点击回复给我自己,居然会刷新页面…嗯,用惯了ajax,js的我果然很不习惯…
      另外其实我本来是想说,评论居然不需要审核…嗯,突然呼吸到了自由的空气.
      这两天突然又能上去youtube了,学到了好多,心情好,废话比较多…
      捉摸着什么时候也建个博客呢…苦于没有稳定的服务器啊,抠门的我舍不得花钱租=..=

  • uu打码

    柔情似水,佳期如梦,忍顾鹊桥归路。

  • wuxx

    认真看了第二遍居然看懂了。。。看懂以后真有种卧槽这都可以的感觉

发表评论