百囚问题之【点灯猜数字】
国王招来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 抛砖引玉:
我们可以使用27比特表示不超过$10^8$的所有整数,由于囚犯们可以提供99比特信息,可以将27比特的信息重复三次,并且最后再任意添加指定的18比特信息。
如果灯灭用0表示,灯量用1表示,那么最后统计结果时,把对应的比特与操作,得到正确结果的概率为$(1-1/16)^18(1-1/8)^9=9.4%$.
虽然概率不高,但是比瞎猜好多了 由于初始状态如果灯是灭的状态,是不会出错的,只有灯是亮着的状态才会出错,所以每个比特的错误率要再低一倍,上面的结果正确率应该是$(1-1/32)^18(1-1/16)^9=31.6%$ 楼上的方案可以继续优化:
前面的$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%$
还有更好的编码方法吗? 如果把$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%$。
还有更好的编码方法吗? 方法看上去不错,可以蒙特卡罗法试验一下看看。
由于$99/e \approx 36$,99个比特里面选择36比特的不同选项约$10^27$,随机选择$10^8$个这样的数,出现冲突的概率会非常低,所以随机选择即可。
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】
还有很大的优化空间。
有没有可能不采取随机编码的方式,而是精心地设计这些编码,使得胜率更高呢?
页:
[1]