天平称重问题
本文研究两个问题:
1、用n个砝码,最多能称出多少种不同的重量?
2、1克到Y克的所有重量,最少要几个砝码才能称出?怎样设计这些砝码?
分两种情况:一是砝码和重物不能放在同一个盘中;二是砝码和重物可以放在同一个盘中。
先探讨第一种情况,砝码和重物不能放在同一个盘中时,问题的解:
1、用n个砝码,最多能称出多少种不同的重量?
既是砝码和重物不能放在同一个盘中,就是天平的一边放重物,另一边放砝码,那么,每个砝码都有放在盘中与放在盘外两种摆放法。根据乘法原理,n个砝码就有2n种摆放法。去掉称量0克重物(砝码都放在盘外)的一种摆放法,这n个砝码有2n-1种不同摆放法。若要达到称出最多种不同重量的
目的,也就是每种不同的摆法对应一种不同的重量,这n个砝码还得满足两个条件:一是每个砝码的重量互不相等,二是其中任一个的重量都不等于其它两个或几个砝码的重量的和。这样的n个砝码最多能称出2n-1种不同重量。
若砝码和重物不能放在同一个盘中,用n个互不相等的且其中任一个都不等于其它两个或几个重量的和的砝码,最多能称出2n-1种不同的重量。
如:4个这样的砝码最多能称出(24-1=)15种不同重量。
3个这样的砝码最多能称出(23-1=)7种不同重量。
更深入的探讨:
因为每个砝码有两种摆法,所以,运用二进制知识来进行研究会有新发现。
把十进制数Y表示成n位二进制数是
Y=[Cn-1······C2C1C0]2=C0+2C1+4C2+······+2n-1Cn-1
让每一个数位代表一个砝码,其中C0、C1、C2······Cn-1
取值为0或1,分别表示砝码放在盘外或放在盘内。由此可知,若把砝码设计成1克、2克、4克······2n-1克,用n个这样的砝码可以称出1克到2n-1克的所有重量。
一般的,若砝码和重物不能放在同一个盘中,用重量为1克、2克、22
克······2n-1克的n个砝码,可以称出从1克到2n-1克的所有重量。
比如:用1克、2克、4克3个砝码可称出1克到(23-1=)7克的所有重量。
用1克、2克、4克、8克4个砝码可称出1克到(24-1=)15克的所有重量。
2、1克到Y克的所有重量,最少要几个砝码才能称出?怎样设计这些砝码?
由问题1的研究可知,只要把十进制数Y表示成n位二进制数,得出n的值,就知道最少要用多少个(n个)砝码才能称出从1克到Y克的所有重量。
这些砝码可设计为1克、2克、4克······2n-1克。
比如:1克到31克的所有重量,最少要几个砝码才能称出?怎样设计这些砝码?1克到34克呢?
因为31=[11111]2,是个5位二进制数,所以,最少要用5个砝码才可以称出从1克到31克的所有重量。
这些砝码可设计为1克、21克=2克、22克=4克、23克=8克、25-1克=16克。
34=[100010]2,是个6位二进制数,所以最少用6个砝码才可以称出1克到34克的所有重量。
这些砝码是1克、21克=2克,22克=4克、23克=8克、24克=16克、26-1克=32克。
探讨第二种情况,砝码和重物可以放在同一个盘中时,问题的解:
1、用n个砝码,最多能称出多少种不同的重量?
要达到称出最多种重量的目的,砝码得满足两个条件:一是每个砝码的重量互不相等;二是其中任一个的重量都不等于其它两个或几个砝码的重量的和或差。砝码和重物可以放在同一个盘中,就是说每个砝码都有放在天平左边的盘中、右边的盘中、天平外边三种不同的摆法。根据乘法原理,n个砝码就有3n种不同的摆法。除去称量0克重物(这时砝码都放在盘外)这一种摆法,n个砝码还有3n-1种有效的不同摆法。因为天平是对称的,把天平左右两边放置的砝码和重物对换,这两种摆法对应的是同一种重量,可知每两种摆法对应一种同样的重量。就是说这n个砝码最多能称量出1/2(3n-1)种不同的重量。
若砝码和重物可以放在同一个盘中,用n个互不相等的且其中任一个的重量都不等于其它两个或几个砝码的重量的和或差的砝码,最多可以称量出1/2(3n-1)种不同的重量。
比如:3个这样的砝码能称出[1/2(33-1)=]13种不同的重量。
因为每个砝码都有三种不同的摆法,所以可用三进制知识来进行更深入的研究。
把十进制数Y表示成n位三进制数是
Y=[Cn-1······C2C1C0]3=C0+31C1+32C2+······+3n-1Cn
-1
让每一个数位代表一个砝码,根据需要作点改变,引进个负余数,让其中C0、C1、C2······Cn-1取值不再是0、1、2,而记成-1、0、1,就是当余数是2时,用负余数表示,特记作-1。比如5÷3=1······2,现在不这样记,而记成5÷3=2······(-1)。再赋予-1、0、1新的含义,分别表示砝码与重物放在一起、放在盘外、放在重物的另一端。由此可知,只要把砝码设计成1克、31克、32克、······3n-1克,这样的n个砝码就能称出从1克到1/2(3n-1)克的所有重物。
一般的,若砝码和重物可以放在同一个盘中,用1克、3克、32克······3n-1克的n个砝码,可以称量出从1克到1/2(3n-1)克的所有重量。
下面来证明上面这个命题的正确性。
①当n=1时,只一个砝码1克,也就只能称量出1克的重量,这时
1/2(3n-1)=1/2(31-1)=1,原命题成立。
②假设n=k(k≥1,k是自然数)时原命题成立,就是
若砝码和重物可以放在同一个盘中,用1克、3克、32克······3k-1克的k个砝码,可以称量出从1克到1/2(3k-1)克的所有重量。
若要称量1/2(3k-1)+1克的重量,增加一个砝码3k克,由
3k-1/2(3k-1)=1/2(3k-1)+1,可称出。
再由3k分别减去1/2(3k-1)-1、1/2(3k-1)-2……2、1、0,就可称出从1/2(3k-1)+2克到3k克的所有重量。
又由3k分别加上1克、2克……1/2(3k-1)克,就可称出从3k+1克到3k+1/2(3k-1)=1/2(3k+1-1)克的所有重量。
就是当n=k+1(k≥1,k是自然数)时,用1克、3克、32克······3k-1克、3k克的k+1个砝码,可以称量出从1克到1/2(3k+1-1)克的所有重量。
原命题成立。
综合①②,对一切自然数n(n≥1,n是自然数)原命题都成立。
应用:
如:用1克、3克、9克这3个砝码,可称出从1克到[1/2(33-1)=]13克的所有重量;
用1克、3克、9克、27克这4个砝码,可称出从1克到[1/2(34-1)=]40克的所有重量。
2、1克到Y克的所有重量,最少要几个砝码才能称出?怎样设计这些砝码?
只要把十进制数Y表示成n位三进制数(余数用-1、0、1表示),得出n的值,就知道最少用多少个(n个)砝码就能称出从1克到Y克的所有重量。
这些砝码可设计为1克、3克、9克······3n-1克。
比如:若砝码和重物可以放在一起,要称量从1克到15克的所有重量,最少要几个砝码?怎样设计这些砝码?若是从1克到121克呢?
15=[1(-1)(-1)0]3,是个4位数,所以最少要用4个砝码,这些砝码是1克、31克=3克、32克=9克、34-1克=27克。
121=[11111]3,是个5位数,所以最少要用5个砝码,这些砝码是1克、31克=3克、32克=9克、33克=27克、35-1克=81克。