数学无处不在——血液检测的数学模型和理论（最终篇）
作者：中国科学院数学与系统科学研究院 胡旭东
继续给大家介绍与血液检测相关的数学模型和理论：如何运用数学的方法，用最少的成本（检验次数和时间），在大量的血液样本中准确地检验出哪些是阴性的（好的），哪些是阳性的（坏的）。
上接
五
前四次我先后讲了四个模型，
概率模型：假设事先已经知道所需检测的个样本中有个是阳性的，其中； 组合模型：假设事先已经知道所需检测的个样本中有个是阳性的，其中； 竞争模型：事先既不知道也不知道； 容错模型：检测结果可能出现错误。
同时介绍了相应的四个理论结果。这四个模型都属于序贯方法：每次检测哪些样本组，通常要依赖以前的检测及其结果。一个序贯方法如果需要进行次检测才能检测出所有的坏样本，而每次检测需要时间的话，整个检测过程通常需要时间。如果想缩短时间，那么除了尽可能地减少检测次数，还有一个方法就是在时间内同时（并行地）检测若干（而不是一个）样本组。
今天我要给大家介绍一种非序贯方法：在检测开始前，需要把将要检测哪些组完全确定下来，换言之，检测哪个组并不依赖于其他检测组的结果。不难发现，尽管非序贯方法用的检测次数不会少于序贯方法，但是完成全部测试所需用的时间段长度会小于序贯方法，因为非序贯方法允许同一时间段并行地进行检测（只要有足够多的检测设备；比如，如题图所示，有4台设备）。逐一检测法可以看作是非序贯检测法，因为所有的检测都可以在时间内同时完成（但是至少需要台检测设备）。
首先我想给大家回顾一下《环球时报》4月5日的一则报道：“…疫情在全球蔓延后，比尔盖茨更是耗费数十亿美元投资研发新冠疫苗。据《国会山报》4月3日报道，比尔盖茨的基金会目前正在投资建造工厂，这些工厂将生产七种有前途的冠状病毒疫苗。比尔盖茨对《每日秀》的主持人“崔娃”表示，虽然他最后只会从这七种疫苗中选择一到两种，但他也会出钱让七个工厂同时运作，这样就不会因为一个个排除而浪费时间 …”可以看出，比尔盖茨采用的就是非序贯方法。
下面言归正传，我们先看组合模型的一个简单例子：在待检测的4个样本中，已知仅有一个是坏样本。若采用二分策略的组合检测（序贯方法），用2次检测就可以找出那个坏的样本；如果做一次检测的时间是，那么完成两次检测的时间就是。能不能用时间就检测出那个坏样本呢？
上面的图表给出了一个非序贯的组合检测方案：检测I包含样本①和③，检测II包含样本②和③。同时进行检测I和检测II。若得到检测结果I和结果II是“+”和“-”，则样本①是坏样本；若得到检测结果I和结果II是“+”和“+”，则样本③是坏样本；等等。这个方法就可在时间里同时完成两次检测，而且一定能找出那个坏样本。一般的，若已知在待检测的个样本中，有惟一一个是坏样本，则可以在时间内同时完成次检测，并找出那个坏样本。请大家自己设计这样的一个非序贯的组合检测方案吧，你一定能行！
最后，我来给大家介绍一个猜年龄游戏。实际上，它是前一次我讲的乌拉姆猜数游戏的一种特殊情况（我在上一次已经说明：猜数游戏实际上是血液检测问题的特例）。考虑到她的年龄不超过60岁，且，因而我可以采用基于二分策略的序贯方法，向她提问最多不超过6个问题，一定可以猜出她的准确年龄。而在这个游戏中，我给出了6张表，每张表相当于一个问题：她的年龄是否出现在这张表中？只不过这次，这6个问题是一次给出的（非序贯方法），而不是像采用二分策略（序贯方法），一个问题问完了以后，根据得到的回答，再问下一个问题。
比如，当她告诉我，她的年龄出现在第①、③、④、⑥张表中的时候，我就猜出了她的年龄是45岁。我是如何做到的呢？首先，我观察到6张表的每张表第1行第5个数字分别是 1，2，4，8，16，32。然后，我将第①、③、④、⑥张表中对应的数字相加得到 1+4+8+32=45，这就是我猜出的年龄。大家不妨验证一下，45的确出现而且仅出现在第①、③、④、⑥张表中。
我为什么能利用这6张表猜出她的年龄呢？注意，每一个自然数都可以用二进制惟一表示出来，比如，。而这6张表的每一张表第1行第5个数字分别是，它们分别都仅出现在一张表中。因而，可以将不超过60的任何一个自然数，根据其二进制惟一表示，填入相应的表格中。显然，将1，2，4，8，16，32分别放在6张表的每张表第1行第5列的位置，只是为了计算方便，实际上可以将它们分别放到每张表的任何位置上。建议大家如法炮制，制作8张表，从而猜出任何人的年龄（因为一般情况下没有人的年龄超过120吧）。
大家会问对于一般情形：个样本中有不止一个坏样本，又该如何设计非序贯的组合检测方案呢？先看一个比较小的例子：12个样本中有2个坏样本。如果用序贯的组合检测方法，那么用7次检测就可以确定哪2个样本是坏的。下图中给出了一个非序贯的组合检测方案，它用8次检测就可以确定哪2个样本是坏的（建议大家花点时间，仿照前面4个样本中有1个坏样本的例子，验证一下）。
一般来讲，一个非序贯的组合检测方案可以用 ()-矩阵表示，其中表示检测组数，表示样本数，矩阵的单元为1，表示第个检测组包含第个样本；否则为0，表示不包含。大家自然要问了：这个()-矩阵应该满足什么样的性质，至少要多大（当然不会超过），其对应的非序贯组合检测方案就可以确定个样本中哪个样本是坏的呢？要回答这个问题需要用到叠加码（superimposed code）的设计方法和理论。这个方法最初是由W. H. Kautz和R. R. Singleton [1]于1964年研究如何检索文件时提出来的，后来被K. A. Bush等人[2]于1984年应用到（非序贯）组合检测方法的设计中。大家对这个方向如有兴趣，还可参阅文献[3,4,5]。
至此，我给大家介绍了与血液检测（直接）相关的五个基本模型及其相应的组合检测方法。下一次，也是最后一次，我将给大家介绍一个血液检测的变形，伪硬币问题。
参考文献
[1] W. H. Kautz and R. R. Singleton, Nonrandom binary superimposed codes, IEEE Trans. Information Theory, 10 (1964), 363-377.
[2] K. A. Bush, W. T. Federer, H. Pesotan and D. Raghavarao, New combinatorial designs and their applications to group testing, J. of Statist. Plan. & Infer., 10 (1984), 335-343.
[3] F. K. Hwang and V. T. Sos, Non-adaptive hypergeometric group testing, Studia Scient. Math. Hungarica, 22 (1987), 257-263.
[4] F. Vakil and M. Parnes, On the structure of a class of sets useful in non-adaptive group-testing, J. Statist. Plan & Infer., 39 (1994), 57-69.
[5] A. G. Dyachkov and V. V. Rykov, a survey of superimposed code theory, Problems of Control and Information Theory, 12 (1983), 1-13.
六
这次我给大家介绍一个血液检测的变形，伪硬币(检测)问题：从前有位国王，有一天他收到了12枚金币，他怀疑其中可能混有一枚伪币。他知道所有金币的重量都是一样的，而伪币的重量与金币的不同。于是国王责令一位最聪明的大臣利用天平称重的办法告诉他：
（1）金币中是否混有伪币； （2）如果混有伪币，找出它来； （3）伪币比金币重还是轻。
这位大臣最少需要几次称重才能回答上述三个问题呢？
关于这个趣题，1953年E. V. Nebery [1]在《数学报》（The Mathematical Gazette）上的一篇文章中称：“我确信这个问题起源于二战后期，而且很快在英国政府部门和科研机构流传开来。据估计竟然大约有10,000个人力时被耗费在这个问题上了。因而有人就建议，将该问题翻译成德文并印在传单上，让英国皇家空军(Royal Air Force)将这些传单撒到德国领土上，这样就会耗费德国人差不多同样的人力时了。”
现在言归正传，我们还是讨论如何求解伪硬币问题吧。每个天平有左和右两个托盘。显然，进行称重时，应该在两个托盘上放的硬币个数是一样多的，称重的结果有三种情况：左边重一点，右边重一点，两边一样重。最简单的称重方案就是逐一检测法：每次只检测两枚硬币，比如，左边托盘放①号硬币，右边托盘放②号硬币。
如果两边一样重，说明它们都是金币；再将右边托盘上的②号硬币拿走，放上③号硬币。如果两边一样重，说明③号硬币也是金币，否则它是伪币（同时知道它比金币轻还是重）。 如果两边不一样重，比如，①号硬币比②号硬币轻，说明它们中有一枚是伪币；再将右边托盘上的②号硬币拿走，放上③号硬币。如果两边一样重，说明①号和③号硬币都是金币，②号硬币是伪币（同时知道它比金币重）；否则①号硬币比③号硬币轻，说明①号是伪币，它比其他的金币轻。(不会发生①号硬币比③号硬币重的情形，因为硬币最多有两种重量。)
易知，用上述逐一检测法最多用11次检测就可以找到那一枚伪币或者验证没有伪币。能不能用更少的称重检测呢？大家很容易就想到了组合检测法：每次称重时，两边的托盘分别放2枚或者更多枚硬币。下图给出了一个组合检测方案，它只用了3次称重检测就可以找到那枚伪币或者验证没有伪币。（请大家说明2次称重检测是不够的。）
现在一个非常自然的问题是，如果有更多的硬币，不止12枚硬币，其中可能不止1枚伪币（而且事先也不知道有多少枚伪币，可能一枚也没有），那么我们又应该如何进行组合检测呢？很多学者对这些问题进行了研究，其中包括 L. Halbeisen 和N. Hungerbuhler [2]，L. Pyber [3]，笔者和黄光明[4]，N. Alon 和V. H. Vu [5]，等等。大家如果有兴趣，可以阅读相关的论文。
好了，至此我先后分六次给大家介绍了血液检测及相关问题的最基本数学模型和结果，包括DNA测序和网络故障诊断等在内的其他相关内容，因为时间关系没有涉及（大家马上就要返校上课了）。如果大家对这个方向特别感兴趣，那么我推荐大家研读堵丁柱和黄光明两位教授的专著[6, 7]。
最后，谢谢大家阅读我的科普系列短文！也请大家多提意见。同时，我也要感谢柚子优化团队的辛勤劳动。
参考文献
[1] E. V. Newbery, 2342. The penny problem, The Mathematical Gazette, 37 (320) (1953), 130-130.
[2] L. Halbeisen and N. Hungerbuhler, The general counterfeit coin problem, Discrete Mathematics, 147 (1995), 139-150.
[3] L. Pyber, How to find many counterfeit coins? Graphs and Combinatorics, 2(1986), 173-177.
[4] X.-D. Hu and F. K. Hwang, A competitive algorithm for the counterfeit coins problem, Noncovex Optimization and its Applications, Kluwer Academic Publishers, USA, 4 (1995), 241-250.
[5] N. Alon and V. H. Vu, Anti-Hadamard matrices, coin weighing, threshold gates, and indecomposable hypergraphs, Journal of Combinatorial Theory, Series A, 79 (1997), 133-160.
[6] D.-Z. Du and F. K. Hwang, Combinatorial Group Testing and its Applications, 2nd edition, World Scientific Publishing Co. Pte. Ltd., Singapore, 2000.
[7] D.-Z. Du and F. K. Hwang, Pooling Designs and Nonadaptive Group Testing, World Scientific Publishing Co. Pte. Ltd., Singapore, 2006.