关于三神谜题,改版
数学吧
全部回复
仅看楼主
level 6
原题如下:
有三个神,一个只说真话,一个只说假话,一个随机说话(变化之神)
你可以问三个问题,每个问题只能问一个神问谁都行。问题只能以是和否作答,不能问悖论
同时你只知道ozo和ulu里一个是是一个是否,但不知道哪个是哪个
怎么问才能知道三个神谁是谁
这个题本身不难,大概是这样的思路:通过“如果我问你xx命题是真是假,你会回答ozo吗?”的方式,既规避掉了语言不通的问题,又可以无视真神假神直接得到xx命题的真答案。
所以通过第一个问题排除掉变神,第二个问不是变神的那个得到一个身份,第三个问题再问一次得到第二个身份,即可通关
但我现在想知道:
如果有四个神(两个变神),最少需要几个问题才能得知四人的身份?
如果有n个神,是否具有某种公式算法,得知最少需要几个问题。
这个我确实不会了。想不太明白怎么在4个里排除掉2个变神。我的直觉告诉我是6个问题,但我不知道怎么证明或者能不能证明。也不知道对不对,对的话怎么问(
n神n-2变,直觉感觉是1到n-1的等差数列求和,比如5神3变是10个问题。似乎是1+2+...+n-2个问题排除变神,然后连问n-1个问题确认身份。但我不知道是不是对的
2023年09月05日 13点09分 1
level 8
可能有点跑题,我想到了一个可以给出一个提问下界的方法(毕竟
lz
在找上界),至少需要n/2次提问,因为不管你提出任何问题,你都无法排除目前跟你对话的是变化之神的可能,因为你提的问题和他给的答案是完全无关的。n个神一真一假总共有n(n-1)种分布方案,每次提问,你可以排除的可能性不超过“与你对话的神是真神or假神”的总排列数也就是2n-2,所以如果你想确定每一个神的身份至少需要提问n/2次
写完想了一下这个估计过于粗糙了可能没什么意思吧
2023年09月05日 19点09分 2
level 1
有的,我以前考虑过这个问题。
有a个真神,b个伪神,c个变化之神,一共Z个神(a,b,c>0),在最坏的情况下,至少要问几个问题才能把它们都区分开?
设至少要问X个问题才能把它们都区分开。
①,当c≥Z/2时,此题无解。
②,当c=1时:X=x1+x2。x1=1,x2=F1+F2。
F1=Z-1,F2=Z-MAX(a,b)-INT[(Z-1)/2]-1。
所以X=2Z-MAX(a,b)-INT[(Z-1)/2]-1。
③,当1<c<Z/2时:X=x1+x2。
x1=(2c+1)×(c-2)+(2c+1)×1
x2=F1+F2。
F1=Z-(c-2)-1。
F2=Z-(c-2)-MAX(a,b)-1-1。
所以X=2c^2+2Z-3c-MAX(a,b)。
这是我的答案,c=1和1<c<Z/2时的情况都有一点点复杂,比较难想。
2025年10月06日 02点10分 4
帅的,但是为什么。比如5神2变2真1假,具体应该怎么问呢?
2025年10月06日 08点10分
@轻蹈云巅♬ 先随便选个神1,然后对这5个神都问同一个问题“如果我问你神1是变化之神,你会回答O吗?”,其实就相当于5个人投票表决,只要非变化之神数量大于变化之神,就可以根据大多数人的答案知道神1是否是变化之神。
2025年10月06日 08点10分
@轻蹈云巅♬ c>1时,然后我们要找到第一个非变化之神,我们要计算一下,运气最坏的情况是什么情况,即何种情况下,提问数最多。 我们会发现,最坏的情况是,在投票表决第(c-1)个神时才找到第一个非变化之神,这时整体的提问数最多,所以我们只需计算在这种情况下的最少提问数即可。 找到第一个非变化之神,后面的提问策略就比较简单了。
2025年10月06日 09点10分
@轻蹈云巅♬ 如果你问我,为什么在投票表决第(c-1)个神才找到第一个非变化之神是整体提问数最多的最坏的情况。那么你得先把c=1时的情况和最优提问策略搞清楚然后才能比较。 这是我以前算的,我记得最坏的情况好像比第二坏的情况整体只多了1个问题(好像是这样,也可能记错了)。[吐舌]
2025年10月06日 09点10分
1