最省砝码设置问题的数学模型.doc

１最省砝码设置问题的数学模型最省砝码设置问题的数学模型【摘要摘要】通过对砝码的最省设置问题的研究，建立了解决这一类问题的数学模型，并 给出了一个有效、简便、操作程序化的求解算法 【关键词关键词】砝码，数学模型，算法，猜想砝码的最省设置问题砝码的最省设置问题：：用一架天平分别称出1克—n克不同物体的重量，最少需要几个 天平砝码?砝码各重多少克? 我们可以把部分砝码当作“物体”，与物品放在一边，天平平衡时，“砝码”一边的 砝码重量之和减去“物体”一边的砝码重量之和就是物体的重量1 1 数学实验数学实验我们用枚举法，使用计算机做数学实验用一架天平“称出”1克至n克的不同物体的 重量，最少砝码数k和相应个数砝码的取法m的实验结果列入下表：n12345678910111213141415151616 最少砝码数 k1222333333333444 砝码取法种数 m123118222619199431 761 890880n17181920212223242526272829303132最少砝码数 k4444444444444444 砝码取法种数 m920 906 877 719 712 561 469 415 309 227 205 153 106886246n333334343535363637373838393940404141……7777……120120 121121 最少砝码数 k444444445 …5 …55砝码取法种数 m36261714943130642 …8796 …21设,我们归纳发现：k kt33331321猜想：猜想：用一架天平分别称出1克—n克不同物体的重量，如果，则最少需kktnt1要k+1个砝码。

对所有的自然数n，砝码可取当时，它是砝码的)3 ,,3 ,3 , 3 , 1 (32kktn 唯一取法2 2 数学模型数学模型为了叙述的方便，设集合P=，，记 }, 3 , 2 , 1 , 0{nnmmml211),,,(21lmmm}101|{2211或或illxmxmxmx),,,(21lmmm}0, 101|{12211 liiiillmxxmxmxmx且或或（1）若或，我们称为P的Pmmml),,,(21Pmmml),,,(21lmmm,,21代数生成元组2）代数生成元组的最小个数称为集合P的代数维数具有个生成元的代)(P)(P２数生成元组称为极小代数生成元组3）是P的极小代数生成元组，对每一个都可以唯一地表示成：),,,()(21PmmmPm，（） ，则称为P的标准代)()(2211PPmxmxmxm10或ix)(21,,,Pmmm数生成元组由数论中知识，我们有下面与带余除法完全类似的一个正确结论：引理引理1：：对任意的自然数，存在唯一的整数和，使得（aqrrqa 3） 。

101或或r命题命题1：：对任意自然数，令（[x]为不超过x的最大整数）,则n]2[log3nk 是集合P=的一个代数生成元组)3 ,,3 , 3 , 1 (2k}, 2 , 1 , 0{n证明：证明：，对任意的自然数，即，可以类似十进制]2[log3nk Pmktnm0数转换成二进制数的“除2取余法” ，我们可以作一系列的“带余除法”,直到商数等于零为 止：003rqm1103r2213r……其中=-1或0或1（） lllr31irli,...,2 , 1 , 0从上面式子可得：，（） ，由此可推出3100mq3101i ili,...,2 , 1，所以，从而有，即上述的“带余除法”130ii itmq132 3011kk kk kttnq0kq最多做k+1步后商数为零如果，我们可从上面“带余除法”等式推出：)(0klql133 .3 .011 1 rrrrml ll l)(kl 我们已证明：对任意的自然数， Pm（为-1或0或1）；而且容易证明其表示式kk kkxxxxxm333311 22 10ix是唯一的（证明略）。

所以是集合P=的一个代数生成元组)3 ,,3 , 3 , 1 (2k}, 2 , 1 , 0{n记，，则}, 2 , 1 , 0 , 1, 2,{kkkttP},, 3 , 2 , 1 , 0{kktNklNmmm),,,(21klPmmm),,,(21３命题命题3 3：：集合的代数维数为k+1，是唯一的极小},, 3 , 2 , 1 , 0{kktN)3 ,,3 , 3 , 1 (2kkN代数生成元组,也是唯一的标准代数生成元组证明：证明：由命题1可知，有一组代数生成元，所以kN)3 ,,3 , 3 , 1 (2k1)( kNk设，为的任意代数生成元组，，由于lNk)(lmmm,,21kNl lmmm3| ),,,(|21的对称性，的正项与负项的项数相等，从而，1213| ),,,(|21llmmm，由，得, 从而有2131kkNkkkNmmmm),,,,(1211 kl1)( kNk设为的极小代数生成元组，则121,,,kkmmmmkNkkkNmmmm),,,,(121从而，所以，由此可以推出kkPmmm),,,(1211 1213| ),,,(| k kmmm，即互不相同，且≠kkktmmmm1211),,,(121kxxx时，有。

),,,(121kyyy112211112211kkkkmymymymxmxmx（否则）从而有为标准代数生成||3| ),,,(|1 121kk kPmmm  121,,,kmmmkP元组，且=下面我们将按的系数不同分为三类：kP),,,,(121kkmmmmkPim},,,,,,(}0{111111111111kiikkiiiiimmmmmxmxmmxmxA，}1{11111111kkiiiiimxmxmmxmxB}|{Aamai，则}) 1({11111111kkiiiiimxmxmmxmxC}|{Aamai，且，kCBA3||||||CBCABACBAPk,,, ①若，则；②若，则；③若，则BbAmbiAaCmaiCcBmci（这是因为：，否则 ，也有，否则CmciAmmccii)(Amci)设Bmmccii)(,11121mmmmmmmkkii，所以是最大的个元素，又因为是的最大kitmmimmmm,, 2, 1kPimmA元素，从而它们不是的元素；它们也不是中元素（否则它们每个元素加上后ACim４是的元素，而这些元素已不在中）；所以它iiiimmmmmmm,,2,1AkP们是中的元素；应是中元素；Bmmmmmii,, 2, 1A应是中元素，iiimmmmmm,, 22, 12C又是中元素……，由可以得出，iiimmmmmm2,, 23, 13B||||||CBA依大小次序排列可分为段，每段个元素，且交替为、和},, 3 , 2 , 1 , 0{kktPl 3imAB的元素组，从而有，从而是3的幂，即(i=1,2,…,k, k+1)。

C||31 kkPiml 3imt im3又，所以(i=1,2,…,k, k+1)从而证明了1 12131 k kktmmm13i im是的唯一的极小元代数生成元组，也是唯一的标准代)3 ,,3 , 3 , 1 (2k},, 3 , 2 , 1 , 0{kktN数生成元组推论推论1：：当对任意的自然数,集合P=的算术维数n}, 3 , 2 , 1 , 0{n)(P1]2[log3n证明：证明：令,则，因为， ]2[log3nk kktnt1kkNPN11)()()(1kNPNkkk综上所述，我们实际上已证明了猜想在解题的过程中，我们建立了解决这一类问题的数学模型：设集合P=，则 （其中）是P的极}, 3 , 2 , 1 , 0{n)3 ,,3 , 3 , 1 (2k]2[log3nk 小代数生成元组，也是标准代数生成元组即P中的每一个元素均能唯一地表示成的代数和（即系数可以为-1或0或1），并可采有特殊的“除3取余法”来求)3 ,,3 , 3 , 1 (2k表达式当时，是P唯一的极小代数生成元组,也是唯一的标准代数生ktn )3 ,,3 , 3 , 1 (2k成元组。

3 3解释与应用解释与应用问题问题1 1 用一架天平分别称出1克—40克不同物体的重量，最少需要几个天平砝码?砝码 各重多少克?如何进行操作？解：解：取，3)]402([log3k，故砝码只能取1克、3克、9克、27克4021343t（唯一的选取方法） 如果物体重量是22克，我们可以作“带余除法”， 用左边的“除法”算式表示，我们得到：322“余数”37132131-101５11319) 1(27111313) 1(312223即把27克、3克和1克的砝码放在天平的一边，物品与9克砝码放在天平的另一边，若天 平平衡，物体的重量为22克问题问题2 2：：在集合P=选取极少的几个数，使得这几个数能以加减运算组成}31, 3 , 2 , 1 , 0{另一些数解：解：，可以选取1、3、9、27（还可能有其它选法），用3)]312([log3k1、3、9、27以加减运算组成0—31各数，可用上述特殊的“除3取余法”4 4问题的拓展问题的拓展对于砝码的最省设置问题，如果按人们习惯，天平称物品是砝码和物品各一边，天平 平衡时，砝码的重量之和就是物体的重量的，那么答案就不一样了：要用一架天平分别称出1克—n克不同物体的重量，令（[x]为不超过x的][log2nk 最大整数），则至少需要k+1个砝码,砝码可取。

当=)2 ,,2 ,2 , 2 , 1 (32kn时，它是砝码的唯一取法k222121相应的数学模型：设集合P=，则 （其中）}, 3 , 2 , 1 , 0{n)2 ,,2 , 2 , 1 (2k][log2nk 是P的极小算术生成元组，也是标准算术生成元组即P中的每一个元素均能唯一地表示成的算术和（系数只能是0或者1），并可采用化十进制为二进制数的 “除2)2 ,,2 , 2 , 1 (2k取余法”来求表达式当时，是P唯一的极小算术生成元组,也是唯ksn )2 ,,2 , 2 , 1 (2k一的标准算术生成元组将有限集合P延伸为自然数集合N，则标准代数生成元组也无限延伸，)3 ,,3 , 3 , 1 (2k从而数学模型的内容也随之得到扩展是自然数集合N的极小代数生成元)3 ,,3 , 3 , 1 (2k组，也是标准代数生成元组即每一个自然数均能唯一地表示成的代数)3 ,,3 , 3 , 1 (2k和，并可采有特殊的“除3取余法”来求表达式应该指出：天平砝码问题已不再只是一个简单的物理问题或数学游戏问题，它与很多 数学问题有密切的联系，在生活、生产实际中也有较广泛的应用。

参考文献：参考文献： [1]杨世明，王雪芹.数学发现的艺术[M] .青岛：青岛海洋大学出版社,1998．６[2] 吕宪军.由一个重要数列谈数学模型的建立[J].小学数学教师,2002,。