百囚问题之【你是最后一个出来的吗？】

dianyancao

这个办法很好啊，到最后一个囚犯时，他可能已经肚子饿或者想睡觉了

平常心

这个办法很好啊，到最后一个囚犯时，他可能已经肚子饿或者想睡觉了
dianyancao 发表于 2013-5-5 15:38

当一个人面临生死关头时，还这样的好心情，难得。

zgg___

考虑了这个问题良久，倾向于认为64%是最好的结果了。
对于这个问题，可以确定的事实如下：
1、固定策略将不会比随机策略差，即最优策略一定是某种固定策略。所谓固定策略就是当囚徒看到灯的状态后，他的举动是固定的；而随机策略是囚徒看到灯的状态后，他的举动带有随机性。如果某个随机策略是最优的，那么，去掉随机性的对应策略也一定是最优的。
2、问题和6个灯的状态编码策略是无关的，即问题可以转化为对于m=100个囚徒和n=64个可变状态(n<=m)，某囚徒正确回答他恰好是第k=100个出场的人的最大概率P(m,n,k)是多少？
3、在感觉上，P(m,n,m)=n/m。
因此，此题可以更加复杂一点，就是求P(100,64,81)。
即变成如下问题：（照抄1层的，呵呵。）

国王招来100个囚犯，对他们说：你们犯了死罪，理应判处死刑。但我今天决定开恩，给你们一次逃生的机会。你们稍后将会被分开地关在100个房间里——1个房间只关1个人。这些房间都是密闭的，在里面无法获得任何外界的信息，直到房间门被打开——我会按照某种顺序【注1】，一个一个地打开你们的房间。每打开一个房间，该囚犯都会被带到一个特殊的房间——这个房间里有6盏灯。最初的时候，6盏灯都是灭的。看了这6盏灯之后，该囚犯必须回答该问题：“你恰好是第81个出来的吗？”如果答错了，那么逃生失败，全体杀头。如果回答的是“否”，而且答对了，那么该囚犯可以改变若干盏灯的状态——点亮或者熄灭，然后回到自己的房间。除了灯的状态之外，该囚犯在该房间里留下的任何痕迹都会被清除，如果回答的是“是”，而且回答正确，那么逃生成功，全体无罪释放。现在你们可以商量怎么办，若干时间过后，你们将会被完全分开，接受生死考验。
注1：一共有 100*99*98*...*1 = 100! 种顺序，国王按照任何1种顺序打开房间的概率都是相等的，均为 1/100! 。
这100个囚犯希望活命的概率尽可能大。
问：最佳策略是什么？最大的活命概率是多少？

平常心

最优策略一定是某种固定策略。
如果整个测试的过程基本上是连续的，而且在一个相对较短的时间内结束。可以得到百分之百逃生固定策略。因为：“我今天决定开恩，给你们一次逃生的机会。……按照某种顺序，一个一个地打开你们的房间。”
当然如果过程的连续性有很大破坏、时间拖延得很长，这样的策略不成立。不过，这似乎违背了题目的本意。

gxqcn

13# zgg___


原本以为“81”是随手写的一个数字，但稍作推敲一下：64+(100-64)/2=82，
而“81”是一个远比“82”更让人浮想联翩的数字，而它们又是如此接近。

经此扩展，问题确实更复杂了。

注：我第一次看到本帖，误读成了“你是最后一个想出来的吗？”，还以为是道普通的简单的智力题呢。

wayne

我也以为标题是“你是最后一个想出来的吗”。

标题党伤不起啊

shshsh_0510

考虑了这个问题良久，倾向于认为64%是最好的结果了。
对于这个问题，可以确定的事实如下：
1、固定策略将不会比随机策略差，即最优策略一定是某种固定策略。所谓固定策略就是当囚徒看到灯的状态后，他的举动是固定 ...
zgg___ 发表于 2013-5-7 14:05

前两点我同意,第三点感觉的不同意(虽然我一直钦佩zgg的感觉 )
第一点事实并不显然,但是可证的,大致思路是给每个人对每个状态设一个转移概率,然后解出一个人对一个状态的p,由独立性,证明其极值可以在区间[0,1]的端点达到

第3点之所以不同意,是因为我认为这和人数比例相关.
首先,灯状态反映了一个进程的进行程度,所以每个人都应该使他沿同一顺序前进,否则是没有好处的
然后,当到达了最后状态,该使用什么样的策略,这应该和人数有关.
这相当于将100-64=36个球,放到65个格子中,然后求最后一个格子的球数的期望.对于65个格子,36个球,最后一个格没球的概率很大(不到60%),所以才让最后一个人来说他是最后一个,否则,就不一定了,比如总共10000个人,6盏灯

无心人

关键没法从其他外部因素确定第N种状态是否是第二次出现
预测间隔我以为是无效的，因为你看不到国王放人的间隔，否则，根本不需要灯来记录状态

zgg___

To shshsh_0510的17层：
呵呵，对于第三点，我没法证明，也没有找到反例。
对于6盏灯10000个人的情况（或者是其他的比例），有没有存活几率大于64/10000的方案来做为反例呢？

gogdizzy

考虑了3个人1盏灯的简单情况，我也觉得64%是最好的概率了。

那些随机的策略似乎总是浪费了一些信息，反而不如确定性的策略。

也考虑了假如一部分人在计数上+n1,一部分人+n2...一部分人+nk，如果总数恰好是64的倍数就说自己是最后一个，发现还是不如分成A、B，一部分+1，另一部分+0好。因为越多种可能到64的倍数，正确概率越低。