数学无处不在——血液检测的数学模型和理论
作者：胡旭东，中国科学院数学与系统科学研究院研究员
作者简介：胡旭东，中国科学院数学与系统科学研究院，研究员，博士生导师，中国运筹学会理事长。1985年毕业于清华大学，获应用数学专业学士学位，1989年毕业于中国科学院应用数学研究所，获运筹与控制论专业博士学位。自1989年始，一直在中国科学院从事运筹学的理论研究和教学工作，主要研究方向为组合优化、网络博弈、近似算法。2012年被评为第五届“全国优秀科技工作者”，2016年获“中国科学院朱李月华优秀教师奖”。
今年国际日的主题是“数学无处不在”。这是因为数学在我们日常生活的几乎每个领域都发挥着至关重要的作用：从自然模式到气候科学，从医学成像到搜索引擎，从运输网络到 AI 的优化，从建模到流行病的控制等。它扩大了“圆周率日(以前在3月14日庆祝)”的范围，涵盖了整个数学领域乃至整个世界的各个方面。
近日，全国上下都还处在抗击疫情的阶段。这两个多月以来，大家持续在关注新冠肺炎确诊病例数，也知道确诊病例时需要进行核酸检测，而且每一次检测既需要花费时间也需要花很多钱。
一
下面我就给大家介绍一下与血液检测相关的数学模型和理论：如何应用数学的方法，用最少的成本（检验次数和时间），在大量的血液样本中准确地检验哪些是阴性的（好的），哪些是阳性的（坏的）。
在第二次世界大战期间，美国政府因战事需要征集了大量的年轻人参军。在征兵过程中需要体检，其中一个环节就是验血，用来筛查出应征参军的报名者中携带淋病病毒的年青人。通常的筛查方法是采集血样以后，对它们一个一个地进行检测，我们不妨称为「逐一检测法」。1943年 R. Dorfman 为美国公共健康服务和筛选服务系统设计了一个「组合检测法」[1]：
首先，将所要检测的个样本中的每一个样本都分成两部分（类似于现在兴奋剂检测采用的A瓶和B瓶方法）； 然后，将个A瓶样本分成组，每组5个血液样本充分混合，得到了个样本； 最后，将个样本组，每一个组每一个组进行检测。
这样检测一个样本组可能出现的结果：
某一个样本组显示是阴性的，那么说明该组样本中的每一个样本都是好的。这样我们通过检测1次就确认了5个样本都是阴性的，从而比逐一检测法少用了4次。 某一个样本组显示是阳性的，那么说明该组样本中至少有一个样本是不好的，但是不清楚哪一个或者哪几个是阳性的；因而需要对该组中5个样本的B瓶，进行逐一检测以便确认每个样本是阴性还是阳性。这样我们通过检测6次可以确认5个样本是阴性还是阳性的，比逐一检测法多用了1次。
不难看出，如果在所有样本中阳性的比较少，那么组合检测法会减少大量的检测次数；而这正是当年征兵进行血液检测时的情形（现在每年高考学生进行体检时也类似）。可是如果在所有样本中阳性的比较多，那么组合检测法很有可能不仅不会减少检测的次数，还会增加检测的次数。
由此就自然地产生了一个数学问题：什么时候组合检测法可以减少检测的次数，什么时候不可以呢？1960年P. Ungar 对这个问题进行了研究[2]。他假设所需检测的个样本有个是阳性的，其中；每组可以包含任意多的血液样本（不再限定最多5个样本），而且每一个样本可以重复使用（一个血液样本可以分装在很多瓶子里）。在这些假设下，他证明了如下定理（大意是：当少于 的样本是阳性的时候，组合检测法平均需要的检测次数比逐一检测法需要的检测次数少）：
R. Dorfman 和P. Ungar 等人对血液检测问题的研究激发了很多后续的相关研究，很多有意思的数学模型和方法也先后被提出来，并逐渐形成了一个研究方向：组合检测/搜索。下一节我将给大家介绍这个方向中一个非常有趣的数学猜想。
二
上一节讲到，1943年 R. Dorfman提出了一个组合检测法[1]：将若干个样本放在一起进行检测。如果检测结果显示是阴性的，那么这个组里的所有样本都是阴性的；如果检测结果显示是阳性的，那么再将这个组里的样本逐一检测。1960年P. Ungar 对这个问题进行了研究[2]。他考虑的是一种「概率模型」：假设所需检测的个样本有个是阳性的，其中每一个样本可以有很多备份，每组可以包含任意多的血液样本（备份）。在这些假设下，他证明：当时，组合检测法平均需要的检测次数比逐一检测法需要的检测次数少。
应用实践和理论分析都表明，当大量的待检测样本中坏的样本不是很多时，比如，高考考生体检验血，或者新兵入伍复查体检验血，组合检测法比逐一检测法需要的检测次数要少。
今天我来介绍「组合模型」：假设事先已经知道所给的个样本中有个是阳性的，其中。（未经检测就知道有个是阳性的，这个假设不合理，是吧？我将在下一次介绍当这个假设不满足时，如何设计组合检测法。）下面先考虑最简单的情形，看看组合检测法好呢？还是逐一检测法好呢？
当时（只有1个样本是坏的），可以二分技巧快速检测到这个坏的样本，亦即将个样本尽量平均分成两组A和B，先检测A组；
如果A组的检测结果显示是阳性（意味着B组中的样本都是好的），那么再将A组中的样本尽量平均分成两组A1和A2，并检测A1组…… 如果A组的检测结果显示是阴性（意味着A组中的样本都是好的），那么将B组中的样本尽量平均分成两组B1和B2，并检测B1组……
上面的图示给出了用组合检测法对个样本的检测过程，检测开始前已知只有1个是坏样本，但是不知道哪一个样本是坏的。可以看出：当样本3是坏样本时，用2次检测就可以找到它；但是其他情况都需要3次检测。经过简单的计算可知：基于二分技巧的组合检测法用次检测一定可以找到那个坏的样本。
上面的图示给出了用逐一检测法对个样本的检测过程。可以看出：当样本1是坏样本时，用1次检测就可以找到它；但是当样本6或者7是坏样本时，则需要6次检测。显然，逐一检测法需要次才能确保找到那个坏的样本。
另外，当时（只有1个样本是好的），此时使用组合检测法是没有任何意义的，因为将任意两个样本放到一起进行检测，（不用检测就可以推断出）结果一定是阳性的，所以逐一检测法是最好的。
上面是两个最极端的情形：只有一个样本是坏的，或者只有一个样本是好的。前一种情形，组合检测法最好，后一种情形，逐一检测法最好。下面我们来考虑非极端的情形。比如，，，采用组合检测法7次检测就可以了（建议你自己试一试），比逐一检测法用的检测次数少一次。而当，，你会发现采用组合检测法需要8次检测才可以，与逐一检测法用的检测次数是一样多。
经过上面的初步分析，我们自然就会提出如下的数学问题：
❝
什么时候组合检测法比逐一检测法用的检测次数少？亦即，给定个样本，并且已知其中有个样本是坏的，当不超过多少时组合检测法用的次数少于?
❞
1971年F. K. Hwang（黄光明）研究了上述问题[3]。他将上述问题称为「Group Testing Problem」，并用 表示最优检测法所需次数。显然，当不等式取等号时，就表示逐一检测法是最优的。他证明：当时，，亦即，若已知有以上的样本是坏的，则逐一检测法是最好的。
1981年F. K. Hwang等通过进一步的研究[4]，证明：当时，，亦即，若已如有以上的样本是坏的，则逐一检测法就是最好的。同时，他们提出了如下猜想：
❝
Hu-Hwang-Wang 猜想:当时，。
❞
上述猜想成立意味着：若已知有以上的样本是坏的，则逐一检测法是最好的。
1982年D.-Z. Du（堵丁柱）与F. K. Hwang合作对上述猜想进行了研究[5]。他们证明：当时，，亦即，若已知有以上的样本是坏的，则逐一检测法就是最好的。尽管已经非常接近，这个结果也已发表近四十年了，但是至今还未出现更好的结果。「Hu-Hwang-Wang 猜想」已成为了组合检测/搜索研究方向的一个著名难题。大家有没有兴趣挑战一下？
下一节我将给大家介绍一下，当我们得到了个（血液）样本，但不知道关于它们的任何信息：既不知道好的样本多还是坏的样本多，更不知道究竟有多少个是坏的样本，我们又该如何设计组合检测方法呢？
参考文献
[1] Robert Dorfman, The Detection of Defective Members of Large Populations, The Annals of Mathematical Statistics, 14 (4)(1943), 436-440.
[2] Peter Ungar, The Cutoff Point for Group Testing, Communications on Pure and Applied Mathematics, XIII (1960), 49-54.
[3] F. K. Hwang, A minimax procedure on group testing problems, Tamkang Journal Mathematics, 2 (1971), 39-44.
[4] M. C. Hu, F. K. Hwang and J. K. Wang, A boundary problem for group testing, SIAM Journal on Algorithms and Discrete Methods, 2 (2) (1981), 81-87.
[5] D.-Z. Du and F. K. Hwang, Minimizing a combinatorial function, SIAM Journal on Algorithms and Discrete Methods, 3 (1982), 523-528.