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

KeyTo9_Fans

虽然现在还不知道如何证明最高的逃生概率为$64%$，但是可以证明一个弱一点的命题：

记人数为$N$，灯数为$m$，那么只有当$N\leq 2^m$时，才能以$100%$的概率逃生。

证明如下：

根据题目设定，灯的状态是唯一可以用来做决定的因素。

记$m$盏灯一共有$M=2^m$种状态，我们用$i=0, 1, 2, ..., M-1$来表示这$M$种状态，

于是每个人的策略都是一个从【状态】到（【状态】，【回答】）的函数：

$f: M\rightarrow(M,a)$

例如，某个人的策略如下：

如果出来的时候，看到房间里的灯处于状态$0$，就回答“不是”，然后改成状态$1$，
如果出来的时候，看到房间里的灯处于状态$1$，就回答“不是”，然后改成状态$2$，
如果出来的时候，看到房间里的灯处于状态$2$，就回答“不是”，然后改成状态$3$，
……
如果出来的时候，看到房间里的灯处于状态$62$，就回答“不是”，然后改成状态$63$，
如果出来的时候，看到房间里的灯处于状态$63$，就回答“是”，然后改成状态$0$，

那么这个策略可以用以下函数来描述：

$f(i)=((i+1) mod 64,a(i))$

其中：$a(i)=$

$0 (i\ne 63)$
$1 (i=63)$

#####

我们将每个人的策略记为$f_1, f_2, f_3, ..., f_N$，初始状态记为$0$，

要想$100%$逃生，那么第$1$个人看到状态$0$，必须要改成非$0$状态：$f_1(0)\ne(0,*)$，

因为如果第$1$个人看到状态$0$而不去改变，

那么对于以下$2$个序列：

$1, 2, 3, 4, ..., N$
和
$2, 3, 4, ..., N, 1$，

第$N$个人将看到相同的状态，却要分别回答“是”和“不是”，于是无法以$100%$的概率逃生。

记第$1$个人看到状态$0$，改成状态$s_1$，

于是第$2$个人见到状态$s_1$，必须要改成$0$和$s_1$以外的状态，

因为如果改成状态$0$，那么对于以下$2$个序列：

$1, 2, 3, 4, 5, ..., N$
和
$3, 4, 5, ..., N, 1, 2$，

第$N$个人将看到相同的状态，却要分别回答“是”和“不是”，于是无法以$100%$的概率逃生。

如果改成状态$s_1$，那么对于以下$2$个序列：

$1, 2, 3, 4, 5, ..., N$
和
$1, 3, 4, 5, ..., N, 2$，

第$N$个人将看到相同的状态，却要分别回答“是”和“不是”，于是也无法以$100%$的概率逃生。

记第$2$个人看到状态$s_1$，改成状态$s_2$，

于是第$3$个人见到状态$s_2$，必须要改成$0, s_1, s_2$以外的状态，

因为无论改成状态$0$，$s_1$，还是$s_2$，都能类似地找出$2$个序列，

使得第$N$个人面临相同的状态，却要分别回答“是”和“不是”，于是无法以$100%$的概率逃生。

综上所述，每出来$1$个人，都要将灯改成新的状态，不能和以前的任何一个状态重复，否则无法以$100%$的概率逃生。

但是当第$M$个人出来后，无论如何修改，都会和以前的某个状态重复，

所以当$N\geq M+1$时，无法以$100%$的概率逃生。

证毕。

#####

以上讨论是$f_1, f_2, ..., f_N$都是确定的函数的情况。

如果某个人需要抛硬币来决定【状态】或【回答】，

那么【在他看到灯的时候抛硬币】，和【在大家商定策略的时候，就把每种状态要抛的硬币抛好，把每个人的策略确定下来】，逃生概率是相同的。

=====

例如，在楼主的设定（$N=100$，$M=64$）下，【大家都把状态$+1$（$mod 64$），看到状态$36$就抛硬币回答“是”或“不是”】的策略，

跟【大家先抛好硬币，把看到状态$36$的回答确定下来】的策略，逃生概率都是$25%$。

（与其这样，还不如选定$50$个人，看到状态$36$就回答“是”，其余$50$个人看到状态$36$就回答“不是”，逃生概率为$50/100 * 50/99 =25.25%$，反而更好。）

=====

所以只需讨论$f_1, f_2, ..., f_N$都是确定的函数的情况，无需讨论不确定的函数。

#####

如果能在此基础上，证明这个命题：

记人数为$N$，状态数为$M$，最佳逃生概率为$p(N,M)$，那么当$N>M$时，我们有$p(N,M)\leq (N-1)/N * p(N-1,M)$，

那么就说明$64%$就是最佳的逃生概率了，此题就完美解决了。