百囚问题之【点灯猜数字】

KeyTo9_Fans

国王招来100个囚犯，对他们说：你们犯了死罪，理应判处死刑。但我今天决定开恩，给你们一次逃生的机会。你们稍后将会被分开地关在100个房间里——1个房间只关1个人。这些房间都是密闭的，在里面无法获得任何外界的信息，直到有人把一张纸条递进来——我会在纸条里写一个1亿以内的正整数【注1】，然后叫人依次递到99个房间里。收到纸条的囚犯会被告知是第几个收到该纸条的，然后该囚犯可以根据纸条上的数字，把房间里的灯点亮或者熄灭，然后离开房间，去一个特殊的房间等候。除了灯的状态之外，原房间里留下的任何痕迹都会被清除。当99个囚犯都离开了原来的房间之后，我会叫人对这99个房间里的灯做点手脚：若灯是灭的，则不做任何改变；若灯是亮的，就抛硬币决定这盏灯的最终状态——如果抛到正面，则不做改变——让这盏灯继续亮下去；如果抛到的是反面，就把这盏灯熄灭【注2】。此后，我会叫人把没有收到纸条的囚犯按照递纸条的顺序依次带领到那99个房间里查看灯的状态，然后猜纸条里的数字是多少。如果猜对了，那么逃生成功，全体无罪释放；否则逃生失败，全体杀头。现在你们可以商量如何尽可能地猜对纸条上的数字。商量好之后，你们将会被完全分开，接受生死考验。

【注1】国王选取任何一个正整数的概率都是相等的，均为 1/100000000。
【注2】这是一枚正常的硬币，抛到正面或反面朝上的概率都是1/2。

这100个囚犯希望活命的概率尽可能大。

问：最佳策略是什么？最大的活命概率是多少？

相关贴子：百囚问题之【你是最后一个出来的吗？】
https://bbs.emath.ac.cn/thread-4993-1-1.html

mathe

抛砖引玉:

我们可以使用27比特表示不超过$10^8$的所有整数，由于囚犯们可以提供99比特信息，可以将27比特的信息重复三次，并且最后再任意添加指定的18比特信息。
如果灯灭用0表示，灯量用1表示，那么最后统计结果时，把对应的比特与操作，得到正确结果的概率为$(1-1/16)^18(1-1/8)^9=9.4%$.
虽然概率不高，但是比瞎猜好多了

mathe

由于初始状态如果灯是灭的状态，是不会出错的，只有灯是亮着的状态才会出错，所以每个比特的错误率要再低一倍，上面的结果正确率应该是$(1-1/32)^18(1-1/16)^9=31.6%$

KeyTo9_Fans

楼上的方案可以继续优化：

前面的$72$个比特分成$18$组，每组$4$位，$0000$表示$0$，$1111$表示$1$，可表示$2^18$个数，正确率为$(1-1/32)^18$

后面的$27$个比特分成$9$组，每组$3$位，$000$表示$0$，$111$表示$1$，只需要表示${10^8}/{2^18}=382$个数。

如果想提高正确率，我们要尽可能少用$1$，所以优先使用$0$较多的$9$位二进制数来表示这$382$个数。

巧合的是，$C_9^0+C_9^1+C_9^2+C_9^3+C_9^4+C_9^5=1+9+36+84+126+126=382$，

所以我们只需要用不超过$5$个$1$的那些$9$位二进制数，就可以表示这$382$个数。

正确率为$(1-1/32)^18*(1*1+9*(1-1/8)+36*(1-1/8)^2+84*(1-1/8)^3+126*(1-1/8)^4+126*(1-1/8)^5)/382=34.18%$

还有更好的编码方法吗？

KeyTo9_Fans

如果把$10^8$个数都随机编码，使得那$99$个比特都是相互独立地以$p$的概率取$1$，以$(1-p)$的概率取$0$，

那么对于国王选取的数，平均情况下会点亮$99*p$盏灯，

被人做过手脚之后，平均情况下会有$49.5*p$盏灯留下。

由于猜数的囚犯一开始的猜数范围是$10^8$个数，

而其他那$99$个囚犯点的灯中，每有一盏灯留到了最后，就可以把猜数范围缩小$1/p$倍，

而平均情况下一共有$49.5*p$盏灯留下，因此平均情况下可以将猜数范围缩小至原来的$1/p^{49.5*p}$倍，

猜对的概率大约为$1/{1+(10^8-1)*p^{49.5*p}}$，

（精确的猜对概率需要用泊松分布的公式计算）

当$p$取$1/e$时，猜对的概率达到最大。

用泊松分布的公式计算得到该概率值约为$46.96%$。

还有更好的编码方法吗？

mathe

方法看上去不错，可以蒙特卡罗法试验一下看看。
由于$99/e \approx 36$,99个比特里面选择36比特的不同选项约$10^27$,随机选择$10^8$个这样的数，出现冲突的概率会非常低，所以随机选择即可。

KeyTo9_Fans

5楼的分析做了如下假设：

【如果有多个数字对应的编码与看到的亮灯匹配，则在所有匹配上的数字里面随意瞎猜一个。】

这一步还可以继续优化，定义最佳匹配：

我们知道，数字对应的编码与实际亮灯有以下关系：

编码中的 0 对应的灯一定是灭的，编码中的 1 对应的灯可能是亮的，也可能是灭的。

最佳匹配就是指该数字对应的编码里面，所有的编码 0 对应的灯都是灭的，并且编码 1 对应的灯中，灭的盏数最少。

猜数的时候，总是猜最佳匹配。如果最佳匹配还不止1个，就在最佳匹配里面随意猜一个。

例如，最后灯的状态是010。假设与这个亮灯匹配的编码有110和111这两个，那么就猜110对应的数字，不猜111对应的数字。

因为编码111与灯状态010有2位不同，编码110与灯状态010只有1位不同。根据最佳匹配原则，猜只有1位不同的编码110对应的数字。

实验表明，按照最佳匹配原则进行猜数可以大幅提高胜率。

编程模拟5组1亿个数的随机编码（每位编码独立地以1/e的概率取1，(1-1/e)的概率取0），每组编码随机抽取1万个数进行模拟，结果如下：

10000局胜8692局，胜率86.92%
10000局胜8738局，胜率87.38%
10000局胜8752局，胜率87.52%
10000局胜8710局，胜率87.10%
10000局胜8684局，胜率86.84%

平均胜率：87.152%

#####

虽然胜率大幅提高了，但总感觉这里：

【每位编码独立地以1/e的概率取1，(1-1/e)的概率取0】

还有很大的优化空间。

有没有可能不采取随机编码的方式，而是精心地设计这些编码，使得胜率更高呢？