zzy 云，要把他的题解放到我的 Blog 上，于是这篇文章出现了。下面是原文。
https://www.zhihu.com/question/461028423
YZ云:刚才搬迁了
0x01 题意概述
一个 4 人囚徒困境的必胜策略？
今天从一位老教授那里得来一个趣味问题，挺有意思，转过来与更多年轻朋友一起讨论。
为增加节目效果，以下内容对老教授的原问题描述进行了改编和演义。
——————
芝士世界的蹄拦桥监狱内有四名熟练掌握信息经济学与博弈论的囚徒，分别别囚禁在编号为1至4的单间牢房里。某天上午，监狱长将他们集中并宣布：
今天起，每个月23日的北京时间23点，我将掷一次骰子，如果出现1至4中任何一个点数，就将你们当中对应房号中的人招呼出来放风一小时。如果出现5和6，当天就不给你们任何一个人放风。
在楼道入口处左右两侧各有一盏路灯，今天23点前，我去确定他们的开关状态，这个状态你们无法知道。此后，这两个开关只供你们四人使用，其他人绝不得再碰。总之，无论你们谁被放风回房时，都可以决定它们的开关状态，并用它们的开关状态传递信息。
如果有一天，你们当中的任何人向我断言「我们四人都放过风了」，如果他说对了，你们全部立即释放；如果他说错了就直接处死，剩下的三个人的无期徒刑改为两年有期徒刑。如果一直没有人断言，那就永远囚禁你们。
现在你们在此商量如何用灯的开关状态表示信息，保证总有一天能被某人得到正确的断言。你们现在有一小时的讨论时间，一小时后押回各自牢房，严格隔离。
——————
问：他们有全部出狱的必胜策略吗？若有，如何实现？（年轻人们果然飞快地解决了）
但如果存在欺骗的情况，囚徒们是否会选择欺骗他人然后获得自己的减刑呢？（原来设置的十年发现太远了，现在改成两年）囚徒有可能开始选择欺骗策略的减刑上限是多少年？
Beta版：若在开始前囚徒不能讨论，但监狱长在开始前告知了灯的初始状态，囚徒们又应该如何决策？
0x02 前置知识
0x03 分析问题
yz会帮我们解决的 （确信）
假设深通数学的人延年益寿
我们由浅入深地来
1：罪犯们可以讨论，并且也知道灯的初始状态，有2盏灯
2：罪犯们可以讨论，但他们不知道灯的初始状态，有2盏灯
3：罪犯们可以讨论，但他们不知道灯的初始状态，并且有一盏灯坏掉了
4：罪犯们不可以讨论，也不知道灯的初始状态，但是有1e8盏灯
5：罪犯们不可以讨论，但知道灯的初始状态，有2盏灯
6：罪犯们存在互相欺骗的情况，分析减刑状况
7：罪犯们存在互相欺骗的情况，如果是减刑后判10年呢，分析减刑状况
yz云：这明明是概率问题啊
对，这缺实是概率问题，因为在运气足够差的前提下，骰子掷到的都是5和6，
先假设他们不会选择欺骗，
我们要做到的是想办法找到一个必胜的状态：
(0). 显然囚犯勇敢地提出所有人都出去过了，!一定是在他放风时看到灯后!，‘’‘长有高猿长啸，嘱引凄异，空谷传响，哀转久绝’‘’
(1). 当到达该状态囚犯就能！确保！所有人都出去过了
(2). 所有状态都存在到达该状态的可能，也就是说不存在死路或必败状态
(3). 不存在欺骗
0x04 解决问题
1：罪犯们可以讨论，并且也知道灯的初始状态，有2盏灯
2：罪犯们可以讨论，但他们不知道灯的初始状态，有2盏灯
yz亦云：这明明是概率问题啊
3：罪犯们可以讨论，但他们不知道灯的初始状态，并且有一盏灯坏掉了
4：罪犯们不可以讨论，也不知道灯的初始状态，但是有1e8盏灯
5：罪犯们不可以讨论，但知道灯的初始状态，有2盏灯
yz亿云：这明明是概率问题啊，我们彼此无法交流，这灯的状态有用吗？
loading:
先假设我们找到了一个可行的解，如果在灯和人的分配上有冲突，那么这其实不是可行的最优解
先假设我们找到了一个可行的解，如果存在更优解，那就会采用最优解
首先，罪犯们都是绝顶聪明的然而我们并不是，从博弈的角度来看，一个罪犯所知道的，别的罪犯也知道；一个罪犯可以推知的状态，别的罪犯也都能想得到，也就是他们会达成心灵的契合。
其次，没法交流意味着没有分工，所有人都是记录者
基本思路就是不断提升我们到达必胜状态的概率从而逼近并找到一个可行解
我们把灯的 状态编一下号 0灭 1亮
由于知道初始状态，为了方便我们记初始灯为 00
00->1 01->2 10->3 11->4
25%:
所有罪犯都会想到：每个人放风时都会选择自己的编号，如果自己随便更改自己的编号，那么灯就废了，一个罪犯
的编号将在第一次放风时确定下来，
所有罪犯都会想到：放风时不要选择灯现有的状态，因为这样很可能就和别人的重了，别人也无法知道你的存在感
进而会达成共识：假如他们RP+=inf，所有人的编号都不一样，那么只要统计编号的种类，什么时候连上自己有4
种了什么时候就可以溜了
虎门销烟
40%
罪犯们不满足现状
于是所有罪犯都会想到：初始状态【1】是一个特殊的状态，那应该可以交流一些特殊信息，比如，如
何判断重复的状况！
于是他们会达成共识：自己第一次选的编号一定不为初始状态【1】，但这样必然引起至少一个冲突编
号
70%?
所以如果一个罪犯第一次出去，则会选择和此状态不同的编号，如果他发现当前编号不是自己的编号
就记录下来，并调成自己的编号；如果发现是自己的编号而且是刚才自己放风调成的那就假装无事发生，如果发现是自己的编号，并发现自己的编号被别人取走了，那么就把灯调成初始状态【1】，这样别人看到了就知道有重复的了。于是重复状态类型为 （囚犯编号）2，3，4，4，就可以解决了，因为只要不是第一次出来，看到【1】就可断言出来人数至少是编号数量++；
这样我们又提高了出狱的可能性
85%?
所以如果重复状态类型为 （囚犯编号）3，3，4，4，那又如何解决？
囚犯们都会想到：那简单啊，我们只需要在见到别人调的【1】和自己也是重复的【1】就可断言出来的人数等于灯的种类数+2了
但这样有个问题，两个编号为【3】的囚犯都发现编号重了，都选择了【1】，然后又撞面了，并且之前只有一个【4】出来，那其中的一个【3】不就遭殃了吗？如何解决两个人相同都发现自己编号相同的情况呢
囚犯们都会想到：【3】一旦选了编号【1】那就丢掉自己的编号，以后就一直选择编号【1】，这样另一个【3】就再也不会主动发现重于自己而是直接知道有重复的，就不会换【1】了，就不会对答案产生贡献
这样我们又大大加深了出狱的可能性 甲午中日战争
100%？
所以如果重复状态类型为 （囚犯编号）3，4，4，4，那又如何解决？
因为之前没有改【1】的机制，根据匹配机制，在二分图上是不会存在这个情况的，因为每个人都不会选和上一个重复，但现在就不行了
显然易证同理可得，这和，3，3，4，4是同一类型
那我们打最坏的打算，如果重复状态类型为 （囚犯编号）4，4，4，4，那又如何解决？
显然，所有罪犯都会想到：放风时不要选择灯现有的状态，因为这样很可能就和别人的重了
所以这种情况不存在
至此，此题圆满结束了 吗？
100%!
如果发现是自己的编号而且是刚才自己放风调成的那就假装无事发生，如果发现是自己的编号，并发现自己的编号被别人取走了，那么就把灯调成初始状态【1】，这样别人看到了就知道有重复的了。
仔细品味这句话，你会发现有点不对？
一开始你出去时一定会选择不同的编号作为你的编号，此后，
因为你所有出去时都调成了自己的编号，这样等你再次出去时仍然是这个编号，并不能断言有重复的，也就是你永远也没法断言有重复编号
怎么解决呢？
考虑引入模拟退学（huo/）的机制，引入温度T……，在T度时有概率P%；
在你发现等不是你的编号时
你有P%的概率会选择调成自己的编号
你有（100-P）%的概率会选择暗中观察，保持沉默，若你再次出去时发现编号变成了你的编号，那么你这时就可以断言有重复的情况，此后就可以选择【1】了
自此，芝加哥的狱警少了一个，多了一个OIer
6：罪犯们存在互相欺骗的情况，分析减刑状况
7：罪犯们存在互相欺骗的情况，如果是减刑后判10年呢，分析减刑状况
0x05 花絮时间
oi世界的机房内有四名熟练掌握信息经济学与博弈论的蒟蒻，因noip失利，分别囚禁在编号为1至4的单间机房里，进行训练。某天上午，娄克斯将他们集中并宣布：
今天起，每个月的noi复活节的那一天23点，我将掷一次骰子，如果出现1至4中任何一个点数，就将你们当中对应机房号中的人招呼出来放风一小时。如果出现5和6，当天就不给你们任何一个人放风。
在楼道入口大铁门处左右两侧各有一盏路灯，今天23点前，我去确定他们的开关状态，这个状态你们无法知道。此后，这两个开关只供你们四人使用，其他人绝不得再碰。总之，无论你们谁被放风回房时，都可以决定它们的开关状态，并用它们的开关状态传递信息。
如果有一天，你们当中的任何人向我断言「我们四人都放过风了」，如果他说对了，你们全部立即释放；如果他说错了就直接给我去拿ioi金牌，剩下的三个人的简单数论改为高考称病再学一年文化课，两年后交到班主任手中。如果一直没有人断言，那就永远让你们练下去。
现在你们在此商量如何用灯的开关状态表示信息，保证总有一天能被某人得到正确的断言。你们现在有一小时的讨论时间，一小时后押回各自机房，严格隔离。
本文作者：zzy
本文链接：https://yz-hs.github.io/3f5d366e12dd/
版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。
