数学无处不在 – 血液检测的数学模型和理论（六）

今天我给大家介绍一个血液检测的变形，伪硬币(检测)问题：从前有位国王，有一天他收到了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]。

最后，谢谢大家阅读我的科普系列短文！也请大家多提意见。同时，我也要感谢柚子优化团队的辛勤劳动。

作者：中国科学院数学与系统科学研究院  胡旭东

排版：柚子美编三号（西安交大金融优化组Brandon）

如需转载请联系柚子优化公众号