KeyTo9_Fans 发表于 2011-7-25 23:18:17

抛硬币的最佳策略

有N枚硬币,看起来是一样的。

其中1枚有问题,抛到正面朝上的概率是2/3。

其余$(N-1)$枚正常,抛到正面朝上的概率是$1/2$。

请你通过抛硬币试验将有问题的硬币找出来。

要求:
——————————
正确率达到$50%$即可。

每次只能抛$1$枚硬币。

抛硬币次数的期望值尽可能少。
——————————

求抛硬币次数的期望值$f(N)$。

例$1$:
——————————
当$N=1$时,$1$次都不用抛,正确率$100%$。

所以$f(1)=0$。
——————————

例$2$:
——————————
当$N=2$时,也是$1$次都不用抛,正确率$50%$。

所以$f(2)=0$。
——————————

对于更大的$N$,情况比较复杂,看谁给出的方案最佳。

KeyTo9_Fans 发表于 2012-1-31 16:19:04

当$N=3$时,$3$枚硬币各抛$3$次,然后取正面朝上次数最多的那枚,如果有并列第$1$的,则任取$1$枚。正确率为$50.057%$。

一共抛了$9$次,说明$f(3)<=9$。

我认为,一定还有更好的方案。

056254628 发表于 2012-1-31 21:00:51

我的一个方案:
将三枚硬币从前到后排列。
先扔最前面的一枚,若连续两次正面,选中该硬币;若连续两次反面则淘汰;一正一反则把该硬币放在最后面,继续前面的操作,直到剩下一枚硬币或选中一枚硬币为止。
计算成功率和步数期望有些复杂。
编程模拟一下上述过程约一千万次。
平均约5.3505752步得到结果,结果的正确率约为0.5017258。
希望各位大拿计算我的方案是否正确。

056254628 发表于 2012-2-1 14:35:32

计算3楼的方案:
得精确值:
抛硬币次数的期望值=1699/336=5.0565476190476190476190476190476(跟计算机模拟的有差距)
                正确率=1349/2688=0.50186011904761904761904761904762

056254628 发表于 2012-2-1 15:27:03

重新计算,得抛硬币次数的期望值=599/112=5.3482142857142857142857142857143
这下对了。
按照3楼方案,$f(3)=599/112$,正确率=$1349/2688$

wayne 发表于 2012-2-3 11:26:56

把那一枚坏的硬币当做毒酒。其他的没有毒,讨论一下 看怎么组合最好

KeyTo9_Fans 发表于 2012-2-5 22:16:36

这题跟毒酒没有关联吧。

我找到了一个方案,平均要抛$(4.64343\pm 0.00004)$次硬币,正确率恰好为$50%$。

猜想$1$:该方案是最佳方案,我们有$4.64339<f(3)<4.64347$。

猜想$2$:$f(3)$是无理数(更一般地,当$N>2$时,$f(N)$都是无理数)。

KeyTo9_Fans 发表于 2012-2-11 21:03:11

经过了$10^11$次模拟,结果为$f(3)=4.64347\pm 0.00001$。

KeyTo9_Fans 发表于 2012-3-27 22:04:59

通过高精度计算,得平均抛硬币次数为:

$f(3)=4.64346552636429900821528012160745797688045626990934...$

其中,正确率恰好为$50%$。

但愿我的算法和代码是正确的。

能找到一个精确到$f(3)$的前$50$位小数,且分子分母的位数在$20$以内的分数吗?

如果不能,则几乎可以肯定$f(3)$是无理数了。

AAAAA 发表于 2012-3-28 08:54:53

这题跟毒酒没有关联吧。

我找到了一个方案,平均要抛$(4.64343\pm 0.00004)$次硬币,正确率恰好为$50%$。

KeyTo9_Fans 发表于 2012-2-5 22:16 http://bbs.emath.ac.cn/images/common/back.gif

这个方案具体内容是什么?
页: [1] 2
查看完整版本: 抛硬币的最佳策略