称硬币问题的两面--信息论和搜索
开始
首先给出我们要解决的问题:
有 12 枚外表一模一样的硬币，其中一枚是假币，其余都是真币。假币的重量与真币不同，但是更重还是更轻不知道。给你一个没有砝码和刻度的天平，最少称几次才能确保找出假币?
类似的题目的变种也非常的多而且经常会时不时出现在我的面前,但是一法通 万法通,只要掌握了方法这类问题也就变成了有通解的简单数学题而已.以前的我也是这么想的,但是在机缘巧合之下看到了这个硬币的两面,感觉非常有趣便在此记录一下.
离散数学
让我们先从逻辑谓词的角度来看看这个问题.当然如果你对离散学习非常熟悉的话,在看到这个问题的时候应该就能想到:”这不就是纠错码吗?”,没错,离散数学的解决方法就是纠错码.
Hamming Code
汉明码（Hamming Code）是广泛用于内存和磁盘纠错的编码。汉明码不仅可以用来检测转移数据时发生的错误，还可以用来修正错误。（要注意的是，汉明码只能发现和修正一位错误，对于两位或者两位以上的错误无法正确和发现）。
纠错,一位,完美适应我们提出的硬币问题!那么我们就开始吧~
过程
首先对于硬币称重这个问题来说,我们可以假设称完硬币有状态:1(左边),2(右边),而将0保留为没有上天平的硬币.那么我们就有$3^3=27$种状态:000,001,002…..,221,222.首先可以排除000这种状态,因为这表明这个硬币没有被用到(浪费显然是不可能的).然后我们要排除所有状态中的共线的状态(对于每一位数乘以2取余3后结果相同为共线),然后我们就一共剩下了下面的13种可能的状态:
当然因为我们这里是需要对硬币称重,所以需要每次上天平的硬币数量相同,那么我们只要保留前12组(没称,左边,右边)就可以了.
接下来我们要对硬币开始调平,对于第一行来说,有4个0和8个1,所以把最后4组都乘以2取余3:
然后来看第二行:多了2个1,因为第一行已经固定了所以这次只能在第一行为0的列中下手,我们对3,4列乘以2:
整个称重的过程就已经出现了:
- 第一次:
- 左边:5,6,7,8
- 右边:9,10,11,12
- 第二次:
- 左边:2,8,11,12
- 右边:3,4,9,10
- 第三次:
- 左边:1,4,6,10
- 右边:3,7,9,12
对于结果来说:
- 1代表左倾,2代表右倾,0是平衡,如果能够直接在表中找到结果,那么对应的硬币则为假币且比真的更重
- 如果在表中找不到结果但是有其共线的向量,那么对应的硬币为假币且更轻.
例子
比如:
- 第一次:右边重(2)
- 第二次:右边重(2)
- 第三次:右边重(2)
那么(2,2,2)9号为假币且更重
- 第一次:左边重(1)
- 第二次:右边重(2)
- 第三次:平衡(0)
那么(1,2,0)其共线向量硬币为11且更轻
解决了!
没错,通过一个简单的矩阵就可以解决这一类的问题并且非常的简单:查表就完事了~当然这需要对纠错码非常的敏感才能映射到这个问题上并且加以运用才行.
有限域
当然如果数学非常流批的话,可以直接忽视上面的纠错码而直接进行数学推导也是可行的.在这里给出纯粹的数学推导的方法:(直接给出大佬的博客:称硬币问题、小白鼠找毒药问题与编码理论),在推导结束之后写出矩阵和称重的过程是完全一致的.
信息论,还是信息论!
当然信息论给了我们一个有力的工具:纠错码,但是这还不够!如果我们将这个问题进行变种:在要求最少称重次数的情况下需要称过的球的次数也最少.
纠错码似乎就变得束手无策了,看一下维基百科上对于纠错码的描述:
实现错误检测和纠正的一般思路是添加一些信息冗余（例如一些额外数据）到消息，从而使接收器可以用它来检查消息的一致性，并恢复被确定为损坏的数据。错误检测和纠正的方案可以是系统性或非系统性：在系统性方案中，发射机发送原始数据，并且附加其通过一些确定性算法从数据比特导出的固定数量的校验位（或奇偶校验数据）。如果仅需要错误检测，则接收器可以简单对接收到的数据位应用相同的算法，并将其输出与接收到的校验位进行比较。如果值不匹配，则传输期间的某个点位发生错误。在非系统性的编码系统中，原始消息被变换与原始消息相等或更长比特的被编码消息。
也就是说,纠错码的纠错机制是建立在冗余之上的,而在这个问题中对于称球的次数也明显出现了冗余的信息.
二分
其实对于CS的学生来说(最起码对于我)想到的第一个解决的思路就是二分,而二分的可贵之处在于:
二分搜索为什么好，就是因为它每次都将可能性排除一半并且无论如何都能排除一半（它是最糟情况下表现最好的）。
那么对于这道题目的解法就是需要使得左倾,右倾和平衡三种结果的分支上的情况尽可能的相等,而12个硬币的可能情况有24种,也就是可以在$\lceil log_3(24) \rceil = 3$次之内解决这个问题.
下面给出解法(三分):
可以看到后面的称重是有效的利用了前面称重结果中的信息的(比如7轻8轻的情况下1必然已经是重的了,直接和1比较即可)
总结
这个问题的有趣之处在于其在搜索和信息论之间建立起的那座隐秘的桥梁,而对于这个问题的本质的追寻也是使得我难以忘记它的原因.
而大刘的这篇数学之美番外篇：快排为什么那样快也是十分耐人寻味的一篇文章,可以说对于这一个看似简单的问题而抛出的各种不同的解是很令人着迷的,而这也就是在CS这条路上不感到厌倦的原因吧.
对于汉明码解决问题的过程完全参考了这篇博客:Counterfeit Coin–Contributed by J. Dom nguez Montes.
吾尝终日而思矣,不如须臾之所学也.