高智商问题：100名囚犯如何用数学拯救自己？

[@T69732]

不论您在哪所监狱，李老师都是一个不可多得的好狱友。

[@ZigerMa7]

確實

[@jizhou749]

卧草，咱俩想到一起了，不过我没敢说，怕李老师多想。😄

[@andrewxia5143]

但如果他是典狱长而咱们是狱友。。。🙃

[@jjmanewu5836]

@@andrewxia5143 出獄後 變高智商罪犯

[@felixjovial8747]

更好的策略也必须利用这个顺序

[@haofeifan6322]

非常喜欢永乐老师的讲解！我觉得这个问题策略最关键的部分就在于，看清这个数据的拓扑结构。其实关于分析----为何形成环？有一个简单的数学证明。可以从高等到初级的都有。这个观察可以延伸出拓扑学--欧拉数，同调理论，一维复形分类。这样一个看似纯数字的问题，有时候可以变成几何、拓扑问题看。（毕竟计算机里有很多 几何，拓扑的问题）。我就不剧透了。细心的永乐老师的小朋友们一定能找到属于自己的答案。

[@jinjinlou5108]

看原片的时候也一直没弄明白为什么存在长度为k的环的概率为1/k，还是李老师讲得清楚，感谢！

[@whitytsubasa]

當時看原始影片時後半段的確看不太懂，現在都懂了，謝謝老師的講解！

[@cheongfuhxiong4892]

這概率還要乘以得到李老師為獄友的概率。

[@pig...]

片尾最後問題(個人解答): 選出一個[記數者] ，每當他出去放風一次就把燈關起來，其他人一出去放風就開燈，但之前開過燈的就不能再開了。 這時[記數者]只要記他開過等的次數等於 囚犯-1(扣除他自己)就達成條件了

[@clairele6]

监狱长每次随机选的人…这个方法虽然可行可能耗时太长哈哈

[@somtype]

我的想法和你差不多。不过我的条件是：第一次放风就更改灯的状态，放过风就不改。这样灯的状态更改n次就可以达成条件了。😊

[@阿餅-e7g]

​@@somtype這個方式不可行，因為無法交流並且隨機，所以若沒有計數者這個身份並不知道燈的狀態被改變幾次，但計數者這個機制的放風次數只略低於50⁹⁹次，感覺關完人都死了需要在想一想

[@耶比-w8p]

@@阿餅-e7g 記數者是可以知道改變幾次的，只有在關燈狀態下且還沒開過燈的囚犯可以開燈，只要不是記數者，看到前一個是開燈狀態就不能動燈，問題就解決了，不過現實層面來講會很耗時。

[@阿餅-e7g]

@@耶比-w8p 我知到,你好像要跟我上面的說，你是不是標錯人XD

[@q0Jameses0p]

身為一個準備犯罪的人 好好學習數學是非常有必要的

[@tiskybu6561]

然后监狱长出题让你背诵乐谱

[@HeartShapeBlackLocust]

典獄長要你在他面前直接用塑膠湯匙挖出地道離開，前提是跟他放養的100隻彼特犬好好相處在同個空間

[@Guamiha]

@@HeartShapeBlackLocust 別說了，我才被比特犬咬到，好險沒有咬很深

[@HeartShapeBlackLocust]

很遺憾你遇到的可怕經歷，希望那隻狗狗別再找你的麻煩

[@user-mintshark7426]

身為典獄長，看完這段影片並掌握犯人的心理學也同樣重要

[@richardlee635]

每次看李老师讲课，我都有一种梦回学生时代的感觉，我的思绪飞扬到了隔壁班的那个姑娘身上，想着她何时会路过我教室的窗口^_^

[@zhongzhongclock]

别指望了，可以想想那个姑娘的女儿了

[@sanzhang9215]

即便是李老师的课，也不能阻止你想姑娘🤣

[@JH-dy6lg]

池塘邊的榕樹下.......

[@timsecond]

别指望了，人家已经成了村长的新娘

[@Yanagita9]

很喜歡這類益智解題類的題目~~

[@derekmak6204]

黑心獄警那裏要補充一點，一開始要選(我的號碼+x)的盒子。 前面的策略有一個必須條件：環裏包含我的號碼，例如我是1號，我先開1號盒子，環閉合了就代表我最後開的盒子裏裝了1號，所以我的號碼一定在我選的環裏。 但假設我是50號，每次+10，我可能有以下順序： (開50，裏面20)。(開30，裏面60)。(開70，裏面40) 40+10後是50，也就是我一開始的盒子，環閉合了，但我沒有開到裝有50號的。 而一開始選60號盒子，如果環閉合了，就代表我最後開的盒子裏是50號，換而言之，我保證了環裏包含我的號碼。

[@alxu8772]

对，+x的策略可以理解成在每个盒子里的号码m的上面再放一个写着m+x的号码（超过n的要减n）。按上面的号码选盒子。如果我的号码是i， i+x需要出现在环里的上面号码里，也就是要从i+x开始。

[@在你所在的世界]

虽然概率啊公式啊 看不懂。但解题的思路真的是特别好的启发，数学思维，真的是迷人又神奇。喜欢李老师的讲解

[@ztc106]

超級精彩。希望李老師能多介紹一點「隨機算法」或「概率算法」，感謝

[@Kazzit_Chang]

当时看veritasium时候就考虑了下本质，其实就是把随机选择策略在存在51+环路时候微不足道的生存率舍弃，换得在不存在51+环路时候更大的生存率。但是只有一次机会的事情该不该仰仗几率学是一个争论不休的问题。

[@nikochen832]

概率的定义也说了，我只是表示这个概率，并不是说多少次一定发生。

[@HanLi1984]

都是看tradeoff值不值吧？ 就好比1-10000之间抽签。告诉你上上签在1-5000里面有2个中奖签，5000以上只有1个。你会怎么选？全范围还是放弃后5000？ 那前5000有1000个呢？4999个呢？

[@遊戲設計者-節哀順變]

就是轉蛋遊戲的當期主打中獎率兩倍，從1%變2%，你說即使變成2%，我還是有可能抽一千次都抽不到，對，但就是機率問題，至少抽到機率肯定是比1%高的，有趣的是現實生活中我們往往只關注有或沒有0或1，而不去失敗時距離成功的過程到底是遙遠還是接近

[@user-uv6cl7pe6n]

🎯 Key Takeaways for quick navigation: 00:00 🏛️ Issue raised: 100 prisoners need to find boxes with their numbers to be freed, but allowed only 50 tries each. 01:59 💡 With random selection, prisoners have very low chance of all succeeding. 02:28 💡 Strategy: Open own box, then box of number inside, until finding own number. 05:00 🔗 Box numbers will form loops - key to higher success rate. 08:29 📏 Success if no loops longer than 50 boxes. Calculate probability. 14:58 🎯 With strategy, ~31% chance all prisoners freed. 19:55 📈 Doubling prisoners only changes probability slightly. 21:52 🛡️ Prisoners can still succeed if warden tries to thwart strategy. 23:22 🏅 Guard could help ensure success by switching just 2 number cards. Made with HARPA AI

[@olderjiang7070]

李老师你好，我是一名典狱长，感谢你的讲解让我有了新的启发

[@wolfcc2138]

每个囚犯获得有各自的计数设为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为取模)

[@erasersc5509]

所以重点是盒子和盒子里的数字摆放方式有限，不能随便摆放，所以犯人可以通过策略来达到最大成功率而不是完全随机的二分之一的一百次方，但假如规则是100个盒子中只有一个盒子有一张纸条，50次开盒没开到所有人就必死的话，那概率就只能是二分之一的一百次方了

[@shengrongchia6588]

关于后面那题， 首先，选出一个领袖（或者其他什么的，反正选一个人就是了 区分一下，领袖和其他人 然后呢，当游戏开始的时候（灯开着的） 其他人如果看到灯开着，就要关掉， 反之灯关着就不用理 而领袖一定会看灯被人关了，所以就要去开灯 并且 他还需要去数，灯被关了多少次了，如果灯被关了99次，就可以游戏通关了 逃出生天

[@carterzeng5756]

思考题虽然简单，但是李永乐心是真黑啊，不想放人就直说。 解法如下，100个犯人里有一个叫李永乐的狱霸，他负责计数。其他犯人约定每人只有一次机会把灯点亮。如果后一个犯人发现灯是亮的，他不用点亮灯，也不消耗他自己的机会，如果犯人已经点亮过一次灯，他就没有再触碰开关的机会，不管灯亮还是不亮，转身就走。轮到李永乐去放风的时候，如果灯是亮的，他就把灯关了，并且记录一个数字，当李永乐记下99个数字时，所有人都至少碰过一次开关了，下次再轮到李永乐的时候，他就可以大声报告了。我觉得期望至少在100年以上，因为李永乐每年只能期望被放风三次，太难了。

[@chenkarenina4299]

那其实不用这个策略，就按照完全随机状态下计算全放一遍的概率达到90%就直接赌一把算了，也不用100年

[@frankchou5048]

@@chenkarenina4299 是的，10%得概率全体被处死，你说是多关些年好还是10%被处死好呢，好难回答啊

[@super5682]

這種方法我想到的是倘若自己的號碼箱裏不是自己的號碼，那麽自己號碼就肯定不在箱號對應的箱子，順著箱子裏的號碼繼續找下去，就可完全避免開到箱號對應的箱子來浪費機會。

[@kongcher]

当犯人人数很少时： 如果犯人只有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)，或者简化版游戏规定：每次猜测后箱子中球体颜色随机更换，那么单人随机猜测和团队合作猜测的生存率就没什么差别了。

[@遊戲設計者-節哀順變]

你提的簡化版題目比影片中的題目更能讓人理解，感謝

[@BUBU-yq6nt]

谁知道罪犯中有一个卧底。。他没有按照规矩打开盒子，并把纸条又随机摆放了。。。

[@albertxyz]

这个思考题我有几个问题哈： 庭院只有一盏灯 所有囚犯能且只能看到庭院的灯光，显然不能看到点灯的人 放风的人可以在10分钟内随意开关灯 每次放风的人都是随机选出的 每日固定时段放风，非放风时段假设有狱警干预灯光 那这样的话我倒觉得可以用2进制解决吧。囚犯们给自己编上1~100的号，用2进制表示，那么100号为1100100(bin)。以分钟为单位，熄灯代表0，亮灯代表1。比方100号囚犯就可以在10分钟内，以0001100100的形式展示自己的编号（第1~3分钟熄灯，第4分钟开灯，类推）然后所有人都可以得知。 牢房应该有钟吧....哈哈哈哈哈哈

[@chikuwa_2564]

反过来思考更容易理解，首先要明白这里面每一个数都在某一个环里，不管是一个超大的环还是一个自己连自己的环。然后当你选择自己的盒子时，你已经选择了有你那个数的那个环，从而把其他环排除了。

[@str66177]

找到一个直接把号码写在盒子上

[@jchaos8230]

你就换了个说法而已，你反过来个毛线了

[@baiy-cn]

你说的很对，但是有一点我没太理解：就是后面那个 +X 的策略，每个打开自己号码的盒子后，跳转到的下一个盒子是取出号码+10。+10 以后不就很有可能跳出 “有你那个数的那个环” 了么？为什么最后成功的概率仍然不变？

[@chikuwa_2564]

@@baiy-cn +10后就是新的一群环了，可以说是重新洗牌来绕开监狱长故意设置的长环

[@baiy-cn]

@@chikuwa_2564 嗯，我也是这么理解的，但为啥最终成功概率不变，仍然是 30%+ 呢？

[@joelee8857]

1號負責開燈，其他人只能關燈。每人只能關一次燈，當一號開了第100次，表示大家都放風過了。 另外，原題目沒說囚犯不能交換盒中號碼，而且是按照順序進入，那就可以用排序的方式再提高成功率，粗算97/198

[@delza-archipilot]

这个方法不错。不过这个附加题感觉没有能保证的解法。比如楼主这个方法，如果一号只被叫一次，之后再也不叫了，那就会卡住了。。 我有一个更笨的方法，比如可以规定一个数字n，假设n=100。那么每个人都会有自己的专属时间段可以开灯。比如第一个人只能在第一个100天里开灯，第二个人只能在第二个100天里开灯。。每个人在非自己的专属时间段内，唯一要做的就是在这个时间段的第一天关灯，其他天什么都不做。这样在第i个人的专属时间段内，如果第i个人正好放风了，那么在他之后并且在这个专属时间段内放风的人就能得到信息：“第i个人放过风了”。这样一直循环循环。。一直到有个人比较幸运，他收集到的信息正好可以推出所有人都放过风了。 这里n的取值是可以变化的，感觉会有一个最优的n使得期望的等待天数最小。不知道这个方法和楼主的方法比哪个期望值更小？求李老师解答！

[@HRWU]

@@delza-archipilot 如果典狱长按你说的，一号叫一次，剩下99个人循环，或者就两三个人循环交替的放风，剩下的人等到死也轮不到释放了🤭

[@KKK-oi3qb]

@@HRWU 是的，也就是说应该没有解法可以确保在每个人都至少放风一次以后，可以在有限时间内让典狱长放人。只能比较每种解法的平均期望值，看哪种解法更好。

[@CraneZHY]

总感觉还有更好的解法，你这解法不考虑时间成本固然可行，但实际赦免期望都几十年了

[@VerseUtopia]

@@CraneZHY 犯人全部都给自己取名一个号码》 无论如何选中谁都不要开灯 除非1号开始开灯》 1号出来开了灯》 无论如何谁都不要不要关灯 除非2号关灯》 2号出来关了灯》 3号等被选中 。。。 一直到 大家对着灯数到100次开关 （越后面被叫去的人 黑眼圈肯定还黑过熊猫）

[@weiweiwang4603]

讲得很清楚，谢谢！ 作业：假设只有放风的人能看到灯，并且灯在放风的10分钟里可以多次开关。第一个人回来后，在第二个人放风的时候闪灯发送数字99（闪99次，或某种方式编码的99更佳，如2进制1100011）。以后每个人放风时候记录上次的数字，要是自己是第一次放风就把这个数字减1后第二天闪灯发给下一个人。直到某个人放风的时候没有看到灯闪烁，那个人就知道所有人都轮过了。

[@雪岸翔太]

題目應該 從 所有人選都選到自己的號碼獲釋 改成 所有人都選到自己的號碼才全體獲釋 這樣會比較好理解

[@lyg9986]

尝试解答李老师最后的作业：每个囚犯的策略都是当自己是第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，几乎不可能失败。

[@RD-fp3cy]

下一个囚徒发现亮灯报告监狱长， 肯定有下一个囚徒，那么这个点亮灯的囚徒直接报告不就好了么？

[@gashckq4808]

第一個放風的囚犯開燈, 第二個放風的人如果從未放過風的話就把燈關掉, 否則就不要動那盞燈。如是者, 只有第一次放風的囚犯才會改變燈的開與關, 放風超過一次的囚犯都不踫那盞燈。當那盞燈第50次熄滅時, 全部100個囚犯都已最少放過一次風。

[@f1nd592]

課後作業 (改良在留言看到的解法): 100 個人先決定一個天數 m (< 100)，在第 m 天以前，由第一個重複放風的人負責計數並將燈打開，如果在第 k (< m) 天就重複就從 k - 1 開始計，之後到第 m 天放風的人不動燈 ; 如果 m 天都沒有重複就由第 m + 1 天放風的人從 m (自己重複) 或 m + 1 (自己沒有重複) 計，從第 m + 1 天開始如果是第一次看到燈是開的就關燈，直到輪到那個負責計數的人觀察，如果燈是關的就計數 + 1 並開燈，否則就再等下一輪，直到加到 100 結束。 m 可以透過計算發生重複的機率和分析其效益成本決定。 由第一個重複的人負責計數而非事先隨機挑選，可在第一次就決定數個已放風的人數，之後同樣一輪只決定 1 人，一般情況可較原解法花較少時間。

[@WuMingX2]

其實我不懂這題目要做甚麼 也看不懂你要做甚麼 我的解答很簡單： 大家討論時給每個犯人一個編號 每人出去放風時用二進制開關燈發出自己的編號 等所有編號都放風過 報告獄長......

[@f1nd592]

我認為題目的意思是獄長每天隨機選擇人到庭院放風，只有在庭院的人能控制和看到燈，其他在牢房的人並不能在非自己放風的時間看到燈的狀態，也就是說每個人在放風時只能知道前一天燈的狀態資訊和傳遞資訊給下一天的人，如果每個人都能看到燈的狀態的話那太容易了 (很容易地想得到最佳解)，出這問題沒有什麼討論意義而且我不認為獄長會那麼好心，依照老師敘述的題意被關在牢房裡還能看得到位於庭院的燈也不合理 (雖然我們不清楚監獄的結構)。 我看到的原解法是先選出一個人負責計數，當其他人是第一次看到燈是關 (初始狀態) 的就開燈否則維持原狀態，而輪到負責計數的人就觀察燈的狀態，如果是開的就計數 + 1 並關燈，代表確定在與上次放風的期間至少有 1 人是還沒被算到的，直到加到 100 結束 (包含自己)，顯而易見地平均情況需要花很長的時間。 我的改良解法是想試著在第一次計數時就多計一些人，因為一開始隨機選擇而重複的機率偏低，從粗略分析最佳情況和平均情況來看，我想是能預期花比較少的時間確保 100 人都已放風過，當然這跟 m 值的取決有關。

[@WuMingX2]

@@f1nd592 是 我後來看到其他留言了 題目沒說清楚

[@蔡昀珈-d5p]

結尾那題，第一個放風的囚犯為計數員，計數員只關燈不開燈，而且只有計數員能關燈，計數員每關一次燈就計一次數；接著，其它囚犯只要放風時看到燈是暗的，並且自己沒有開過燈，不論自己是第幾次放風，就把燈打開，如果囚犯開過燈了，往後放風時就不要去開燈。這樣子只要計數員關過99次燈，就一定能確保所有人至少放風過一次

[@hyper-sensitivity]

要关到地老天荒了

[@柏言-k6r]

強！👍慢了點但至少是對的

[@udu6172]

计数员到98次的时候突然想到了一个问题：“一开始灯是亮的还是灭的？”然后疯了……

[@oscarlin3555]

這樣他們被放出去的時間期望值是一萬天，大約要被關30年，而且這30年中如果有個沒開過燈的囚犯死了，那就不可能達成了

[@李濬-i8g]

@@柏言-k6r 慢了億點

[@gangwang6830]

盒子里放的是指针，指向指针的指针，指向指针的指针的指针…一个检索取址的计算机算法问题。李永乐讲课真不错

[@TchLiyongle]

谢谢总结

[@张铭信]

@@TchLiyongle 好有意思，想请教一下老师。如果监狱长的设计两个环，一个是51的环，一个是49的环，是不是囚犯就无解了？如果两个环的话，+X的方法好像就不能再使用了，因为这样就又成了新的两个环，而且只有在X为特定值的时候才能使这两个环恰好都是50，但这个值我好像算不出来

[@Eric-b7p]

如果用+X的方法得出來環的數量就不一定是兩個了吧（我不確定是不是我理解錯誤），我認為+X之後環跟原本就完全沒有關係了……所以逃出的機率還是1/3左右

[@张铭信]

@@Eric-b7p 好像还是两个，概率也是31%左右

[@张铭信]

@@Eric-b7p 本质其实是不变的

[@画堂不负光阴久]

这种策略的妙处就在于：在监狱长放好一切号码之后，犯人生死就已经注定。而如果各自随机选，就和抛100次硬币一样，你的生死还由你后面队友的运气决定。

[@一周-y6x]

不一定 就像李老师说的可以订一个加数 开到5号就去开15的盒子 那环就换掉了 所以还是31.2的运气问题 如果监狱长是想要放他们出去没有设计任何一个大于50的环 偏偏囚犯自己定了个加数那么环就又乱了 还是31.2的机会了

[@RangQuid]

老师，有一点您没有说道：怎么证明这是最佳策略呢？如何严格证明没有另一个更好的策略可以把概率提升超过31.2%？

[@ru4red]

頂

[@TchLiyongle]

那好像不好证明

[@no1xtz765]

每人机会都是均等的…就算狱长故意造超过50的环，囚犯用+1就可以打乱顺序去破解，但前提是大家用同一种策略..如果不相同，肯定不优

[@VerseUtopia]

老师像在误导囚犯跳入陷阱。。😂 最佳的得救方式 还是 让狱长要去改变游戏细节，比如增加一些规律在箱子排序， 而不是去用画线排除法 假以为可以提升几率。。

[@ningxie00]

只要链长度超过一半，规则就没用了……

[@madoka-1003]

课后题一个点不太清晰：只有被选中放风的囚犯可以改变灯的状态，但囚犯什么时候可以看到灯的状态呢？ 如果囚犯随时可以知道灯是灭的还是亮的，那每个囚犯第一次放风的时候都去改变灯的状态，当灯一共改变100次状态即可。 如果囚犯只有在放风的时候知道灯的亮灭状态，那就得选一个囚犯出来当计数员。别的囚犯放风如果第一次看到灯是灭的，就有把灯点亮；当计数员每次看到灯是亮的就去把灯灭掉，灭99次即可。

[@albertxyz]

这个题确实是有好多细节：比方是不是连续放风？如果是每天固定时段放风几次的话，会不会有狱警动灯？....感觉条件还是要在捋一捋....

[@Wooder-gg6lj]

這樣只要有一個人被叫去兩次就全滅了吧

[@ericfang5188]

@@Wooder-gg6lj 只有計數員可以滅燈，其他人只有在第一次放風，且燈是滅的時候，才去點亮，避免被重複叫到

[@Tutukun-vn]

我看到一半就在想要是有黑心獄長怎麼辦，沒想到老師還有對策在片尾，還好我每次都是看完整片。

[@wholink6179]

黑心监狱长对策那里不是很懂，如果有长环为什么+10就能解决，概率不仍然是三成吗

[@chrisscofield9261]

@@wholink6179 如果我沒理解錯誤的話,加任何數都能解決哦,因為環的排序就亂掉了,回到31.2%出現不會是原本超過50長度的環

[@yakonghamo1434]

只是在已知按原本策略圈內有大於50的環，所以通過一點小技巧避開人為製造的難題，但即使如此獲救機率確實還是只有30多％

[@whitytsubasa]

@@wholink6179 仍然只有30%沒錯，從0%變成30%。

[@johnsongong915]

萬一監獄長也預判到囚犯會這麼想，只要在櫃子裡放原櫃子號碼加一號，這策略就必死無疑。

[@zhaoliu6117]

对于思考题我觉得可以这样。选一个罪犯，比如1号，负责计数，当灯状态变化（由灭变亮或者由亮变灭）时计数加一。所有囚犯遵循这样的规则：当且仅当自己第一次被选中时，才可以开或者关灯。当计数到100的时候就胜利了。

[@riceberg0413]

感謝老師詳盡的說明計算過程 建議這些囚犯多一個動作 還可再提升生還機率 找到自己的環後 把號碼紙交換到對應的盒中 這樣後續找到自己號碼的犯人還有更多開盒次數去搜出別的環 我想規則沒提到可以幫號碼換盒子是吧^_^

[@riceberg0413]

@Austin Soong 也是可阿 只是機率就沒有參數可供計算 自己賭嚕

[@BeholdYourLordVirtualChoir]

难得把一个复杂的数学问题讲得这么简洁有趣。直觉根据这么一个简单策略就能提高百万倍不太可能。细想问题出在环长都小于五十的情况，和每个人都找到自己的数之间并没有必然联系。比如10到20到30到40到10是一个长度为4的闭环。囚犯是3号，打开箱子里面装着10号，这样囚徒跟着走一圈来到10号。他该怎么办？如果继续按策略走下去，就只能重复转圈。找不到自己。只能更换策略，这样多走几个圈也不一定找到自己。

[@hongliange7705]

对于3号囚犯来说，他的环里面一定要有3号才算是一个闭合的环。所以他不可能会在10，20，30，40再到10的环里，除非他10号的盒子开了两次，否则不重复的开下去一定会有3号的。

[@ZigerMa7]

身為唸computer science畢業的人 這集我覺得非常有趣。。。 腦袋想了一下才懂

[@c_flan]

脑袋想了一下才懂，总觉得有什么问题

[@WuMingX2]

@@ngsaikeong 你別急著裝B 我也CS畢業的 這傢伙說的大概是他沒看李老師的解釋 自己先想 想了一下才懂 :)

[@webber4427]

@@ngsaikeong 我CS1.6畢業的 也是一想就懂 屬實正常

[@WuMingX2]

@@ngsaikeong 我看你是沒有吧 笑死 可憐

[@WuMingX2]

@@ngsaikeong 我會啊 不會的是你吧 在嘴你根本沒文憑在這BB啥呢 聽不懂嗎 還不閉嘴去拿你的文憑 不是很簡單能拿嗎 連張廢紙都拿不起？廢W🤭

[@csonic]

比起數學題本身，李老師的講解方法跟 Veritasium 的對比更有趣

[@huaxingwang2557]

突然发现这个变成一道中等难度的面试题，给定一个长度为n的数组nums，nums[i]=他指向的index，return true如果所有人呢都可以逃离，return false如果不行， n=1e5

[@davidhuang4248]

用龟兔赛跑演算法来求有没有circle

[@roberthsu6228]

看了蠻多留言 基本上課後問題解法都一樣 選一個熄燈人 問題來了 運氣好熄燈人每次去都是亮的 運氣不好有一次不亮就加一百天(平均100天熄燈一次 越後面不亮機率還會越高) 所以9900天完成算運氣好的 仍然需要27年時間 這個方法的效益太低 在隨機抽取的情況下 2年有人沒被抽到的機率是 萬分之6.5 你會選擇兩年賭一波 還是27年穩一波 策略是必定生存 但27年跟基本上跟死了沒差別

[@小咪-h7g]

為了確保都有抽到提高到3年，除非監獄者惡意滿滿不然基本能出去了

[@蘇妃巴爾札克霧崎]

那就是純賭而已啊，也不用有什麼策略，也不用開燈了

[@kevinli256]

另外欧拉公式的部分其实完全可以用微积分算，n到无穷时其实就是1/(1+x)从0到1积分，等于ln 2

[@jizhou749]

通过这期节目，我深深的体会到，老老实实做人，切莫犯罪；认认真真学好数理化，尤其是数学，真的走遍天下都不怕，包括进监狱。😄

[@jchern94065]

数学再厉害，也只有1/3 的生存几率😭

[@yakonghamo1434]

最後的問題 嗯…… 即使不考慮開關燈，光是要所有人都得隨機被抽到一次的最高期望值機率天數就已經需要很長的一段時間

[@WuMingX2]

結果其實獄長從那天開始偷偷把所有人排序然後一個一個叫出去放風 :)

[@無明-q2y]

李老师，想听你讲讲P/NP的问题

[@lesterlau2011]

我想法是 進去的人改變一下燈的狀態 重複的人不做任何動作 累積100次燈開關就可以了

[@leechan3060]

外面的人看不到燈，沒人統計

[@frankgao6138]

理性分析， 就是 用打开盒子里的数 去找下一个 盒子（标记同样的数）去打开， 那下一个盒子里的数肯定不是那个盒子的数。 减少了 发现盒子里是盒子上标记数的概率到0 如此增大了 发现自己数的概率 因为标记有自己数的盒子已经被打开了。

[@林于翔-m2p]

課後問題： 100個囚犯選一個人稱為關燈者，只有他可以關燈。其他人放風的時候看到燈是亮的就不作事，看到燈是關的就把他打開，但一個人只能開燈一次。關燈者出去看到燈是亮的則關燈計次，計完自己以外的99次即為全部人都開過一次燈，符合條件。

[@小嶋茜-k7b]

正解

[@soap2315]

666

[@MarnoGe]

同意

[@chenkarenina4299]

这个计数者一年放风期望三次，每年记三个数，记100次要30年，大家早就刑满释放了

[@百合仙子]

@@chenkarenina4299 所以大家还是别费脑细胞想方案啦，老老实实等刑满释放就行了。

[@一块行尸走肉]

首个人为"关灯员"，只关灯。后面放风都是"开灯员"，每个人都只在，自己第一次"看见关灯"的时候开一次灯，后续不开(每个人只开一次)。直到"关灯员"计数关了99次灯，则认定为全放风过了。耗时多久取决于关灯员能否 穿插着进100次

[@leelee4929]

这是个合理的办法，但是从概率上说，估计要小30年了。不如等个三年五载直接说，那样有人没放风的概率已经小得可怜了。这个题目告诉我们追求完美的边际收益太小了😄

[@ryanye8441]

老师，我觉得有一个内容，您得讲一讲，就是关于“这些解法，都是怎么想出来的” 我听都能听得懂，复述给别人讲也没问题 但是，如果不听，恐怕我一辈子也想不出来 我觉得，这里面肯定有什么玄机。 这解法是怎么想出来的呢？这解法是怎么想出来的呢？这解法是怎么想出来的呢？这解法是怎么想出来的呢？这解法是怎么想出来的呢？

[@albertxyz]

说的没错...不过要想出这些策略，首先要成为一名优秀的数学家。。。。要有充分的知识储备，才能有足够的思路想到最好的解决方案。 李老师有一次讲课提到过，研究新课题，必须是在充分了解前人所作的努力的基础上。否则就会是有点扯淡的事情。。。

[@albertxyz]

哇竟然被李老师点赞了！好兴奋哈哈哈~ 我头两个月刚买了李老师的书给孩子看，我老婆还是您的老乡~~~ 谢谢李老师！

[@RyanTau.3]

最后一个问题：只有第一个人有开灯的权利且奇数日只允许第一个人出去放风开灯偶数日另外99名囚犯随机出去放风关灯并关过灯的囚犯不再出去放风，那这样当第一个囚犯出去放风第一百次也就是所需199天时间就可以全部100名囚犯至少出去放风一次

[@smalltoll]

條件：100天一循環 犯人編號1-100 規則1.自身編號與當天循環天數相同則亮燈不同則滅燈 規則2.前一天的燈為亮則當天才可繼續亮燈 否則則為滅燈 並等待下一個輪迴 規則3.編號100成功完成亮燈 則宣告結束 2>1>3

[@roywang7414]

這... 應該會先老死吧

[@明心-w6x]

师父希望你们要懂得，恭敬才能得到智慧，谦卑才能得到智慧啊。智慧是怎么来的？因为你很谦虚，你非常的谦卑：“不好意思，我不懂，你多跟我讲讲。”人家听了开心就跟你讲了，你不就是学会了吗？学会之后，你不就是拥有别人的知识，变成自己的智慧了吗？否则，你哪来的智慧啊？很多的智慧是人家拥有的，但是你把它学过来了，不就是你拥有了智慧吗？ *不针对任何 人和 事 ，仅分享善言，感恩宽容！

[@WuMingX2]

實際上的情況：1號跟100號盒子裝的都是87號牌 然後全員處死 死無對證🤪

[@junsongli1815]

怎么出现两个87号，这样犯人肯定会拿到证据并举报，监狱长也会判刑的。

[@WuMingX2]

@@junsongli1815 都死了 誰舉報？:)

[@yen1245]

@@WuMingX2 我是不看題目的人　我智商低　誰舉報

[@徐瑞斌-i8o]

在獄長作弊的情形下， 打亂有一種最直觀的方法， 就是將盒子編號用亂數重排。

[@TheXuism]

这是两个概率问题：一个是排列固定，囚犯按照这个链表法有1/3的排列能逃出生天。一个是不管排列，囚犯随便猜，机会几乎为0.

[@CharlesWong6]

有一個問題：只要沒有長度大於50的環，那一定成功，這一點沒有問題！ 可是如果有一個長度大於等於51的環，只要所有囚犯開始選的盒子，也就是在環中起始進入點距離目標的距離，小於等於50，那還是會成功，而這個以隨機來說應該也有一定的機率。所以現實中實際成功機率，應該還是比31.2%高一些。以最長環=51來說，出現的機率是1/51, 所以李老師直接減去1/51, 這個不對！！ 其實只有其中至少一人開始選的盒子距離真正目標距離大於等於51，才會失敗，所以不失敗的機會是所有這51人，選的距離目標小於等於50, 也就是失敗機率是(1-(50/51)^51), 也就是原始成功機率不是 1 - 1/51 - 1/52 ... - 1/100 而是 1 - (1/51)*(1-(50/51)^51) - (1/52)*(1-(50/52)^52) - ... - (1/100)*(1-(50/100)^100) 比本來李老師的31.2% 高一些。計算結果大概 32.3%

[@niay79]

其實，只要監獄長藏起一個號碼，人人都必須處死😅

[@black0pudding]

陰間

[@拉雞毛]

藏起一個號碼 那監獄會暴動啊

[@奇怪的知識減少了]

那處死犯人的藉口不就更多了嗎

[@蓝蓝刘]

@@拉雞毛 但是囚犯以为自己失败了😃

[@軒軒-s7t]

藏起一個號碼代表會有一個號碼重複啊，全部人中有最少一個人開到兩個一樣的機率近乎100%吧

[@nevermind-sl2vx]

15:32 第二次回來看的時候靈光一現 "指定去開盒子裡面的號碼", 相當於我們所有人都進行了一次溝通 所以通關機率就會比隨機開的時候更高了 即使你不知道你想告訴別人甚麼, 但已經有人幫你決定好要說甚麼了w

[@甘納北棲]

最後典獄長設計超過50的長環那裡的破解方法有點疑問，若是每個號碼都加10，那開到91以上號碼的人，加10就超過100了，那是否就只取後兩位數就好呢？例如：91+10=101開1號箱，100+10=110開10號箱這樣~

[@zzzzzz522002]

那是當然，否則1到10永遠不會被打開

[@fentoyal]

最后的问题太不清楚了。 1. 谁能看到灯？ 如果所有都能看到庭院的灯，那只要规定每个人只能碰一次灯，然后大家就数灯改变过几次状态即可。 2. 每次放风能开关几次灯？如果可以多次，那每人编个号，每次用灯的亮灭来二进制传递自己的号码，更简单。甚至直接摩斯码群聊都可以。。

[@kaiwensun]

给小朋友出一道思考题: 如果题目不是要求k>50，而是要求k>49，也就是说每个囚犯最多能打开51个箱子。那么这种策略的的存活概率是多少呢？如果k>48或者k>47呢？k>0呢？

[@learnfromdata3660]

卧槽 大佬

[@ryoyan1128]

自己代公式OwO

[@gukahn4003]

@@ryoyan1128 李永乐老师那个公式只适用于k>50的情况。

[@operaitve]

只要囚犯第一次被放風，就把燈開關一次累加進累積的總初次放風人數，否則把燈開關一次至累積的總初次放風人數，直到哪天發現燈明暗了100次就可以出獄了。例如：第3個初次被放風的人就把燈明滅3次，之後有另一個前兩次就被放風的人（非初次放風者）又被放風，則仍然把燈開關3次，直到登連續明暗100次即為成就。

[@kevinzhang1221]

非常喜欢老师的视频，涨知识，练脑子。有两个问题，随机拿对的概率好像应该是（1/50）100次方，拿了号码之后如果不放回去不是空了吗？😄

[@koaw4792]

我想前提是要把牌子放回去吧,不然鏈子也會斷,方法自然也沒用了吧

[@bingxizhang7849]

那如果某一个囚犯虽然挑选的号码箱的环小于50，但这并代表这个环一定会包含该囚犯的号码牌啊。比如有四个环，每个环均有25个箱子，简称为A环，B环，C环，D环，3号囚犯的号码牌是存在D环内，但如果该囚犯寻找的顺序为A环再到B环再到C环最后再到D环，那么他就会失败，求解答。

[@dreamingfor]

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?

[@bcsa8079]

Big problem for this solution:that guy has to get pick 100 times when it’s a 1/100 chance everyday

[@chiweilee1168]

nice solution

[@huiiheng]

说到最后如果囚犯的号码不在那小于50的环，又或者里边有多个环例如十个环一个环的大小不一样或一样都好如果囚犯的号码不在哪总数为50的环里，到头来其实概率也是一样，换个方法开盒都会多产生几种影响因数，而如果把这些被“无视”的因数的概率相乘应该会得像开头老师说的概率

[@alexjjkuo1234]

視頻最後的問題解法: 100個囚犯商量好, 當自己是第一次被放風時要去切換開關, 第二次以後就不要動開關了. 這樣大家各自在牢籠裡數燈開關次數, 滿100次就表示大家都放風過了

[@nerd1900]

每个牢房能不能看到这个 灯？ 题里没说， 如果看不见的话呢？

[@居住的街道风]

@@nerd1900 那是不是要假设有n个牢房看不到灯。m个牢房看得到灯。100-m-n个牢房可能看得到灯，可能看不到灯。

[@木添白]

錯誤，你選的可能是另一個環，100可分兩個環。

[@木添白]

最好的策略，機會是50％。

[@Mr.Isaac-L]

​@@木添白 有100%的策略，也不需要能看到灯，但是需要相当长的时间。 第一，约定好只有一号囚犯能够关灯，其他人只能开灯但不能关灯。 第二，对于其它囚犯而言，如果放风时看到的灯是开着的，就不管，看到灯是关着的，就打开，而且只操作一次。 第三，轮到一号囚犯放风的时候，如果灯是打开的，就关上，并在心里记录数字加一，如果灯是关着的，就不管它。 这样等一号囚犯数满了99次关灯以后，就可以报告典狱长了。 当然对于能看到灯的情况，就不一样了，会快很多。只要数开关灯的次数就行了。

[@gospurs7424]

第一次出来放风：当一个囚犯第一次被放风时，他打开灯。这是一个共同遵守的初始规则。 后续放风：一旦一个囚犯已经被放风过一次后，当他后续再次被放风时，他不打开灯，而是把灯关掉。 计数者：囚犯们约定一个特定的囚犯作为计数者。计数者的任务是在每一天晚上检查庭院里的灯是否被打开。 计数：每当计数者看到灯被打开，他就会将计数器加一。 判定：当计数器累计到100时，计数者就可以确定所有囚犯都至少被放风了一次。因为每个囚犯第一次被放风时都会打开灯，而后续的放风不再打开灯，所以当计数器累计到100时，就表示有100个囚犯都至少被放风了一次。

[@UU-235]

于北辰说它的爱三防空导弹拦截成功率有70%，发三枚就能有210%的成功率，我竟无言以对。。。

[@langwu6448]

思考题好像做过类似的，先商定好只有一个人能够开灯，假定是1号。 策略是所有人都等1号放风，然后1号把灯打开。 那么第一次开灯就是1号放风。然后99名囚犯后面进来了，就关灯。而等1号开灯后如果再放风，发现灯关了，就数+1并且再开一次灯。而前面关过灯的囚犯再也不参与开关灯了。只需要1号观察到99次关灯，那么就等于所有人都放风过了

[@feyfey88]

李老师是神一般的存在

[@JS-dx3yp]

找一个人负责关灯，其它99人只在第一次看到灯灭灯时候开灯， 其它情况不碰灯。 由关灯人负责数他自己的关灯次数， 数到99就可以宣布了。 请李老师计算一下狱长放任的时候太阳系还存在吗？

[@zhuyaobushiyao]

这个是比较容易懂的策略，每个囚犯都能简单操作。那么有没有更复杂的运算策略使得成功概率提高呢？

[@manaphylv100]

最后的问题关键在于谁能看见灯。 如果大家都能看见灯，所有第一次被叫去的人闪一下灯即可。已经去过的人别动灯。记住灯被闪了多少次，到100了就汇报。 如果只有去的那一个人能看见，那就只有第一个被叫去的人才能开灯，其他人只有第一次去才能关灯。只有开灯者开了98次（或99次，如果灯开始是灭的）后而且见到灯是灭的才能汇报。（这不太现实。如果100人随机抽签，一天抽一个，100年也未必能成功。）

[@oscarlin3555]

最後的問題： 第一個放風的囚犯把燈點亮，之後每個放風的囚犯如果是第一次去放風就改變燈（亮的變暗的 暗的變亮的）第二次或以上就不動，只要第五十次亮起的燈熄滅了，所有囚犯就能釋放

[@user-a33kixd2wq41]

好像行得通，不过应该没这么简单吧？我读得书少，不要忽悠我啊！

[@HRWU]

不行吧…再下一个囚犯无法得知上一个囚犯把灯熄灭前的再上一个囚犯是否曾经点亮过这盏灯。更不要提计数了，你每次出去只会看见一盏亮着或者灭着的灯。

[@楓紫-y5j]

不要自行擴充題意，題目只說庭院可以看到燈，牢房看不到

[@oscarlin3555]

@@HRWU 我有說第二次或以上放風的時候不改變燈號 所以你提的情況照樣行得通

[@HRWU]

@@oscarlin3555 阅读疏忽了，抱歉🙏

[@tatata20818]

第一個A出去時打開開關 之後所有其他人第一次出去看到燈亮就關掉 已經被關了就不動 每一個人只有第一次出去要動開關，其他就不動 下一次這個第一個人再次出去，看到燈暗了，就再打開燈 以此類推，等到他count到人數次-1開關之後就代表所有人都出去過了，即可以回報

[@ffal6521]

最后的问题，我想可以用李老师以前讲过的一个编码+二进制的方法解决。

[@abcrui]

片尾的题，事先约定好，指定一个人计数，如果此人有幸被防风，发现是开灯状态，则计数+1。对于其他99人的要求就是，如果出去发现灯是关闭状态，则开灯，如果灯是打开状态，不要去碰。如果改变过一次灯的状态后，以后出去就不要再碰灯了。如此，当计数达到99时，则可判定所有人都被防风过。若事先灯的状态未知，则需计数达到100。

[@hengsun2776]

还有一个关于这个问题的拓展思考。不管什么策略，单个囚犯的找到自己号码的概率总是1/2。所以要提高所有囚犯找到自己号码的概率，必须提高他们找到自己号码的相关系数。本题解法使得在号码在一个闭环（长度小于51）里的囚犯有百分之百的相关系数。所以整体概率大大提高。这个概率肯定小于1/2。请问上限是什么？本题解法是最优的吗？

[@ningzhixie4818]

上限就是1/2。因为在没有额外信息的情况下总成功（找到自己号码）人数期望是50。最理想的就是100个人要么全成要么全不成，概率各1/2。视频解法是否最优这个证明就比较复杂了，我没想到

[@zhenggu4517]

除了放风的囚犯，其他囚犯在牢房里都应该看不到灯，只能按下开或关灯按钮；囚犯可以约定1号囚犯在他曾经被放风的情况下只能按一次开灯，其他囚犯只能关灯按钮，是在没有被放风的情况下按并且必须按2次以上间隔1分钟，防止比1号开灯提前按了关灯，这样当某一天放风的囚犯发现灯一直亮着，就可以报告全部被放风过了

[@jinjinlou5108]

课后作业文字版： 有一个监狱里有100名囚犯关在100个单独的牢房里面，每天晚饭之后监狱长会随机的选出一个囚犯在庭院里进行单独放风10分钟，在庭院里有一盏灯，囚犯们可以控制这盏灯，变亮或者变灭，有一天监狱长发善心，把囚犯们聚集到一起宣布说：我现在把庭院里的灯熄灭，然后从现在开始计算，如果某一天有个囚犯告诉我说所有的囚犯都至少被放过一次风了而且的确如此，那么所有的囚犯都将被释放，但是如果报告错了的话那所有的囚犯都会被立刻处决。现在，所有的囚犯可以聚集在一起商量一个对策然后就不能再见面或者交流了，那么囚犯们应该采用什么样的策略才能保证自己会被释放呢？

[@Ronald_Wilson_Reagan]

把10個人為一組分成10個隊伍，每個隊伍成員各自得到1-9的編號，當天放風完的人用長燈報隊伍號、短燈報編號，再等到所有人的燈號都出現過在申請釋放😂

[@miaotai]

摩斯密码 over

[@miaotai]

@@Ronald_Wilson_Reagan 你自己都说了长短了 就不能直接摩斯密码么

[@fgghcggh9394]

链表检测，环：表示一个链表中是否存在相同的元素，若存在，表示这是一个环形链表。 不过，哪里会有好心的狱长，会让狱友知道这个环在哪。如果，我是那个黑心的狱长，会直接设置无环。那么， 这个好心的狱友，只有可能是狱警走漏了消息！

[@张铭信]

好有意思，想请教一下老师。如果监狱长的设计两个环，一个是51的环，一个是49的环，是不是囚犯就无解了？

[@gamedier]

那囚犯只要打開盒子內號碼+n(n⋳N n

[@张铭信]

@@gamedier 不会，你会发现必然会再次出现两个环，一个大于50一个小于50很难做到正好是50两个环，李永乐老师好像只考虑到一个51的环，剩下的随机

[@mu416]

@@张铭信 李老師的跳號解法確實是只考慮到一個較長的環

[@张铭信]

@@mu416 请问您怎么看我的提问

[@whitytsubasa]

@@张铭信 請問一下，+n之後應該未必還會是兩環吧？

[@sohigh-vo2vu]

100个囚犯选一个人作为观察者，观察者每次被放风的时候只观察灯的状态但不去碰开关，而其他人，只在第一次轮到放风的时候去拨动一下开关。每次轮到观察者去放风的时候发现灯的状态跟上一次观察的状态不同了，计数器就加1（因为灯的初始状态是关的，所以如果观察者第一次放风就发现灯是亮的，计数器就直接加1）。当观察者的计数器达到99的时候，观察者就可以告诉监狱长，所有人都至少被放风过1次了。

[@nightstrigiformes]

毕业以后：数学屁用没有，每天都是看领导脸色。看完李永乐老师的视频：老子要用数学拯救世界。

[@千面侠]

然后世界教你，你先救你自己吧

[@joshuapeng831]

做蛋糕可以，分蛋糕no。

[@王六爻]

每個人都先開自己的號碼， 如果是自己的號碼，就放回去。 如不是自己的號碼，就將錯的號碼放到正確的箱子裏，再將裡面的號碼拿出來 放到號碼指定的箱號。第50次，將錯誤碼放回空箱子中。 如此操作，第一個人最多可拯救49人。 最終，每個人號碼都在自己箱子裏面

[@fredd12356]

好有道理，典狱长没说不能移动号码的位置哈哈哈

[@Peter-r4h9q]

就囚犯中選一個點燈人 其他人只要是第一次放風的就滅燈 讓點燈人記數，只要數到99(因為去掉自己) 那就代表所有人都放風過

[@chankay9585]

不行 設囚一代表第一次放風的人, 燈代表點燈人. 要是出現 囚一 囚一 燈 點燈人只能記一次數 他永遠不能數到99

[@CabbageCube]

@@chankay9585 你好像理解錯題目了

[@CabbageCube]

nice喔！不過監獄長一開始是把燈熄滅，所以反過來應該比較快，選一人當滅燈人，其他人第一次放風若燈是熄的就點亮，原本是亮的就不動。當滅燈人滅了99次燈就可以報告了。

[@black0pudding]

平均來看得被關9900天吧

[@voidxvoid]

@@black0pudding 會先老死。 27年

[@CabbageCube]

nice喔！不過監獄長一開始是把燈熄滅，所以反過來應該比較快，選一人當滅燈人，其他人第一次放風若燈是熄的就點亮，原本是亮的就不動。當滅燈人滅了99次燈就可以報告了。

[@a09836101]

覺得你才是正解 雖然這題我在好幾年前聽教授說過XD

[@waiwong5998]

平時口袋都放著李老師，生存機率就會大大提升

[@ouo1456]

估计还没求神拜佛 来得几率大，遇到危机证明倒霉，倒霉是一种超越知识的存在，比如飞机。火箭，在怎样检查 总有意外发生，这就是倒霉

[@ouo1456]

倒霉理论是超越任何的存在，运气什么的都没倒霉厉害

[@HRWU]

思考题的表述有点奇怪，也可能是我太咬文嚼字：庭院里的灯，囚犯们在各自的牢房看得到吗？毕竟只是说囚徒们无法互相见面而已。如果能，把灯光开关当作信号灯就解决问题了。问题变成如何发信号。如果不能，当我没说…那就很复杂了，毕竟可以让某一个人连续n天放风，如果每人都连续放风一年，囚徒们等到死也无法被释放… 如果这样可以把问题稍微精简一下，其实就变成： 100个囚犯开同一个装有灯泡的箱子，每天随机选某一人开一次箱，初始灯泡熄灭，开箱者可以选择改变或不改变灯泡的亮灭，n天后的某一人通过天数、开箱时灯泡的状态、还有预先约定好的规则，判别是否之前所有人至少开箱一次，如果是则报告，如果不是则不报告。求如何优化这个规则和判别条件。

[@jerry8liu]

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.

[@jerry8liu]

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.

[@whitytsubasa]

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.

[@jerry8liu]

@@whitytsubasa Interesting condition. The light is the only communication channel in this question. Without it, there is no way to signal other inmates.

[@Cookie-sg7lt]

@@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.

[@helloworld1707]

@@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

[@ymyfish]

（假设灯在广场上大家都能看到）：每个人如果自己是第一次防风就改变灯的状态，如果是第二次或者以上就不改变灯的状态。灯第100次被改变状态的那天就都放过一次风了。

[@joecomets8654]

"我要是懂这么多就不会坐牢了“

[@whitytsubasa]

這世上還有冤獄、意外傷害等等各種情況，監獄也不是設計來關笨蛋的。

[@flash-xx3eh]

最后的问题，也是概率问题，没有实打实的把握。因为其他人看不到灯的变化，也看不到别人放风的次数，而且时间是有限的，因为人是有寿命的。所以问题解是，100人中选个1号，选个2号。一开始是暗的，然后所有去放风的人都不开灯，1号第一放开灯，2号放了关，1号再开，2再关，1再开，2号第三次看到灯，就可以宣布了。极大概率。

[@xyaries]

第一个放风的囚犯自动成为灭灯人，他第一次放风的时候让灯保持灭的状态，今后他只要看到灯亮就灭掉。 其他囚犯成为亮灯人，当他放风时看到是灭灯的状态就点亮灯，看到是亮灯状态就不操作。点亮一次灯后就再也不操作灯了。 当第一个放风囚犯数够灭掉99次灯的时候，就说明所有囚犯都点过一次灯了，也就是都放过风了。

[@69-]

这个得一万年

[@xyaries]

@@69- 哈哈哈

[@JJLulu-xl6wv]

逻辑清晰👍

[@icefox99]

总觉得提出问题的那个美国科学家有点眼熟，查了下原来Robert Sedgewick就是著名的算法第四版的作者。😂

[@卖仔蛙]

相对而言，对应李老师这种策略最好的方法就是1-100都对应下一个号码，这样又回归了50-50了。