抛硬币的最佳策略

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.643392$时，$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

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