数学研发论坛

 找回密码
 欢迎注册
查看: 330|回复: 6

[原创] 百囚问题之【点灯猜数字】

[复制链接]
发表于 2020-9-29 22:50:40 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
国王招来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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-10-1 10:04:14 | 显示全部楼层
抛砖引玉:

我们可以使用27比特表示不超过$10^8$的所有整数,由于囚犯们可以提供99比特信息,可以将27比特的信息重复三次,并且最后再任意添加指定的18比特信息。
如果灯灭用0表示,灯量用1表示,那么最后统计结果时,把对应的比特与操作,得到正确结果的概率为$(1-1/16)^18(1-1/8)^9=9.4%$.
虽然概率不高,但是比瞎猜好多了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-10-1 11:06:11 | 显示全部楼层
由于初始状态如果灯是灭的状态,是不会出错的,只有灯是亮着的状态才会出错,所以每个比特的错误率要再低一倍,上面的结果正确率应该是$(1-1/32)^18(1-1/16)^9=31.6%$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-10-2 00:00:05 | 显示全部楼层
楼上的方案可以继续优化:

前面的$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%$

还有更好的编码方法吗?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-10-7 20:06:04 | 显示全部楼层
如果把$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%$。

还有更好的编码方法吗?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-10-8 08:28:34 | 显示全部楼层
方法看上去不错,可以蒙特卡罗法试验一下看看。
由于$99/e \approx 36$,99个比特里面选择36比特的不同选项约$10^27$,随机选择$10^8$个这样的数,出现冲突的概率会非常低,所以随机选择即可。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-10-22 13:07:20 | 显示全部楼层
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】

还有很大的优化空间。

有没有可能不采取随机编码的方式,而是精心地设计这些编码,使得胜率更高呢?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2020-11-26 14:47 , Processed in 0.066021 second(s), 16 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表