问题描述：

有编号从1到n的n个小球，其中可能有一个球的重量和其他的球重量不一致，而且这个重量不一致的球可能是偏重或偏轻。给定一个天平（天平有r=2个盘子），要求通过m次称量来判断出是否有重量失衡的球，如果有的话，判断出球的编号，并且能够指出该球是偏重还是偏轻。

请问：
给定m=3 r=2，最大的n的数量为多少？

问题分析：

很多称重问题都可以加以泛化等效为上述问题。在只需判断出失衡球的编号而不需要知道失衡种类的情况下，我们可以很轻易地把称重问题等效为二进制的汉明编码问题。而在上述问题中，我们则需要把称重问题等效为三进制的汉明编码[1]。为了搞清楚等效的思路，我们在下面的分析中，首先对三进制下的汉明编码进行完整地描述，然后再把三进制汉明码与称重问题建立等效关系。

二进制汉明码：

图1-1 二进制汉明码校验规则[2

三进制汉明码描述：

在三进制中，一个码元上的错误位置就可以有2个，n个码元上的错误位置就有2n种，而n-k个校验位可以表达3^(n-k)个不同的意思。由汉明码定义，它应该恰好等于所有的单个差错图案加上1，即。令n-k=m(校验位个数)，则q进制汗明码的n，k应该服从

三进制汉明码的构建方法：

首先分析三进制汉明码的特征：m个校验位，其要完成的不仅仅是定位，还要指出相应位置上的错误的类型。在三进制的情况下，这样的错误类型数为2。这就要求每个位有两种表示方法来定位。[3]指出，可以运用一种类似贪心算法的方法来构建满足以上条件的校验矩阵，通过Lexicographic顺序加入校验矩阵的列，同时保证新加入的列和前面的任意一列线性不相关。这样的话在所有3^3-1个列中每一个列都有与之相对应的一个线性相关列。校验规则构建方法如下图

图1-2 三进制汉明码校验规则

其中淡蓝色的列是和之前的列出现相关的列，红色的列组成了校验矩阵，我们其中校验位为第1(3^0)，3(3^1)，9(3^2)位。所有的校验运算均是在GF(3)域下的运算。

三进制汉明码与称重问题的转化：

与三进制汉明码类似，在称重问题中，每一次称重都会得出三个结果：左偏，右偏，平衡。而n次称重之后的结果是要判断这些小球中是否有一个重量失衡的球，如果有，球的编号和失衡的状态(偏重，偏轻)分别是多少。因此我们可以用三进制汉明码的概念来解决小球称重的问题。

称重问题与三进制汉明编码的区别：

1. 汉明码的校验位可能出现失真；而小球称重时校验位不包含在编码当中，而且是一个定值(都应该是平衡状态)，不会出现失真。
2. 汉明码的校验方程检验的位数可以是奇数；而称重问题需要在天平两端放上同等数量的球才能使校验有效，每次必须只能检验偶数个球。因此校验的方式不同。

称重问题的编码方式：

如下图所示：

图1-3 m=3下称重问题的校验规则

图1-4 GF(3)域乘法运算

我们定义一个球的重量正常为1，和偏重为2，偏轻为0。那么我们从图1-4的运算中可以发现：1，如果该球代表的位在校验矩阵中的系数为1，那么偏重将导致校验和+1，偏轻将导致校验和-1；2，如果该球代表的位在校验矩阵中的系数为2，那么偏重将导致校验和-1，偏轻将导致校验+1。

相对应的，如果我们把天平左倾记为符号“+1”，天平右倾记为符号“-1”，校验系数为1的球放左盘，校验系数为2的球放右盘。那么和以上的校验规则是一致的！稍微有所不同的是在天平校验中，左盘球的数量和右盘球的数量必须一致才有意义，因此我们要求图1-3的校验矩阵做出调整：首先删去一列使校验位的数量恒为偶数，再把某些列变换为其线性相关列，从而使每一行的1的数量和2的数量相同，在图1-3的环境中，我们变换了5，6，9，10列，删去了13列。于是，我们便得到了在称天平次数m=3的情况下，对12个小球做出校验的方式。

结论：

通过图1-3的方法，我们求出了在m=3的情况下，最大的n为12，并且给出了称重的方式。

从信息论的角度来说，每一次称重的结果为3个，可以提供的信息位数为log2（3）个，而系统的总状态有2n+1个，可以通过log2(2n+1)个信息位来描述，则称重次数m应该满足m>log2(2n+1)/log2(3),即n<=(3^m-1)/2。在m=3的情况下，n<=13。

注意到理论上我们可以得到n=13的情况下的称重方法，为了实现这种方法，我们需要加入一个标准的球即可。但是在一开始的问题描述中我们并没有这条假设，因此n=13的上限是不可实现的。

通过把称重问题刻画为汉明编码的方法，我们能求出任意m，任意r（一个天平多个盘）的情况下 n的最大值。

Isn’t it great?:)

参考文献：

[1]Thomas M Cover, Joy A Thomas,<Elements of Information Theory>, Chapter 2, Problem 13

[2]http://en.wikipedia.org/wiki/Hamming_code

[3]http://www.mth.msu.edu/~jhall/classes/codenotes/Hamming.pdf