如何制造个数最少的单位砝码,如 1g,2g,3g,4g……,使得这些单位砝码能称出1g到100g之间的任何整数克的物体?
最直观的感受是直接使用1,2,4,8…,64 。也就是2^0,2^1,2^2…2^6,一共7个砝码,因为任何数字都可以表示成二进制数,比如100用二进制表示就是:1100100,所以使用2^2,2^5,2^6三个砝码即可。任何数字都可以表示为二进制数,在这里就意味着任何重量都可以用上述2^n砝码表示。
但这是最少数量的砝码吗?
这要视情况而定,如果只能在天平的一边放砝码,另一边放物品,这就是最少的方案。因为对于砝码而言只有两种状态:放与不放,对于n个砝码,可能出现的总体状态有2^n种状态,要表示100个数据则要保证2^n>=100,得最小的n=7,意思就是说不管什么砝码方案,至少都要7个砝码。而前面我们猜想的方案正好是7个砝码,正好是理论推导出的最少砝码个数,不会比这个数目更少了,所以是一个最少的方案。
如果允许天平两边都放砝码,也就是说物品可以和砝码放在一边,上述2^n砝码方案就不是最少的方案了。
因为砝码有三种状态:不放、放左边和放右边。
对于n个砝码,可能出现的总体状态有3^n种状态,要表示100个数据则要保证3^n>=100,的最小的n=5,意思就是说不管什么砝码方案,至少都要5个砝码。
接下来我们尝试一下能不能找到5个砝码的方案。
任意一个数都可以表示成三进制的数,比如100用三进制表示就是10201,通过减法,我们又可以把任意一个三进制数化成只有0和1的形式,比如将10201化成10201=11001-100。而且减数与被减数相同位上的数字必然不会同时为1,假如化成减法形式后相同位同时为1,比如110-10,两个数的十位上都为1,结果必然是100,没有2,所以不用化简,矛盾。
综上,3^0,3^1,3^2…3^4一共5个砝码一定可以表示出从1到3^0+3^1+3^2+…+3^4=121的所有数(注:不是3^5-1)