查看: 227906|回复: 14

验血问题 [复制链接]

铯_猪哥恐鸣

银魔

Rank: 7 Rank: 7 Rank: 7

积分: 3923
帖子: 2556
精华: 6
UID: 15558
性别: 保密
WCA ID: 2008CHEN27
兴趣爱好: 理论

电梯直达

1^#

发表于 2010-4-12 19:01:04 |只看该作者 |倒序浏览

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

收藏0

使用道具举报

yanzi7816

红魔

Rank: 4

积分: 1038
帖子: 843
精华: 0
UID: 1250957
性别: 男

2^#

发表于 2010-4-12 19:03:54 |只看该作者

吓我一跳。我还以为是广告....

2010.02.18入魔！提速关键：观察、连贯性。

使用道具举报

superacid

银魔

Rank: 7 Rank: 7 Rank: 7

积分: 2520
帖子: 3072
精华: 7
UID: 62890
性别: 男

3^#

发表于 2010-4-12 19:14:32 |只看该作者

占楼思考中..

19events = 644days
PB (2 3 4 5)B = 1200seconds
北大魔方爱好者QQ群74893945
mf8最少步讨论群：RP与公式的绝佳配合QQ群5652935

使用道具举报

speedz

蓝魔

Rank: 2

积分: 233
帖子: 214
精华: 0
UID: 74598
性别: 保密

4^#

发表于 2010-4-12 19:17:10 |只看该作者

先总体测一次，然后分组，这样逐渐分细？

[ 本帖最后由 speedz 于 2010-4-12 19:19 编辑 ]

使用道具举报

夜雨听风

铜魔

♂鉦版宅娚ミ

Rank: 8 Rank: 8

积分: 10831
帖子: 9358
精华: 1
UID: 90305
性别: 男

5^#

发表于 2010-4-12 19:18:16 |只看该作者

the same to 3L

哥拧的不是魔方，是寂寞
“人生就好比魔方，要想好下一步该怎么走”
魔方吧-福建超级群：63887957
玩魔方就是玩个低调

使用道具举报

铯_猪哥恐鸣

银魔

Rank: 7 Rank: 7 Rank: 7

积分: 3923
帖子: 2556
精华: 6
UID: 15558
性别: 保密
WCA ID: 2008CHEN27
兴趣爱好: 理论

6^#

发表于 2010-4-12 19:21:02 |只看该作者

开放性问题，我自己都没找到答案，就像某个找女朋友问题一样，无法判断是不是最优的

使用道具举报

phileas

白魔

Rank: 1

积分: 80
帖子: 65
精华: 0
UID: 107099
性别: 保密

7^#

发表于 2010-4-12 19:29:59 |只看该作者

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

使用道具举报

dkjiaoyang

粉魔

Rank: 5 Rank: 5

积分: 3752
帖子: 3175
精华: 1
UID: 1245673

8^#

发表于 2010-4-12 19:32:51 |只看该作者

设：除了每人一次的最慢方法外，每人的血样需要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 编辑 ]

使用道具举报