1.1 偷懒的小货郎

“易有太极，是生两仪，两仪生四象，四象生八卦。”

——《易经·系辞上传》

以前，有个老货郎沿街卖糖果，糖果以1斤（1斤=500克）为最小售卖单位，他一次最多带40斤出门。老货郎称糖果用的是天平（图1.1.1），所以除了货物以外，他还需要带上一套能够称出1～40斤整数重量糖果的砝码。

单个砝码的重量从1斤到40斤的都有，老货郎家有好几套这样的砝码。以前卖货时，他总是带上这样一组共6个砝码出门：1个1斤、2个2斤、1个5斤、1个10斤、1个20斤。不同重量的砝码类似于不同面额的钞票，老货郎可以通过这些砝码的组合，得到1～40斤的任意一个整数重量。比如，要称出17斤的糖果，只需在天平的另一端放上2斤、5斤和10斤3个砝码就可以了；要称出29斤的糖果，则需要放上2个2斤、1个5斤和1个20斤共4个砝码。

后来，老货郎招了个徒弟，即小货郎，出门卖货时背砝码的任务也就交给了小货郎。砝码总重40斤，小货郎年轻力壮倒不嫌砝码重，只是觉得大大小小共6个太麻烦，还很容易弄丢。既然砝码是卖货必须要用的，小货郎心里虽然有想法，嘴上却也没有说什么。

每天夜里躺在床上，小货郎就开始琢磨：是不是可以少带些砝码，同样可以称出1～40斤的整数重量？

为了简化问题，小货郎先从较小的重量开始考虑：如果老货郎最多只卖7斤糖果，那么最少需要哪些砝码呢？因为糖果的最小售卖单位是1斤，所以1斤这个砝码是肯定需要的；同时最多要称出7斤糖果，所以所有砝码的总重量不会低于7斤。这样，最少也需要2个砝码了。

按照老货郎根据钞票面额确定选用哪些砝码的做法，实现1～7斤任一整数重量的砝码组合可以是1个1斤、3个2斤，或者1个1斤、2个2斤和1个5斤，无论哪种组合都需要4个砝码。如果使用其他重量的砝码呢？那么可以是1个1斤、1个2斤、1个4斤，这样3个砝码就可以通过加法组合出1～7斤的任一整数重量。

这种组合可以比老货郎的办法少带1个砝码！

类似地，对于1～15斤的任一整数重量，可以用4个砝码通过加法组合实现，4个砝码分别是1斤、2斤、4斤和8斤。比如要称出11斤的糖果，可以使用1斤、2斤和8斤3个砝码；要称出14斤糖果，可以使用2斤、4斤和8斤3个砝码。

小货郎把4个砝码从大到小依次放好，从左到右依次是8斤、4斤、2斤和1斤。他发现对于1～15斤的任一整数重量，只需要用二进制来表示它，然后使用出现1的相应位置上的砝码来称重即可。比如十进制中的(11)10，用二进制表示就是(1011)2，从左到右表示使用8斤、2斤和1斤的砝码；十进制中的(14)10，用二进制表示就是(1110)2，表示使用8斤、4斤和2斤的砝码。

因为1～15的任意一个整数可以且唯一可以用一个4位数的二进制表示，所以用8斤、4斤、2斤和1斤这4个砝码就可以通过加法组合出1～15的任意一个整数重量。

小货郎依此类推，得出：要表示1～3斤的任一整数重量，用2个砝码即可；1～7斤需要3个砝码；1～15斤需要4个；1～31斤需要5个……结论：对于1～2n-1斤的任一整数重量，只需要n个砝码就可以了，其重量分别为1斤、2斤……2n-1斤。不过很遗憾的是，要表示1～40斤的任一整数重量，因为40大于25-1，所以小货郎仍然至少需要6个砝码。

那么，是不是还有别的办法可以让他偷个懒，少带些砝码呢？

小货郎的目光从天平的一边移到了另一边，所有的砝码可以单独放在一边，是不是也可以把部分砝码和糖果放在另一边呢？以1斤和3斤两个砝码为例，如果只把砝码单独放在一边，通过加法组合，可以得到1斤、3斤和4斤3个不同重量；如果同时可以把一部分砝码放在另一边，那么通过减法组合，还可以得到2斤这个重量，比如把3斤的砝码放在一边，1斤的砝码和糖果放在另一边。因此，实际上使用1斤和3斤两个砝码，通过加法和减法组合，就可以得到1～4斤的任意一个整数重量。

受到这个发现的鼓舞，小货郎又拿出了9斤这个砝码，他兴奋地发现，使用9斤、3斤和1斤这3个砝码，通过在天平两边的摆放，可以得到1～13斤的所有整数重量。比如要得到11斤糖果，可以将9斤和3斤砝码放在一边，1斤砝码和糖果放在另一边；要得到7斤糖果，可以将9斤和1斤砝码放在一边，3斤砝码和糖果放在另一边。

这个方法的可行性是很容易被证明的：因为使用3斤和1斤砝码可以得到1～4斤的任一整数砝码净重，那么通过减法组合，将9斤砝码放在与净重砝码侧相对的另一边，就可以得到5～8斤的任一整数重量；同样通过加法组合，将9斤砝码放在与净重砝码相同的一边，就可以得到10～13斤的任一整数重量。因此，使用这3个砝码，就可以得到1～13斤的任一整数重量（表1.1.1）。

并且，这个规律可以外推到更大的重量：用1斤、3斤、9斤和27斤4个砝码，可以得到1～40斤的任一整数重量；用1斤、3斤、9斤、27斤和81斤5个砝码，可以得到1～121斤的任一整数重量……由此得出的结论：对于1～·(3n-1)斤的任一整数重量，只需要n个砝码就可以了，其重量分别为1斤、3斤……3n-1斤。

对于小货郎来说，从明天开始他带上4个砝码出门就可以了，现在他可以安心地睡个觉了。

我们再来看看小货郎要带的那些砝码，1斤、3斤、9斤、27斤，现在将这些砝码由大到小从左到右排列，然后把1～40中的任一整数用三进制来表示，是否可以得到某种对应关系呢？

比如十进制中的(22)10，用三进制表示就是(211)3。问题来了，在二进制中，每个数位上的0表示不用该砝码，1表示使用该砝码；在三进制中，非零的数位上除了1还有可能是2，这意味着只用加法组合的话，我们还可能需要另外一套砝码。不过小货郎聪明地发现了砝码还可以放在天平的另一边，也就是说可以使用减法组合。(211)3也可以表示为(1011)3-(0100)3，即(27+3+1)-9=22；或者说27斤、3斤和1斤3个砝码放在一边，9斤那个砝码放在糖果的一边，我们就得到了22斤这个重量。类似地，要得到35，可以利用(35)10=(1022)3=(1100)3-(0001)3，即(27+9)-1=35。

如果我们扩展一下三进制的定义，从右至左将数位上的每一个2都改为-1，同时向前一位进位，0和1则保持不变。这样，(211)3变成了(1-111)3，表示33-32+31+30=22；(1022)3则变成了(110-1)，表示33+32-30=35。在扩展的三进制定义中，每个数位上要么是0，要么是1或者-1，0表示该砝码不用，-1表示该砝码和糖果放在同一边，1表示该砝码放在天平的另一边。依此定义，一个4位数其最大值为(1111)3，即27+9+3+1=40，所以使用这4个砝码就可以表示1～40的任一整数重量。

从小货郎的例子我们可以看出，不同基数（又称底数）的数制表示法有着不同的效率。二进制每个数位上只有两个状态，即0和1，但它需要更多的数位来表示较大的数；十进制每个数位上有0～9共10个状态，但对于同样大小的数，它需要的数位比二进制要少很多，比如同样表示1024，十进制只需要4个数位，而二进制需要11个数位。

哪一个基数的数制是最优的？对此并没有一个简单的答案。如果从信息传递效率的角度来看，考虑所谓底数经济度（radix economy），那么不同基数的数制具有不同的效率。

简单来说，底数经济度，符号表示将x向下取整。以N=999为例，二进制的基数b=2，用二进制表示999需要10个数位，所以E(2,999)等于20；八进制的基数b=8，用八进制表示999需要4个数位，所以E(8,999)等于32；十进制的基数b=10，用十进制表示999需要3个数位，所以E(10,999)等于30。相比较而言，这3种数制中，二进制的效率最高。

那么对于所有基数，是否二进制的效率最高呢？如果把E(b,N)=b(logbN+1)看作一个关于变量b的连续函数，在函数取最小值时，b等于自然常数e。也就是说，如果采用自然常数e作为基数，效率最高。如果限定基数必须为整数，因为e=2.71828…，所以b=2或者3时E较小。通过比较，b=3时E最小，也就是说，三进制是最有效率的数制。

这个结论和小货郎想出来的方法是相符的，我们把使用-1、0和1的三进制表示法叫作三进制的平衡表示法。计算机科学家高德纳（Donald Knuth）在他的名著《计算机程序设计艺术》中曾经表示，平衡三进制是最美的数学体系。这不仅因为任何整数都可以通过加减3的幂得到（小货郎的天平法），而且和二进制的“非黑即白”的二态性相比，平衡三进制还提供了一个平衡态0，即我们在平衡三进制中除了可以用-1和1来表示确定的两个状态，还可以用0来表示“不确定”。很显然，和二态性相比，这种三态性更符合现实中的情况，也更适合描述现实世界。

既然三进制比二进制更高效，为什么计算机采用的都是二进制呢？

事实上，在人类历史中确实存在着使用三进制设计计算机的努力。因为三进制在理论上更为高效，苏联的科学家曾经在长达20年的时间里试图在三进制计算机领域取得突破。1958年，第一台三进制计算机Setun由谢尔盖·索博列夫（Sergei Sobolev）和尼古拉·布鲁先佐夫（Nikolay Brusentsov）设计成功。1960年，Setun通过公测，并投入批量生产。直到20世纪70年代末，二进制计算机凭借其在电压高低、电路开关二态性方面的天然优势几乎占据了整个市场之后，苏联对三进制计算机的研发才终止。

由此可见，用不同基数的数制来表示十进制数，有时候会给我们带来不同的思路，达到简化问题和计算过程的目的。

下面是一道经典的智力题：工厂生产了10批乒乓球，质量合格的乒乓球每个重2.7克，已知10批产品中有1批出了质量问题，这批乒乓球每个都重2.8克，请问如何使用天平，只称一次就能知道是哪批产品不合格？

这道题目相信很多小学生都会做，做法是将10批产品依次编为1～10号，再依次从1号批次产品中取出1个乒乓球，2号批次产品中取出2个乒乓球，依此类推，10号批次产品中取出10个乒乓球，然后将这55个乒乓球一起放在天平上称重，将实际质量减去55个乒乓球的核定质量（2.7×55=148.5克）得到超出质量，再将超出质量除以0.1得到超重乒乓球数。如果超重乒乓球数为1，就表示1号批次产品不合格；如果超重乒乓球数为2，就表示2号批次产品不合格……如果超重乒乓球数为10，就表示10号批次产品不合格。

现在我们将题目的条件改一下：已知不止一个批次的产品出了质量问题，所有问题批次的乒乓球每个重量都是2.8克，其他合格批次的乒乓球每个重量都是2.7克，如何通过天平称一次，就能知道哪几个批次质量不合格呢？

显然，用老办法解决不了新问题：如果最后得到超重乒乓球数为5，究竟是5号批次的产品出了问题，还是2号批次和3号批次的产品都出了问题，我们不得而知。

这个时候，我们需要改变每个批次乒乓球的称重数量：按照二进制的思想，可以从1号批次产品中取出1个乒乓球，2号批次产品中取出2个乒乓球，3号批次产品中取出4个乒乓球，依此类推，10号批次产品中取出512个乒乓球，然后将这总共1023个乒乓球一起称重，将实际重量减去1023个乒乓球的核定质量（2.7×1023=2762.1克）得到超出重量，再除以0.1得到超重乒乓球个数。此时，如果超重乒乓球数为1，就表示1号批次产品不合格；如果超重乒乓球数为2，就表示2号批次产品不合格；如果超重乒乓球数为3，就表示1号和2号批次产品都不合格。也就是说，如果把超重乒乓球数用二进制表示，从右到左的数位分别表示1号、2号……10号批次产品，哪个数位上数字为1就表示哪个批次的产品不合格。

这个解法的精妙之处在于，通过将第n个批次的乒乓球取样个数从线性的n改为指数的2n-1，避免了线性组合带来的不确定性。因为指数取样法中不可能出现进位叠加，这样就保证了二进制表示的唯一性，可以准确地将不合格产品的批次定位出来。

另外一道经典的“小白鼠试药”问题也很好地体现了二进制的威力。题目是这样的：有1000个外表一模一样的瓶子，其中999瓶中装的是普通的水，只有一个瓶子装的是毒药，小白鼠喝了水会平安无事，喝了毒药的话哪怕只喝了一点点也将在一天内死去。现在你有10只小白鼠，如何在一天的时间内找出哪个瓶子里装的是毒药？

这道题目的解答是非常经典的。将瓶子依次编号为0～999，然后将编号转换为10个数位的二进制编号，比如12号瓶的二进制编号为(0000001100)2，311号瓶的二进制编号为(0100110111)2。然后将小白鼠也编为1～10号，1号小白鼠依次走过所有的瓶子，如果瓶子的二进制编号的右起第1数位（即二进制最低位）为1就喝上一口，如果数位为0就跳过；2号小白鼠依次走过所有的瓶子，如果瓶子的二进制编号的右起第2数位为1就喝上一口，如果数位为0就跳过……依此类推，10号小白鼠依次走过所有的瓶子，如果瓶子的二进制编号的右起第10数位（即二进制最高位）为1就喝上一口，如果数位为0就跳过。

这样到了第二天，10只小白鼠中有一些平安无事，其他的小白鼠中毒身亡。我们将小白鼠按照1～10的编号从右到左排列，如果平安无事就在数位上记0，如果中毒身亡就记1，这样我们得到一个10个数位的二进制数，这个二进制数就是装有毒药瓶子的二进制编号。

举例来说，我们假设311号瓶装的是毒药，其二进制编号为(0100110111)2，根据上述规则，1号、2号、3号、5号、6号、9号小白鼠都喝了这个瓶子装的毒药，而4号、7号、8号和10号小白鼠都将跳过这个瓶子。因此在第二天，1号、2号、3号、5号、6号、9号小白鼠都中毒身亡，相应地将这几只小白鼠对应的数位标记为1，其他数位标记为0，我们就能得到(0100110111)2，即推出311号瓶子里装的是毒药（表1.1.2）。

现在，我们再进一步：如果你有两天的时间，有时间进行两轮试药，同样要在1000个瓶子里找出唯一的一瓶毒药，最少需要几只小白鼠呢？

9只小白鼠可以吗？9只小白鼠可以占据9个数位，9个数位的二进制数最大为511；也就是说，按照老办法，9只小白鼠在第一天可以测试512个瓶子[1]。如果毒药瓶在这512个瓶子中，那么第一天就能被找到；如果毒药瓶在剩下的488瓶中，那么9只小白鼠平安无事，第二天仍然可以用于最多512瓶的测试，而因为第二天只剩下488瓶，所以任务可以圆满完成。

那么8只呢？8只小白鼠可以占据8个数位，8个数位的二进制数最大为255；也就是说，按照老办法，8只小白鼠在第一天可以测试256个瓶子。如果毒药瓶在这256个瓶子中，那么第一天就能被找到；但如果毒药瓶在剩下的744瓶中，那么即便第二天我们还有8只平安无事的小白鼠，它们在一天中最多也只能完成256个瓶子的测试，而剩下的未知瓶子还有488个，所以按照老办法我们无法完成任务。

那么有没有别的办法呢？

有！我们可以利用三进制，利用三进制编码的方法，我们只需要7只小白鼠就能在两天内找到装有毒药的瓶子。

具体做法是这样的。类似地，将1000个瓶子进行三进制编码，因为37=2187，所以这个三进制编码总共有7位。同样将小白鼠编为1～7号，1号小白鼠依次走过所有的瓶子，如果瓶子的三进制编号的右起第1数位为2就喝上一口，如果数位为0或者1就跳过；2号小白鼠依次走过所有的瓶子，如果瓶子的三进制编号的右起第2数位为2就喝上一口，如果数位为0或者1就跳过……依此类推。这样，在第二天统计小白鼠的健康状况时，如果某个数位对应的小白鼠死去，就表示有毒药瓶子的三进制编码在该数位上为2；如果某个数位对应的小白鼠还活着，就表示有毒药瓶子的三进制编码在该数位上为0或者1。然后在第二天，用幸存的小白鼠继续在它们所在的数位试药，在第二轮的试药中，让每只活着的小白鼠尝试自己对应数位上三进制编号为1的瓶子。如果小白鼠死去，说明有毒药瓶子的三进制编码在该数位上为1；如果小白鼠幸存，说明该数位为0。这样，经过两轮试药，有毒药瓶子三进制编码的所有数位都将被唯一确定，我们就能知道哪个瓶子装有毒药。

不失一般性，如果有b-1天时间，那么根据类似的方法只需要n只小白鼠就能从bn个瓶子里找出唯一装有毒药的瓶子来。仔细看看这个公式，是不是和底数经济度E(b,N)的公式很相似呢？