抛硬币的最佳策略

KeyTo9_Fans

有$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

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

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

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

056254628

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

056254628

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

056254628

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

wayne

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

KeyTo9_Fans

这题跟毒酒没有关联吧。

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

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

猜想$2$：$f(3)$是无理数（更一般地，当$N>2$时，$f(N)$都是无理数）。

KeyTo9_Fans

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

KeyTo9_Fans

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

$f(3)=4.64346552636429900821528012160745797688045626990934...$

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

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

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

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

AAAAA

这题跟毒酒没有关联吧。

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

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

这个方案具体内容是什么？