新闻  |   论坛  |   博客  |   在线研讨会
验血问题进阶 (answer)
shadowind | 2008-07-26 21:22:44    阅读:788   发布文章

不妨设有1024个人, 分成 16 个组,每组 64 人,
分组化验 16 次,得到 N (N <= 10)组不合格 

下面将每组 64 个人再分成 32 个人的两个小组,这样一共得 2N 个小组 
编号为 1...2N,其中(2*i-1)号与(2*i)号同属一个 64 人的大组,i=1..N 
  
对 N 讨论: 
N = 10 : 
    逐一化验所有的奇数小组,若奇数组合格,则对应的偶数组必不合格, 
    若奇数组不合格,则对应的偶数组必合格。
    故只需化验10次即可判明所有2N个小组的合格情况,并得到 10 个不合格小组 
N = 9 : 
    逐一化验所有的奇数小组,若奇数组不合格,将其选出,
    若奇数组合格,则对应的偶数组必不合格,将偶数组选出。
    这样化验 9 次后选出了 9 个不合格小组,
    还剩下 9 个小组,其中至多有一个小组不合格,
    可至多用 5 次化验查出这些小组的合格情况,
    并保证最多的混和血样人数为 32*3 < 100 (详细过程在后面叙述)
    这样共化验14次即可判明所有2N个小组的合格情况,并得到 9或10 个不合格小组 
N = 8 : 
    同样的办法,化验 8 次后选出了 8 个不合格小组,
    还剩下 8 个小组,其中至多有两个小组不合格,
    可至多用 6 次化验查出这些小组的合格情况,
    并保证最多的混和血样人数为 32*3 < 100 (详细过程在后面叙述)
    这样共化验14次即可判明所有2N个小组的合格情况,并得到8,9或10个不合格小组 
N <= 7 : 
    逐一化验各小组即可得到所有不合格的小组,化验次数为 2*N <= 14 次, 
    得到不合格的组数 <= 10 
  
综合上面的讨论,无论何种情况,我们都可在 14 次内验明所有 2N 个小组的合格情况,
并得到不多于 10 个的不合格小组(每组32人),这就又回到了和开始时相类似的情形 
  
于是同样的,我们再将每组32人分为16人的两个小组,
仍用类似的办法,可化验 14 次,得到不多于 10 个的不合格小组(每组16人)。

如此再做4次,可得到不多于 10 个的不合格小组(每组1人),即得。 
  
总化验次数不超过 16 + 14*6 = 100 

最后,我们来说明如何至多用5次判明9个小组(至多一个不合格小组)的合格情况 
及如何至多用6次判明8个小组(至多两个不合格小组)的合格情况 

设 9 个小组编号为1,2,...,9,其中至多有1个不合格
验(1,2,3) 若不合格,则再分别验 1,2,3 即可
          若合格,验(4,5,6),若不合格,则分别验 4,5,6 即可
                             若合格,则分别验 7,8,9 即可
检验次数不超过5次,最多的混和血样人数 32*3 < 100

设 8 个小组编号为1,2,...,8,其中至多有2个不合格
验(1,2,3) 验(4,5,6)
若都合格,则再分别验 7,8 即可
若都不合格,则再分别验 1,2, 4,5 即可
若有一个不合格,不妨设是(4,5,6)不合格
    验(7,8),若合格,则再分别验 4,5,6 即可
             若不合格,则再分别验 4,5,7 即可
检验次数不超过6次,最多的混和血样人数 32*3 < 100
          
ok. 搞定。

*博客内容为网友个人发布,仅代表博主个人观点,如有侵权请联系工作人员删除。

参与讨论
登录后参与讨论
推荐文章
最近访客