不妨设有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. 搞定。
*博客内容为网友个人发布,仅代表博主个人观点,如有侵权请联系工作人员删除。