验血问题

铯_猪哥恐鸣

相传二战期间美国流行某传染病，其感染率为p（远小于一），这时刚好有人发明了一种仪器，只要有该病毒的存在，无论多么稀就能检测出病毒来，即对于一堆人，可以将他们的血混一起输入仪器，只要有一人干扰，仪器就会检测出阳性，若都没感染则显示阴性。现在有N（远大于一）个人报名入伍，需要进行该传染病的检测。问，军方应使用什么样的策略，使得最终期望的验血次数最少？

Paracel_007

概率问题最让我头疼了…

superacid

对这题不一定吧

flwb

优选法,黄金分割,0.618

铯_猪哥恐鸣

回8楼，还有更优的想法吗？

ynjyht

人均验一次或分为K组验。
N个人平均验血的次数：N(1-q^k+1/k)
取(1-q^k+1/k)最少。。。

铯_猪哥恐鸣

回7楼，不确定噢，其实是有很小的概率所有人都感染的。
当然也有一定概率没人感染

[ 本帖最后由 铯_猪哥恐鸣 于 2010-4-12 19:42 编辑 ]

dkjiaoyang

个人认为没有总体测一次的必要，顶多开始测一半

dkjiaoyang

设：除了每人一次的最慢方法外，每人的血样需要X次测试。将人分为K组。
视X为随机变量，则X的分布列是（K^-1，1+K^-1；q^K，1-q^K），其中q=1-p
每人平均化验次数E_X=上述分布列对应的矩阵的值=1-q^k+k^-1
则只需要E_X＜1，即比每人单独化验要节省次数
PS：目前还没有想出更优解法~~~

[ 本帖最后由 dkjiaoyang 于 2010-4-12 23:36 编辑 ]

phileas

初步想法：计算N*p，把人均分成 [N*p]+1 或者 [N*p]+2 份 （如果N*p的小数部分大于 0.5，则取[N*p]+2，否则取 [N*p]+1）。
然后测试一下，按照数学期望，有至少一份是检测出来完全健康的，然后把剩下的人并到一起，继续均分。