百囚问题（二阶）

l4m2

100个囚犯讨论对策，之后国王随机选择6个人编号，反复掷骰子并将一个开关送到该编号囚犯面前让他观察并允许修改状态。如何最小化成功需要的平均时间？（下面几项都不允许出现错误报告）
1. 若有人报告“所有人看过开关”
2. 若所有人报告过“所有人看过开关”
3. 若有人报告“所有人报告过‘所有人看过开关’”

可行性我会证，如果合适，我之后发

KeyTo9_Fans

题目太简洁，导致我不知道“100”这个参数有什么用？

保险起见，6个人没完没了地投骰子，投足够多轮，收集到足够的证据，再来报告。这样啥时候才会轮到其余的94人出场呢？

l4m2

KeyTo9_Fans 发表于 2022-11-1 09:35
题目太简洁，导致我不知道“100”这个参数有什么用？

保险起见，6个人没完没了地投骰子，投足够多轮，收 ...

100人选6是为了强迫策略一致的，确实具体是10还是100没啥区别

KeyTo9_Fans

开关只有2种状态，太难搞了，我目前试了很多方案，平均时长都是无穷大。

坐等楼主发布平均时长为有限大的解。

要是 开关的状态数>参与报告的人数，好像就好搞很多了。

要是 开关的状态数>参与报告的人数的2倍，好像直接就有平凡解。