资源描述：
《阿凡提巧拆金环与完备分拆课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、阿凡提巧拆金环与完备分拆目录阿凡提的故事并非用在打赌上一一对应找出完备分析数学比阿凡提更聪明阿凡提是维吾尔族传说中的聪明人,在民间中流传着不少关于他机灵智巧的故事.一次,阿凡提给巴依打短工,商定的时间是十天.三天以后,贪婪的巴依想出一个坏点子赖账.他拿出一串光灿灿的金链,当着大家的面对阿凡提打赌道:“是7个环连成的金链,如果从今天起,你能够第一天取1个环,第二天取2个环,第三天取3个环…第七天取7个环,而你只准砍断一个环.那么,这串金链就归你所有.要是你办不到的话,別说金链,甚至工钱也休想拿走,十天的工
2、作也算是白干了.”阿凡提默然应允.他把金链的第3个环砍断,七个环的链就被分成1个,2个,4个环的小链.第一天,阿凡提拿走1个环.第二天,他把1个环放回去拿走2个环.第三天,他把1个与2个环一起拿走.第四天,放回3个环拿走4个环.第五天,把1个与4个环一起拿走.第六天,放回1个换走2个,即共拿走6个环.第七天,把整条金链拿走.愚蠢的巴依捶胸顿足地哀叹:“跟有学问的人是不能随便开玩笑的.”文献中沒有记载过阿凡提是否学过代数或组合数学.然而,他确实用到了“数分拆”的道理.尽管,今后我们无须企望再遇见第二个如此
3、愚蠢的巴依,然而,深入思考和探索故事中的数学,也决非只能用在打賭上.我们考察下面的问题,要解決它仍然需要阿凡提式的机智.问题1:有一堆重量为整数克的零件,其重量范围是1克至n克均齐备.现要用天平在一边放砝码的方法秤量它们,如何选取一组砝码,使每个零件可用唯一的一中方法秤出來.问题2:找一组电阻,使它可用唯一的方法配成1到n个单位齐全的电阻箱.这类问题,在数学上称为完备分拆(perfectpartition)问题.众所周知,7这个正整数可以写成若干个正整數之和.例如,7=3+4=1+2+4=1+1+2+3
4、=1+1+1+1+1+1+1,这里的每一个和式,称为7的一个分拆(partition).如果和式中有r项,称为r分拆.例如上述从左至右的式子可分別称为7的1分拆,2分拆,3分拆,4分拆,7分拆.在分拆中,我们并不考虑各部分的次序.因此,上述各分拆可分別记为3,4;1,2,4;1²,2,3;1ˆ7.我们考察1,2,4,它正是阿凡提的杰作.它的特別之处在于:仅用3部分1,2,4可以唯一地表示一切不大于7的正整数的分拆(当然,故事中沒有要求唯一性).易见6=2+4,5=1+4,4=4,3=1+2,2=2,1=
5、1,分拆1,2,4称为7的完备分拆.作为严格的数学定义,我们有定义分拆和完备分拆:把正整数n表成若干个正整数之和,叫做n的分拆.分拆中所分成的正整数的个数称为分拆的部分数.若一个分拆包含不大于n的所有正整数的一个唯一分拆,则这个分拆称为n的完备分拆.容易知道:一个正整数n的完备分拆是必定存在的.并且它的一个完备分拆是1ˆn,称之为平凡完备分拆.那么,自然而來的问题是:我们能否把n的所有完备分拆都找出來呢?回答是肯定的.我们注意到一个的事实:一个完备分拆必须含有一个部分是1,否则,它就不能包含1这个正整数
6、的分拆.设分拆中有q1-1个1(q1>1),则所有小于q1的数都必可唯一地(用1)表成分拆.但是,要把数q1表成分拆,必须有另一部分q1.若分拆的下一部分是q1ˆ(q2-1),则所有小于q1q2的数都可用1ˆ(q1-1)*q1ˆ(q2-1)唯一地表成分拆,但数q1q2表成分拆,必须要增加一部分q1q2.若分拆的下一部分是(q1q2)ˆ(q3-1)(q3>1),则所有小于q1q2q3的数可用1ˆ(q1-1)*q1ˆ(q2-1)*(q1q2)ˆ(q3-1)唯一地表成分拆.但要把数q1q2q3表成分拆,必须增
7、加另一部分q1q2q3.如此继续,得(1)它能把[1,n]中的所有整数唯一地表成分拆.这里,于是n+1=q1q2…qk.(2)上述分析表明:n的每一个形如(1)式的完备分拆一一对应于n+1的一个形如(2)式的有序分解.(请注意:(2)式的q1,q2,…qk是有序的).于是,要找出n的所有完备分拆(1),只须做出n+1的所有有序分解(2).归纳上述结论,得到定理1(Rirdon[1]):正整数n的完备分拆的个数与(n+1)的无单位1的正因子的有序分解的个数相等.若n+1=q1q2…qk,(qi>1,i=1
8、,2,…,k),则n的完备分拆是1ˆ(q1-1)*q1ˆ(q2-1)*(q1q2)ˆ(q31)*(q1q2q3)ˆ(q4-1)…(q1q2…q(k-1))ˆ(qk-1){或简记为n~1ˆ(q1-1)*q1ˆ(q2-1)*(q1q2)ˆ(q31)*(q1q2q3)ˆ(q4-1)…(q1q2…q(k-1))ˆ(qk-1)}例如,求7的所有完备分拆.解:先把7+1=8作有序分解,得8,4×2,2×4,2×2×2.由定理1,对应的完备分拆是1ˆ(8
