高智商问题：100名囚犯如何用数学拯救自己？
HTML-код
- Опубликовано: 28 июн 2024
- 【加入会员链接】 / @tchliyongle
【订阅频道链接】 / 李永乐老师
------------------------------------------------
视频内容：
你听说过100个囚犯问题吗？100个盒子中装有100个号码牌，但是顺序是打乱的。每个囚犯独自打开50个盒子，如果找到了自己的号码就算成功。假如100个囚犯都成功了，就会被释放，请问他们应该采取什么策略呢？假如每个囚犯都随机开盒，被释放的概率非常低。但是如果采用一种特殊的策略，他们获胜的概率将会提高到30%以上，怎么做到的？点开视频看看吧！
------------------------------------------------
内容章节：
00:00 100名囚犯问题
01:27 随机概率
02:25 打开盒子的策略
09:15 策略概率
15:54 概率分布
18:58 增加囚犯人数
21:16 讨论引申
23:41 课后作业
------------------------------------------------
火热视频推荐：
如何才能摆脱贫穷？穷人和富人有什么差别？
• 如何才能摆脱贫穷？穷人和富人有什么差别？【2...
120万一针的抗癌神药为啥这么贵？
• 120万一针的抗癌神药为啥这么贵？免疫疗法C...
100亿美元造的詹姆斯·韦伯空间望远镜望到底能干啥？
• 100亿美元造的詹姆斯·韦伯空间望远镜望到底...
如何推翻相对论？广义相对论的建立和实验验证
• 如何推翻相对论？广义相对论的建立和实验验证
【经济泡沫1/4】一朵花换一栋楼？
• 【经济泡沫1/4】一朵花换一栋楼？疯狂的荷兰...
追剧买VIP会员去广告，值不值？
• 追剧买VIP会员去广告，值不值？李永乐老师讲...
神奇的鲁伯特之泪：子弹打不碎，一捏就爆炸
• 神奇的鲁伯特之泪：子弹打不碎，一捏就爆炸
千万不要用微波炉烧水！李永乐老师讲过热/过冷液体
• 千万不要用微波炉烧水！李永乐老师讲过热/过冷液体
5G到底是什么？它能成为创造未来的新科技吗？
• 5G到底是什么？它能成为创造未来的新科技吗？
如何才能长生不老？生命的时钟在哪里？
• 如何才能长生不老？生命的时钟在哪里？
------------------------------------------------ 
Наука
不论您在哪所监狱，李老师都是一个不可多得的好狱友。
確實
卧草，咱俩想到一起了，不过我没敢说，怕李老师多想。😄
但如果他是典狱长而咱们是狱友。。。🙃
@@andrewxia5143 出獄後 變高智商罪犯
更好的策略也必须利用这个顺序
這概率還要乘以得到李老師為獄友的概率。
身為一個準備犯罪的人 好好學習數學是非常有必要的
然后监狱长出题让你背诵乐谱
典獄長要你在他面前直接用塑膠湯匙挖出地道離開，前提是跟他放養的100隻彼特犬好好相處在同個空間
@@HeartShapeBlackLocust 別說了，我才被比特犬咬到，好險沒有咬很深
很遺憾你遇到的可怕經歷，希望那隻狗狗別再找你的麻煩
身為典獄長，看完這段影片並掌握犯人的心理學也同樣重要
看原片的时候也一直没弄明白为什么存在长度为k的环的概率为1/k，还是李老师讲得清楚，感谢！
非常喜欢永乐老师的讲解！我觉得这个问题策略最关键的部分就在于，看清这个数据的拓扑结构。其实关于分析----为何形成环？有一个简单的数学证明。可以从高等到初级的都有。这个观察可以延伸出拓扑学--欧拉数，同调理论，一维复形分类。这样一个看似纯数字的问题，有时候可以变成几何、拓扑问题看。（毕竟计算机里有很多 几何，拓扑的问题）。我就不剧透了。细心的永乐老师的小朋友们一定能找到属于自己的答案。
當時看原始影片時後半段的確看不太懂，現在都懂了，謝謝老師的講解！
很喜歡這類益智解題類的題目~~
讲得很清楚，谢谢！
作业：假设只有放风的人能看到灯，并且灯在放风的10分钟里可以多次开关。第一个人回来后，在第二个人放风的时候闪灯发送数字99（闪99次，或某种方式编码的99更佳，如2进制1100011）。以后每个人放风时候记录上次的数字，要是自己是第一次放风就把这个数字减1后第二天闪灯发给下一个人。直到某个人放风的时候没有看到灯闪烁，那个人就知道所有人都轮过了。
李老师你好，我是一名典狱长，感谢你的讲解让我有了新的启发
尝试解答李老师最后的作业：每个囚犯的策略都是当自己是第100次被叫到时，这点亮该灯，否则都不点亮。当下一个囚徒发现灯亮时，才报告狱长。原理是，这相当于一个几何概型。若有99个囚徒未被叫到，只有一个囚徒被叫到，此时概率是(\frac{1}{100} )^{100}。若有98个囚徒未被叫到，只有一个囚徒被叫到，此时概率是C_{2}^{1}\times (\frac{1}{100} )^{100}\times \left [ \frac{1}{100}+(\frac{1}{100} )^{2}+...+(\frac{1}{100} )^{99}
ight ]。若有97个囚徒未被叫到，只有一个囚徒被叫到，此时概率是C_{3}^{1}\times (\frac{1}{100} )^{100}\times \left [ \frac{1}{100}+(\frac{1}{100} )^{2}+...+(\frac{1}{100} )^{99}
ight ]\times \left [ \frac{1}{100}+(\frac{1}{100} )^{2}+...+(\frac{1}{100} )^{99}
ight ]。若有k个囚徒未被叫到，只有一个囚徒被叫到，此时概率是C_{100-k}^{1}\times (\frac{1}{100} )^{100}\times \left[\sum_{i=1}^{99}(\frac{1}{100} )^{i}
ight ]^{100-k-1}。把以上k=99~1的情况全部相加，就是该策略失败的概率，用计算机程序算得是1.020512e-200，几乎不可能失败。
下一个囚徒发现亮灯报告监狱长， 肯定有下一个囚徒，那么这个点亮灯的囚徒直接报告不就好了么？
超級精彩。希望李老師能多介紹一點「隨機算法」或「概率算法」，感謝
当犯人人数很少时：
如果犯人只有2个人，每人只能开箱1次
随机开箱：生存率 1/4=25%
每个人只开自己的：生存率 1/2=50%
如果犯人有4个人，每个人只能开箱2次
随机开箱：生存率 1/16=6.25%
开自己箱子和自己箱中对应箱子：1-1/3-1/4=5/12=41.7%
即使在人数很少时，按环开箱的生存率仍然比随机开箱提升1倍以上。
关于胜率大幅提升的原因，我的理解是：
每个箱子只能放一张卡片的限定，
这个规则导致了游戏可以按照“最大环长”对应100个可能的类型，进而对应 环数超过50 和 环数不超过50 两种模式。
“一人犯错全部处死”的特性决定了，需要团队作战，不能单人随机挑选。必须团体全部押注于一种可能的模式，才有可能胜利。
我们可以设想一个简化版的游戏：
如果有一个盒子，里面可能是 红球或者蓝球，且固定不变。让100个人排队依次猜里面的颜色。如果有人猜错，那么100个人全部处决。
① 单人随机押注：每个人随机猜颜色，生存概率只有 1/(2^100)
② 团队合作押注：事先约定好，所有人只猜红色(或蓝色)，那么生存概率是 50%
这两种游戏胜利的关键，都在于团队能否成功押注正确的游戏模式，
只不过原版游戏的模式，藏的很深，需要挖掘。简化版游戏的模式，很明显只有红球蓝球两种。
但是，如果原版游戏规定：每个箱子中可以有任意数量的卡片(包括0)，或者简化版游戏规定：每次猜测后箱子中球体颜色随机更换，那么单人随机猜测和团队合作猜测的生存率就没什么差别了。
你提的簡化版題目比影片中的題目更能讓人理解，感謝
谁知道罪犯中有一个卧底。。他没有按照规矩打开盒子，并把纸条又随机摆放了。。。
每次看李老师讲课，我都有一种梦回学生时代的感觉，我的思绪飞扬到了隔壁班的那个姑娘身上，想着她何时会路过我教室的窗口^_^
别指望了，可以想想那个姑娘的女儿了
即便是李老师的课，也不能阻止你想姑娘🤣
池塘邊的榕樹下.......
别指望了，人家已经成了村长的新娘
所以重点是盒子和盒子里的数字摆放方式有限，不能随便摆放，所以犯人可以通过策略来达到最大成功率而不是完全随机的二分之一的一百次方，但假如规则是100个盒子中只有一个盒子有一张纸条，50次开盒没开到所有人就必死的话，那概率就只能是二分之一的一百次方了
虽然概率啊公式啊 看不懂。但解题的思路真的是特别好的启发，数学思维，真的是迷人又神奇。喜欢李老师的讲解
黑心獄警那裏要補充一點，一開始要選(我的號碼+x)的盒子。
前面的策略有一個必須條件：環裏包含我的號碼，例如我是1號，我先開1號盒子，環閉合了就代表我最後開的盒子裏裝了1號，所以我的號碼一定在我選的環裏。
但假設我是50號，每次+10，我可能有以下順序：
(開50，裏面20)。(開30，裏面60)。(開70，裏面40)
40+10後是50，也就是我一開始的盒子，環閉合了，但我沒有開到裝有50號的。
而一開始選60號盒子，如果環閉合了，就代表我最後開的盒子裏是50號，換而言之，我保證了環裏包含我的號碼。
对，+x的策略可以理解成在每个盒子里的号码m的上面再放一个写着m+x的号码（超过n的要减n）。按上面的号码选盒子。如果我的号码是i， i+x需要出现在环里的上面号码里，也就是要从i+x开始。
当时看veritasium时候就考虑了下本质，其实就是把随机选择策略在存在51+环路时候微不足道的生存率舍弃，换得在不存在51+环路时候更大的生存率。但是只有一次机会的事情该不该仰仗几率学是一个争论不休的问题。
概率的定义也说了，我只是表示这个概率，并不是说多少次一定发生。
都是看tradeoff值不值吧？
就好比1-10000之间抽签。告诉你上上签在1-5000里面有2个中奖签，5000以上只有1个。你会怎么选？全范围还是放弃后5000？
那前5000有1000个呢？4999个呢？
就是轉蛋遊戲的當期主打中獎率兩倍，從1%變2%，你說即使變成2%，我還是有可能抽一千次都抽不到，對，但就是機率問題，至少抽到機率肯定是比1%高的，有趣的是現實生活中我們往往只關注有或沒有0或1，而不去失敗時距離成功的過程到底是遙遠還是接近
片尾最後問題(個人解答):
選出一個[記數者] ，每當他出去放風一次就把燈關起來，其他人一出去放風就開燈，但之前開過燈的就不能再開了。
這時[記數者]只要記他開過等的次數等於 囚犯-1(扣除他自己)就達成條件了
监狱长每次随机选的人…这个方法虽然可行可能耗时太长哈哈
我的想法和你差不多。不过我的条件是：第一次放风就更改灯的状态，放过风就不改。这样灯的状态更改n次就可以达成条件了。😊
@@somtype這個方式不可行，因為無法交流並且隨機，所以若沒有計數者這個身份並不知道燈的狀態被改變幾次，但計數者這個機制的放風次數只略低於50⁹⁹次，感覺關完人都死了需要在想一想
@@user-lg3nw1do9l 記數者是可以知道改變幾次的，只有在關燈狀態下且還沒開過燈的囚犯可以開燈，只要不是記數者，看到前一個是開燈狀態就不能動燈，問題就解決了，不過現實層面來講會很耗時。
@@user-rw1qg5ym2d 我知到,你好像要跟我上面的說，你是不是標錯人XD
李老师晚上好🥰
今天也谢谢分享
逻辑清晰👍
这个思考题我有几个问题哈：
庭院只有一盏灯
所有囚犯能且只能看到庭院的灯光，显然不能看到点灯的人
放风的人可以在10分钟内随意开关灯
每次放风的人都是随机选出的
每日固定时段放风，非放风时段假设有狱警干预灯光
那这样的话我倒觉得可以用2进制解决吧。囚犯们给自己编上1~100的号，用2进制表示，那么100号为1100100(bin)。以分钟为单位，熄灯代表0，亮灯代表1。比方100号囚犯就可以在10分钟内，以0001100100的形式展示自己的编号（第1~3分钟熄灯，第4分钟开灯，类推）然后所有人都可以得知。
牢房应该有钟吧....哈哈哈哈哈哈
非常喜欢老师的视频，涨知识，练脑子。有两个问题，随机拿对的概率好像应该是（1/50）100次方，拿了号码之后如果不放回去不是空了吗？😄
我想前提是要把牌子放回去吧,不然鏈子也會斷,方法自然也沒用了吧
每个囚犯获得有各自的计数设为k,初始k = 1.
当前的天数为n,从0开始计数
设i= n mod 7
如果灯是点亮的,在k 加上 (2^(i-1)),将灯熄灭,
当i < 6 时 如果k == (2^i)或者(k/(2^i)) mod 2 == 1 则将k 减去 (2^i)并且将灯点亮
任何一人计数达到100则可以报告
以上==为等于,^为乘方,mod为取模)
這種方法我想到的是倘若自己的號碼箱裏不是自己的號碼，那麽自己號碼就肯定不在箱號對應的箱子，順著箱子裏的號碼繼續找下去，就可完全避免開到箱號對應的箱子來浪費機會。
另外欧拉公式的部分其实完全可以用微积分算，n到无穷时其实就是1/(1+x)从0到1积分，等于ln 2
反过来思考更容易理解，首先要明白这里面每一个数都在某一个环里，不管是一个超大的环还是一个自己连自己的环。然后当你选择自己的盒子时，你已经选择了有你那个数的那个环，从而把其他环排除了。
找到一个直接把号码写在盒子上
你就换了个说法而已，你反过来个毛线了
你说的很对，但是有一点我没太理解：就是后面那个 +X 的策略，每个打开自己号码的盒子后，跳转到的下一个盒子是取出号码+10。+10 以后不就很有可能跳出 “有你那个数的那个环” 了么？为什么最后成功的概率仍然不变？
@@baiy-cn +10后就是新的一群环了，可以说是重新洗牌来绕开监狱长故意设置的长环
@@chikuwa_2564 嗯，我也是这么理解的，但为啥最终成功概率不变，仍然是 30%+ 呢？
李老师讲的太好了😀
題目應該
從
所有人選都選到自己的號碼獲釋
改成
所有人都選到自己的號碼才全體獲釋
這樣會比較好理解
思考题虽然简单，但是李永乐心是真黑啊，不想放人就直说。
解法如下，100个犯人里有一个叫李永乐的狱霸，他负责计数。其他犯人约定每人只有一次机会把灯点亮。如果后一个犯人发现灯是亮的，他不用点亮灯，也不消耗他自己的机会，如果犯人已经点亮过一次灯，他就没有再触碰开关的机会，不管灯亮还是不亮，转身就走。轮到李永乐去放风的时候，如果灯是亮的，他就把灯关了，并且记录一个数字，当李永乐记下99个数字时，所有人都至少碰过一次开关了，下次再轮到李永乐的时候，他就可以大声报告了。我觉得期望至少在100年以上，因为李永乐每年只能期望被放风三次，太难了。
那其实不用这个策略，就按照完全随机状态下计算全放一遍的概率达到90%就直接赌一把算了，也不用100年
@@chenkarenina4299 是的，10%得概率全体被处死，你说是多关些年好还是10%被处死好呢，好难回答啊
我看到一半就在想要是有黑心獄長怎麼辦，沒想到老師還有對策在片尾，還好我每次都是看完整片。
黑心监狱长对策那里不是很懂，如果有长环为什么+10就能解决，概率不仍然是三成吗
@@wholink6179 如果我沒理解錯誤的話,加任何數都能解決哦,因為環的排序就亂掉了,回到31.2%出現不會是原本超過50長度的環
只是在已知按原本策略圈內有大於50的環，所以通過一點小技巧避開人為製造的難題，但即使如此獲救機率確實還是只有30多％
@@wholink6179 仍然只有30%沒錯，從0%變成30%。
萬一監獄長也預判到囚犯會這麼想，只要在櫃子裡放原櫃子號碼加一號，這策略就必死無疑。
比起數學題本身，李老師的講解方法跟 Veritasium 的對比更有趣
关于后面那题，
首先，选出一个领袖（或者其他什么的，反正选一个人就是了
区分一下，领袖和其他人
然后呢，当游戏开始的时候（灯开着的）
其他人如果看到灯开着，就要关掉，
反之灯关着就不用理
而领袖一定会看灯被人关了，所以就要去开灯
并且
他还需要去数，灯被关了多少次了，如果灯被关了99次，就可以游戏通关了
逃出生天
课后题一个点不太清晰：只有被选中放风的囚犯可以改变灯的状态，但囚犯什么时候可以看到灯的状态呢？
如果囚犯随时可以知道灯是灭的还是亮的，那每个囚犯第一次放风的时候都去改变灯的状态，当灯一共改变100次状态即可。
如果囚犯只有在放风的时候知道灯的亮灭状态，那就得选一个囚犯出来当计数员。别的囚犯放风如果第一次看到灯是灭的，就有把灯点亮；当计数员每次看到灯是亮的就去把灯灭掉，灭99次即可。
这个题确实是有好多细节：比方是不是连续放风？如果是每天固定时段放风几次的话，会不会有狱警动灯？....感觉条件还是要在捋一捋....
這樣只要有一個人被叫去兩次就全滅了吧
@@Wooder-gg6lj 只有計數員可以滅燈，其他人只有在第一次放風，且燈是滅的時候，才去點亮，避免被重複叫到
李老师是神一般的存在
讲的非常好！
最後的問題
嗯……
即使不考慮開關燈，光是要所有人都得隨機被抽到一次的最高期望值機率天數就已經需要很長的一段時間
結果其實獄長從那天開始偷偷把所有人排序然後一個一個叫出去放風 :)
我想法是
進去的人改變一下燈的狀態
重複的人不做任何動作
累積100次燈開關就可以了
外面的人看不到燈，沒人統計
这种策略的妙处就在于：在监狱长放好一切号码之后，犯人生死就已经注定。而如果各自随机选，就和抛100次硬币一样，你的生死还由你后面队友的运气决定。
不一定 就像李老师说的可以订一个加数 开到5号就去开15的盒子 那环就换掉了 所以还是31.2的运气问题 如果监狱长是想要放他们出去没有设计任何一个大于50的环 偏偏囚犯自己定了个加数那么环就又乱了 还是31.2的机会了
李老师，想听你讲讲P/NP的问题
我認為成功機率的提高，源自於減少了重複牌，且每個箱子只對應另一張牌，
解法應該不同
最后的问题，我想可以用李老师以前讲过的一个编码+二进制的方法解决。
1號負責開燈，其他人只能關燈。每人只能關一次燈，當一號開了第100次，表示大家都放風過了。
另外，原題目沒說囚犯不能交換盒中號碼，而且是按照順序進入，那就可以用排序的方式再提高成功率，粗算97/198
这个方法不错。不过这个附加题感觉没有能保证的解法。比如楼主这个方法，如果一号只被叫一次，之后再也不叫了，那就会卡住了。。
我有一个更笨的方法，比如可以规定一个数字n，假设n=100。那么每个人都会有自己的专属时间段可以开灯。比如第一个人只能在第一个100天里开灯，第二个人只能在第二个100天里开灯。。每个人在非自己的专属时间段内，唯一要做的就是在这个时间段的第一天关灯，其他天什么都不做。这样在第i个人的专属时间段内，如果第i个人正好放风了，那么在他之后并且在这个专属时间段内放风的人就能得到信息：“第i个人放过风了”。这样一直循环循环。。一直到有个人比较幸运，他收集到的信息正好可以推出所有人都放过风了。
这里n的取值是可以变化的，感觉会有一个最优的n使得期望的等待天数最小。不知道这个方法和楼主的方法比哪个期望值更小？求李老师解答！
@@kevinklain2134 如果典狱长按你说的，一号叫一次，剩下99个人循环，或者就两三个人循环交替的放风，剩下的人等到死也轮不到释放了🤭
@@HRWU 是的，也就是说应该没有解法可以确保在每个人都至少放风一次以后，可以在有限时间内让典狱长放人。只能比较每种解法的平均期望值，看哪种解法更好。
总感觉还有更好的解法，你这解法不考虑时间成本固然可行，但实际赦免期望都几十年了
@@ZCraneY
犯人全部都给自己取名一个号码》
无论如何选中谁都不要开灯
除非1号开始开灯》
1号出来开了灯》
无论如何谁都不要不要关灯
除非2号关灯》
2号出来关了灯》
3号等被选中 。。。
一直到 大家对着灯数到100次开关
（越后面被叫去的人 黑眼圈肯定还黑过熊猫）
在獄長作弊的情形下， 打亂有一種最直觀的方法， 就是將盒子編號用亂數重排。
太牛了，非常有趣有涨知识
盒子里放的是指针，指向指针的指针，指向指针的指针的指针…一个检索取址的计算机算法问题。李永乐讲课真不错
谢谢总结
@@TchLiyongle 好有意思，想请教一下老师。如果监狱长的设计两个环，一个是51的环，一个是49的环，是不是囚犯就无解了？如果两个环的话，+X的方法好像就不能再使用了，因为这样就又成了新的两个环，而且只有在X为特定值的时候才能使这两个环恰好都是50，但这个值我好像算不出来
如果用+X的方法得出來環的數量就不一定是兩個了吧（我不確定是不是我理解錯誤），我認為+X之後環跟原本就完全沒有關係了……所以逃出的機率還是1/3左右
@@user-wm3pf8fd5p 好像还是两个，概率也是31%左右
@@user-wm3pf8fd5p 本质其实是不变的
實際上的情況：1號跟100號盒子裝的都是87號牌 然後全員處死 死無對證🤪
怎么出现两个87号，这样犯人肯定会拿到证据并举报，监狱长也会判刑的。
@@junsongli1815 都死了 誰舉報？:)
链表检测，环：表示一个链表中是否存在相同的元素，若存在，表示这是一个环形链表。
不过，哪里会有好心的狱长，会让狱友知道这个环在哪。如果，我是那个黑心的狱长，会直接设置无环。那么， 这个好心的狱友，只有可能是狱警走漏了消息！
是计算机“检索”相关的问题。使用index会提高检索效率，降低检索时间。
其實，只要監獄長藏起一個號碼，人人都必須處死😅
陰間
藏起一個號碼 那監獄會暴動啊
那處死犯人的藉口不就更多了嗎
@@user-pb1ng9wz1l 但是囚犯以为自己失败了😃
藏起一個號碼代表會有一個號碼重複啊，全部人中有最少一個人開到兩個一樣的機率近乎100%吧
結尾那題，第一個放風的囚犯為計數員，計數員只關燈不開燈，而且只有計數員能關燈，計數員每關一次燈就計一次數；接著，其它囚犯只要放風時看到燈是暗的，並且自己沒有開過燈，不論自己是第幾次放風，就把燈打開，如果囚犯開過燈了，往後放風時就不要去開燈。這樣子只要計數員關過99次燈，就一定能確保所有人至少放風過一次
要关到地老天荒了
強！👍慢了點但至少是對的
计数员到98次的时候突然想到了一个问题：“一开始灯是亮的还是灭的？”然后疯了……
這樣他們被放出去的時間期望值是一萬天，大約要被關30年，而且這30年中如果有個沒開過燈的囚犯死了，那就不可能達成了
@@user-cd5ri8kg7m 慢了億點
第一個放風的囚犯開燈, 第二個放風的人如果從未放過風的話就把燈關掉, 否則就不要動那盞燈。如是者, 只有第一次放風的囚犯才會改變燈的開與關, 放風超過一次的囚犯都不踫那盞燈。當那盞燈第50次熄滅時, 全部100個囚犯都已最少放過一次風。
理性分析，
就是
用打开盒子里的数 去找下一个 盒子（标记同样的数）去打开，
那下一个盒子里的数肯定不是那个盒子的数。
减少了 发现盒子里是盒子上标记数的概率到0
如此增大了 发现自己数的概率
因为标记有自己数的盒子已经被打开了。
突然发现这个变成一道中等难度的面试题，给定一个长度为n的数组nums，nums[i]=他指向的index，return true如果所有人呢都可以逃离，return false如果不行， n=1e5
用龟兔赛跑演算法来求有没有circle
通过这期节目，我深深的体会到，老老实实做人，切莫犯罪；认认真真学好数理化，尤其是数学，真的走遍天下都不怕，包括进监狱。😄
数学再厉害，也只有1/3 的生存几率😭
谁家监狱长会这么无聊任性🤦
谁家监狱长会这么无聊任性🤦
李永乐老师，下期可以做一下最近最火的可乐变可乐冰沙的原理吗
对于思考题我觉得可以这样。选一个罪犯，比如1号，负责计数，当灯状态变化（由灭变亮或者由亮变灭）时计数加一。所有囚犯遵循这样的规则：当且仅当自己第一次被选中时，才可以开或者关灯。当计数到100的时候就胜利了。
这个是比较容易懂的策略，每个囚犯都能简单操作。那么有没有更复杂的运算策略使得成功概率提高呢？
于北辰说它的爱三防空导弹拦截成功率有70%，发三枚就能有210%的成功率，我竟无言以对。。。
最后一个问题：只有第一个人有开灯的权利且奇数日只允许第一个人出去放风开灯偶数日另外99名囚犯随机出去放风关灯并关过灯的囚犯不再出去放风，那这样当第一个囚犯出去放风第一百次也就是所需199天时间就可以全部100名囚犯至少出去放风一次
绝了，李永乐老师
这是两个概率问题：一个是排列固定，囚犯按照这个链表法有1/3的排列能逃出生天。一个是不管排列，囚犯随便猜，机会几乎为0.
最後典獄長設計超過50的長環那裡的破解方法有點疑問，若是每個號碼都加10，那開到91以上號碼的人，加10就超過100了，那是否就只取後兩位數就好呢？例如：91+10=101開1號箱，100+10=110開10號箱這樣~
那是當然，否則1到10永遠不會被打開
难得把一个复杂的数学问题讲得这么简洁有趣。直觉根据这么一个简单策略就能提高百万倍不太可能。细想问题出在环长都小于五十的情况，和每个人都找到自己的数之间并没有必然联系。比如10到20到30到40到10是一个长度为4的闭环。囚犯是3号，打开箱子里面装着10号，这样囚徒跟着走一圈来到10号。他该怎么办？如果继续按策略走下去，就只能重复转圈。找不到自己。只能更换策略，这样多走几个圈也不一定找到自己。
对于3号囚犯来说，他的环里面一定要有3号才算是一个闭合的环。所以他不可能会在10，20，30，40再到10的环里，除非他10号的盒子开了两次，否则不重复的开下去一定会有3号的。
相对而言，对应李老师这种策略最好的方法就是1-100都对应下一个号码，这样又回归了50-50了。
看了蠻多留言 基本上課後問題解法都一樣 選一個熄燈人 問題來了 運氣好熄燈人每次去都是亮的 運氣不好有一次不亮就加一百天(平均100天熄燈一次 越後面不亮機率還會越高) 所以9900天完成算運氣好的 仍然需要27年時間 這個方法的效益太低 在隨機抽取的情況下 2年有人沒被抽到的機率是 萬分之6.5 你會選擇兩年賭一波 還是27年穩一波 策略是必定生存 但27年跟基本上跟死了沒差別
為了確保都有抽到提高到3年，除非監獄者惡意滿滿不然基本能出去了
那就是純賭而已啊，也不用有什麼策略，也不用開燈了
老师，有一点您没有说道：怎么证明这是最佳策略呢？如何严格证明没有另一个更好的策略可以把概率提升超过31.2%？
頂
那好像不好证明
每人机会都是均等的…就算狱长故意造超过50的环，囚犯用+1就可以打乱顺序去破解，但前提是大家用同一种策略..如果不相同，肯定不优
老师像在误导囚犯跳入陷阱。。😂
最佳的得救方式 还是 让狱长要去改变游戏细节，比如增加一些规律在箱子排序，
而不是去用画线排除法 假以为可以提升几率。。
只要链长度超过一半，规则就没用了……
首个人为"关灯员"，只关灯。后面放风都是"开灯员"，每个人都只在，自己第一次"看见关灯"的时候开一次灯，后续不开(每个人只开一次)。直到"关灯员"计数关了99次灯，则认定为全放风过了。耗时多久取决于关灯员能否 穿插着进100次
这是个合理的办法，但是从概率上说，估计要小30年了。不如等个三年五载直接说，那样有人没放风的概率已经小得可怜了。这个题目告诉我们追求完美的边际收益太小了😄
如果进去的囚犯在开箱过程中能够调整看到的盒子和里面的号码，去人为缩短链条，成功概率应该能大增。如假设每个囚犯能够记得自己开箱前看到的五个箱子的情况，不知道这个概率是不是能调整…
身為唸computer science畢業的人 這集我覺得非常有趣。。。 腦袋想了一下才懂
脑袋想了一下才懂，总觉得有什么问题
@@ngsaikeong 你別急著裝B 我也CS畢業的 這傢伙說的大概是他沒看李老師的解釋 自己先想 想了一下才懂 :)
@@ngsaikeong 我CS1.6畢業的 也是一想就懂 屬實正常
@@ngsaikeong 我看你是沒有吧 笑死 可憐
@@ngsaikeong 我會啊 不會的是你吧 在嘴你根本沒文憑在這BB啥呢 聽不懂嗎 還不閉嘴去拿你的文憑 不是很簡單能拿嗎 連張廢紙都拿不起？廢W🤭
感謝老師詳盡的說明計算過程 建議這些囚犯多一個動作 還可再提升生還機率 找到自己的環後 把號碼紙交換到對應的盒中 這樣後續找到自己號碼的犯人還有更多開盒次數去搜出別的環 我想規則沒提到可以幫號碼換盒子是吧^_^
干脆不玩这个游戏。一百个人集体暴走，不被人耍。干翻监狱长
@@austinsoong7217 也是可阿 只是機率就沒有參數可供計算 自己賭嚕
@@riceberg0413 那得是特殊极端的自然因素造成的，必须这样抉择。只要是人为的规则，干掉人就解决了
选一个leader出来计数 其他人只有灯灭同时是第一次放风的时候才开灯的策略大体是对的 但是因为题目没有明确说明灯的初始状态（灯最开始是亮的还是灭的）所以我感觉需要其他人前两次放风同时灯都灭的时候都开灯 然后计数的人数到198的时候才能确定所有人都放过了风
没仔细听题目啊，明确说了灯的初始状态是熄灭的
思考题好像做过类似的，先商定好只有一个人能够开灯，假定是1号。 策略是所有人都等1号放风，然后1号把灯打开。 那么第一次开灯就是1号放风。然后99名囚犯后面进来了，就关灯。而等1号开灯后如果再放风，发现灯关了，就数+1并且再开一次灯。而前面关过灯的囚犯再也不参与开关灯了。只需要1号观察到99次关灯，那么就等于所有人都放风过了
还有一个关于这个问题的拓展思考。不管什么策略，单个囚犯的找到自己号码的概率总是1/2。所以要提高所有囚犯找到自己号码的概率，必须提高他们找到自己号码的相关系数。本题解法使得在号码在一个闭环（长度小于51）里的囚犯有百分之百的相关系数。所以整体概率大大提高。这个概率肯定小于1/2。请问上限是什么？本题解法是最优的吗？
上限就是1/2。因为在没有额外信息的情况下总成功（找到自己号码）人数期望是50。最理想的就是100个人要么全成要么全不成，概率各1/2。视频解法是否最优这个证明就比较复杂了，我没想到
老师，我觉得有一个内容，您得讲一讲，就是关于“这些解法，都是怎么想出来的”
我听都能听得懂，复述给别人讲也没问题
但是，如果不听，恐怕我一辈子也想不出来
我觉得，这里面肯定有什么玄机。
这解法是怎么想出来的呢？这解法是怎么想出来的呢？这解法是怎么想出来的呢？这解法是怎么想出来的呢？这解法是怎么想出来的呢？
说的没错...不过要想出这些策略，首先要成为一名优秀的数学家。。。。要有充分的知识储备，才能有足够的思路想到最好的解决方案。
李老师有一次讲课提到过，研究新课题，必须是在充分了解前人所作的努力的基础上。否则就会是有点扯淡的事情。。。
哇竟然被李老师点赞了！好兴奋哈哈哈~
我头两个月刚买了李老师的书给孩子看，我老婆还是您的老乡~~~
谢谢李老师！
老师，这个开盒方式是生存概率最大的方式吗？为什么是最大解呢？有没有别的方式可能比这个的生存概率更大呢？
求生概率高的方法有个trick--上一次开出n号球，去n号盒子，n号盒子里面必然不是n号球，所以概率比盲开要高
課後作業 (改良在留言看到的解法):
100 個人先決定一個天數 m (< 100)，在第 m 天以前，由第一個重複放風的人負責計數並將燈打開，如果在第 k (< m) 天就重複就從 k - 1 開始計，之後到第 m 天放風的人不動燈 ; 如果 m 天都沒有重複就由第 m + 1 天放風的人從 m (自己重複) 或 m + 1 (自己沒有重複) 計，從第 m + 1 天開始如果是第一次看到燈是開的就關燈，直到輪到那個負責計數的人觀察，如果燈是關的就計數 + 1 並開燈，否則就再等下一輪，直到加到 100 結束。
m 可以透過計算發生重複的機率和分析其效益成本決定。
由第一個重複的人負責計數而非事先隨機挑選，可在第一次就決定數個已放風的人數，之後同樣一輪只決定 1 人，一般情況可較原解法花較少時間。
其實我不懂這題目要做甚麼 也看不懂你要做甚麼 我的解答很簡單：
大家討論時給每個犯人一個編號 每人出去放風時用二進制開關燈發出自己的編號 等所有編號都放風過 報告獄長......
我認為題目的意思是獄長每天隨機選擇人到庭院放風，只有在庭院的人能控制和看到燈，其他在牢房的人並不能在非自己放風的時間看到燈的狀態，也就是說每個人在放風時只能知道前一天燈的狀態資訊和傳遞資訊給下一天的人，如果每個人都能看到燈的狀態的話那太容易了 (很容易地想得到最佳解)，出這問題沒有什麼討論意義而且我不認為獄長會那麼好心，依照老師敘述的題意被關在牢房裡還能看得到位於庭院的燈也不合理 (雖然我們不清楚監獄的結構)。
我看到的原解法是先選出一個人負責計數，當其他人是第一次看到燈是關 (初始狀態) 的就開燈否則維持原狀態，而輪到負責計數的人就觀察燈的狀態，如果是開的就計數 + 1 並關燈，代表確定在與上次放風的期間至少有 1 人是還沒被算到的，直到加到 100 結束 (包含自己)，顯而易見地平均情況需要花很長的時間。
我的改良解法是想試著在第一次計數時就多計一些人，因為一開始隨機選擇而重複的機率偏低，從粗略分析最佳情況和平均情況來看，我想是能預期花比較少的時間確保 100 人都已放風過，當然這跟 m 值的取決有關。
@@f1nd592 是 我後來看到其他留言了 題目沒說清楚
條件：100天一循環 犯人編號1-100
規則1.自身編號與當天循環天數相同則亮燈不同則滅燈
規則2.前一天的燈為亮則當天才可繼續亮燈 否則則為滅燈 並等待下一個輪迴
規則3.編號100成功完成亮燈 則宣告結束
2>1>3
這... 應該會先老死吧
第一個A出去時打開開關
之後所有其他人第一次出去看到燈亮就關掉
已經被關了就不動
每一個人只有第一次出去要動開關，其他就不動
下一次這個第一個人再次出去，看到燈暗了，就再打開燈
以此類推，等到他count到人數次-1開關之後就代表所有人都出去過了，即可以回報
最后的问题太不清楚了。
1. 谁能看到灯？ 如果所有都能看到庭院的灯，那只要规定每个人只能碰一次灯，然后大家就数灯改变过几次状态即可。
2. 每次放风能开关几次灯？如果可以多次，那每人编个号，每次用灯的亮灭来二进制传递自己的号码，更简单。甚至直接摩斯码群聊都可以。。
課後問題：
100個囚犯選一個人稱為關燈者，只有他可以關燈。其他人放風的時候看到燈是亮的就不作事，看到燈是關的就把他打開，但一個人只能開燈一次。關燈者出去看到燈是亮的則關燈計次，計完自己以外的99次即為全部人都開過一次燈，符合條件。
正解
666
同意
这个计数者一年放风期望三次，每年记三个数，记100次要30年，大家早就刑满释放了
@@chenkarenina4299 所以大家还是别费脑细胞想方案啦，老老实实等刑满释放就行了。
Have 99 of them to only turn on light if light is off and each of them can only do turn on the light once. Have only 1 prisoner be able to turn off light and that person will be able to tell when he turn off the light 99 times. . . Is there a better solution than this?
Big problem for this solution:that guy has to get pick 100 times when it’s a 1/100 chance everyday
nice solution
请问李老师，如果囚犯x遵守策略在开到第35个盒子的时候尚未解脱，是否存在修改策略并提高后续成功率的可能性呢？
最后留的题目，是所有囚犯都知道放风的时间，都能看到灯吗？如果是这样，就可以规定如果自己是第一次放风，就去改变灯的状态，例如抽风般的亮灭亮灭亮灭，如果自己不是第一次放风，那就不要去改变灯的状态。直到大家看到100次灯有抽风一样的亮灭亮灭亮灭变化，表示100个人都放过风了。
给小朋友出一道思考题: 如果题目不是要求k>50，而是要求k>49，也就是说每个囚犯最多能打开51个箱子。那么这种策略的的存活概率是多少呢？如果k>48或者k>47呢？k>0呢？
卧槽 大佬
自己代公式OwO
@@ryoyan1128 李永乐老师那个公式只适用于k>50的情况。
"我要是懂这么多就不会坐牢了“
這世上還有冤獄、意外傷害等等各種情況，監獄也不是設計來關笨蛋的。
课后作业应该是用二进制计数
又没说闪灯只能表达一种信息,每种信息闪灯之间的间隔长些或者有暗号就可以表达多于一种信息.
分成两段.
第一段闪灯闪自己编号的数目.
第二段闪自己的队友有没有闪过,(假设10个人一组,每一组人的个位数要一样(1,11,21,31...)这样每个人只需要记住10个号码有没有闪过就行,如果怕有人记不住,少人些一组就好)
如果自己组10个人都闪过灯,那经过第一段信息之后,间隔一段时间后灯就长开不灭,直到放风结束.
如果队友没全部闪过灯,那就直接灭灯直到放风结束.
这样长开灯10次就GG了
Use the light as a counter. Start with the light off every night. Turn it on and off once, count it as one. Each prisoner just needs to remember the number of the previous counts. On his turn to go out, he has to turn the light on and off one more time, if it is his first time to be let out. Otherwise, turn the light on and off the same number of times as the previous night. For the first prisoner, he starts with one. After seeing 99 counts, the last prisoner will know he is the 100 prisoner.
Or, if the prisoner had been let out before, he may choose not to turn on the light at all.
Another solution is that a prisoner will only turn on the light once he is let out for the first time. In this case, every inmate has to record the number of times the light has been turned on.
Good solution! How about in the other condition that only the one who is let out can see the light? ie, they cannot know the status of light when staying their room. Also an interesting question.
@@whitytsubasa Interesting condition. The light is the only communication channel in this question. Without it, there is no way to signal other inmates.
@@whitytsubasa Choose one of the prisoner to calculate the time that the light turn on, start with the light on, the choosen one can only turn off the light and calculate how many time the light was turn on, the other prisoner can only turn on the light for first time they let out, otherwise they do nothing. Then when the choosen one find out it is the 100th time, they win it.
@@Cookie-sg7lt But it takes too long! The counting prisoner need to be let out at least 100 times? I think of no other solution though
毕业以后：数学屁用没有，每天都是看领导脸色。看完李永乐老师的视频：老子要用数学拯救世界。
然后世界教你，你先救你自己吧
做蛋糕可以，分蛋糕no。
李老師 可以拍視頻解釋狂賭之淵 雙 第一集的骰子機率問題嗎？
用python写个程式模拟一下呗
程式可以模擬 但數學公式如何表達出來
好頭痛 ;(
也好证明，就计算一下每个组合对上其他不同组合的胜率即可
只要囚犯第一次被放風，就把燈開關一次累加進累積的總初次放風人數，否則把燈開關一次至累積的總初次放風人數，直到哪天發現燈明暗了100次就可以出獄了。例如：第3個初次被放風的人就把燈明滅3次，之後有另一個前兩次就被放風的人（非初次放風者）又被放風，則仍然把燈開關3次，直到登連續明暗100次即為成就。
平時口袋都放著李老師，生存機率就會大大提升
估计还没求神拜佛 来得几率大，遇到危机证明倒霉，倒霉是一种超越知识的存在，比如飞机。火箭，在怎样检查 总有意外发生，这就是倒霉
倒霉理论是超越任何的存在，运气什么的都没倒霉厉害
总觉得提出问题的那个美国科学家有点眼熟，查了下原来Robert Sedgewick就是著名的算法第四版的作者。😂
第一个放风的囚犯开关灯一次，第二个放风的囚犯开关灯两次，以此类推，每个囚犯记住自己的顺序，和当前放风的人数，再选中自己放风的时候不要在开关灯的总次数上+1，等开关灯次数达到100的时候好日子就来了
100個囚犯找一個人（或是第一個人）做記錄，由他進行第一次開燈，之後的人如果是第一次放風就關燈，如果之後的人到場發現燈已關或是第二次放風看到燈是開的都不需要動作，直至紀錄者開燈一百次且下次放風時發現燈已滅就代表所有人都放風過了
好有意思，想请教一下老师。如果监狱长的设计两个环，一个是51的环，一个是49的环，是不是囚犯就无解了？
那囚犯只要打開盒子內號碼+n(n⋳N n
@@gamedier 不会，你会发现必然会再次出现两个环，一个大于50一个小于50很难做到正好是50两个环，李永乐老师好像只考虑到一个51的环，剩下的随机
@@user-fw9tx6fn8r 李老師的跳號解法確實是只考慮到一個較長的環
@@mu416 请问您怎么看我的提问
@@user-fw9tx6fn8r 請問一下，+n之後應該未必還會是兩環吧？
最後的問題：
第一個放風的囚犯把燈點亮，之後每個放風的囚犯如果是第一次去放風就改變燈（亮的變暗的 暗的變亮的）第二次或以上就不動，只要第五十次亮起的燈熄滅了，所有囚犯就能釋放
好像行得通，不过应该没这么简单吧？我读得书少，不要忽悠我啊！
不行吧…再下一个囚犯无法得知上一个囚犯把灯熄灭前的再上一个囚犯是否曾经点亮过这盏灯。更不要提计数了，你每次出去只会看见一盏亮着或者灭着的灯。
不要自行擴充題意，題目只說庭院可以看到燈，牢房看不到
@@HRWU 我有說第二次或以上放風的時候不改變燈號 所以你提的情況照樣行得通
@@oscarlin3555 阅读疏忽了，抱歉🙏
有意思，quick sort的思路
讲的好好