Dr. Ecco’s cyberpuzzles:36 puzzles for hackers and other mathematical detectives
作者： (美)丹尼斯·夏沙(Dennis E. Shasha)著;周立彪译
出版社：湖南科学技术出版社,2005
简介：昂贵的安全血液
麦克斯·雅各医生穿着运动夹克、打了一条领带，但脖子上挂着听诊器
。他一一打量了我们几秒钟。“小姐，我希望你不是容易呕吐的人，”他对
ll岁的莲恩说，“我们要谈的是血。”
“人血，还是蝾螈血？”莲恩咧嘴笑着问。
雅各医生微笑着：“蛮机灵的。艾可博士，还有教授，我待会儿要提的
问题就需要几点机灵。你们大概知道，C型肝炎这种病会令患者变得非常虚
弱，而且会经由输血传染。检验C型肝炎的方法叫作ⅡJSA检验法，这种检验
法不够精确，既给我们错误的阳性反应(良质血液被认为是劣质的)，也给我
们错误的阴性反应(劣质血液被认为是良质的)。有一种以聚合酶连锁反应(p
olymerase chain reaction，PCR)为基础的技术，很昂贵但较为精准。这种
技术准确到如果50 000袋不同的血液中只有l袋感染C型肝炎，取一滴血就能
检测出来。
“我们中心每天收到100 000袋的血”这些血液有将近l％感染这种疾病
，我们希望以不超过20 000次的检验，查出是哪些血液受到感染。但每检验
一次要花2小时，而我们希望每一袋血液的命运都能在4小时之内决定。你们
能不能帮我们解决这个问题？”
“必须做到精确？”莲恩问，“我的意思是，如果你不在乎有些良质血
会和劣质血一起被扔掉，那么我们根本不需要检验，全仍掉就好。”
“你干卫生行政这一行前途看好，”雅各医生咧嘴笑着回答，“首先，
请设定你的前提为每扔掉1袋劣质血，一起扔掉的良质血不能超过2袋。”
“我们先试试每袋血液在决定其命运前，只能做1次c型肝炎检验(2小时
)。”艾可提议。
电脑新手题：继续往下读之前，看你能不能找_出方法，以不到35 000
次的检验得出结论，而且，假定有1 000袋劣质血，你的方法不能扔掉超过2
000袋的良质血。每袋血液的命运必须在大约2小时之内决定。
“好主意，叔叔，”莲恩对艾可说，“嗯，因为有1 000袋劣质血，而
我们允许2 000次错误的阳性反应，所以我们把这些血液每3袋一组分成33
333组，还有l组l袋的，同组的血液一起检验。有1 000组各含1袋劣质血，
这1 000组都是3袋一起扔掉。”
1 电脑新手题：如果有4小时可进行检验，而且100 000袋中有l 000袋
劣质血、可以扔掉2 000袋良质血，莲恩能以不到12 000次的检验完成任务
。你能做到什么程度？
“如果不得失误的话，又如何？”
2 电脑新手题：莲恩能以20 000次检验达到4小时零失误的要求。你能
吗？
