《阿凡提巧拆金环与完备分拆课件》由会员分享，可在线阅读，更多相关《阿凡提巧拆金环与完备分拆课件（17页珍藏版）》请在金锄头文库上搜索。
1、阿凡提巧拆金环与完备分拆,目录,阿凡提是维吾尔族传说中的聪明人,在民间中流传着不少关于他机灵智巧的故事. 一次,阿凡提给巴依打短工,商定的时间是十天.三天以后,贪婪的巴依想出一个坏点子赖账.他拿出一串光灿灿的金链,当着大家的面对阿凡提打赌道:“是7个环连成的金链,如果从今天起,你能够第一天取1个环,第二天取2个环,第三天取3个环第七天取7个环,而你只准砍断一个环.那么,这串金链就归你所有.要是你办不到的话,別说金链,甚至工钱也休想拿走,十天的工作也算是白干了.”阿凡提默然应允. 他把金链的第3个环砍断,七个环的链就被分成1个,2个,4个环的小链.,第一天,阿凡提拿走1个环. 第二天,他把1个环
2、放回去拿走2个环. 第三天,他把1个与2个环一起拿走. 第四天,放回3个环拿走4个环. 第五天,把1个与4个环一起拿走. 第六天,放回1个换走2个, 即共拿走6个环. 第七天,把整条金链拿走. 愚蠢的巴依捶胸顿足地哀叹:“跟有学问的人是不能随便开玩笑的.”,文献中沒有记载过阿凡提是否学过代数或组合数学.然而,他确实用到了“数分拆”的道理.尽管,今后我们无须企望再遇见第二个如此愚蠢的巴依,然而,深入思考和探索故事中的数学,也决非只能用在打賭上.我们考察下面的问题,要解決它仍然需要阿凡提式的机智. 问题1: 有一堆重量为整数克的零件,其重量范围是1克至n克均齐备.现要用天平在一边放砝码的方法秤量它
3、们,如何选取一组砝码,使每个零件可用唯一的一中方法秤出來. 问题2: 找一组电阻,使它可用唯一的方法配成1到n 个单位齐全的电阻箱. 这类问题,在数学上称为完备分拆(perfect partition) 问题.,众所周知,7这个正整数可以写成若干个正整數之和.例如, 7=3+4=1+2+4=1+1+2+3=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
4、; 17.我们考察1,2,4,它正是阿凡提的杰作.它的特別之处在于:仅用3部分1,2,4可以唯一地表示一切不大于7的正整数的分拆(当然,故事中沒有要求唯一性).易见6=2+4,5=1+4,4=4,3=1+2,2=2,1=1, 分拆1,2,4称为7的完备分拆.,作为严格的数学定义,我们有定义 分拆和完备分拆:把正整数n 表成若干个正整数之和,叫做n 的分拆.分拆中所分成的正整数的个数称为分拆的部分数.若一个分拆包含不大于n 的所有正整数的一个唯一分拆,则这个分拆称为n 的完备分拆. 容易知道:一个正整数n的完备分拆是必定存在的.并且它的一个完备分拆是1n,称之为平凡完备分拆. 那么,自然而來的问
5、题是:我们能否把n 的所有完备分拆都找出來呢?回答是肯定的.,我们注意到一个的事实: 一个完备分拆必须含有一个部分是1,否则,它就不能包含1这个正整数的分拆. 设分拆中有q1-1个1(q11),则所有小于q1的数都必可唯一地(用1)表成分拆.但是,要把数q1表成分拆,必须有另一部分q1.若分拆的下一部分是q1(q2-1),则所有小于q1q2的数都可用1(q1-1)*q1(q2-1)唯一地表成分拆,但数q1q2表成分拆,必须要增加一部分q1q2.若分拆的下一部分是(q1q2)(q3-1)(q31),则所有小于q1q2q3的数可用1(q1-1)*q1(q2-1)*(q1q2)(q3-1)唯一地表成
6、分拆.但要把数q1q2q3表成分拆,必须增加另一部分q1q2q3. 如此继续,得(1) 它能把1,n中的所有整数唯一地表成分拆.,这里, 于是 n+1=q1q2qk. (2) 上述分析表明:n的每一个形如(1)式的完备分拆一一对应于n+1的一个形如(2)式的有序分解.(请注意:(2) 式的q1,q2,qk是有序的).于是,要找出n的所有完备分拆(1),只须做出n+1的所有有序分解(2). 归纳上述结论,得到 定理1(Rirdon 1): 正整数n 的完备分拆的个数与(n+1) 的无单位1的正因子的有序分解的个数相等.若 n+1=q1q2qk, (qi1,i=1,2,k),则n 的完备分拆是1(
7、q1-1)*q1(q2-1)*(q1q2)(q31)*(q1q2q3)(q4-1)(q1q2q(k-1)(qk-1) 或简记为n1(q1-1)*q1(q2-1)*(q1q2)(q31)*(q1q2q3)(q4-1)(q1q2q(k-1)(qk-1),例如, 求7的所有完备分拆. 解: 先把7+1=8作有序分解,得8,42,24,222. 由定理1,对应的完备分拆是1(8-1)=17;13,4;1,23;1,2,4 可以看到,只要作出了n的一个有序分解, 我们无须做出完备分拆,就能知道它的部分数Q,因为Q=(q1-1)+(q2-1)+(qk1)=(q1+q2+qk)k (3) 运用(3)式,我们
8、可以直接对上述7的完备分拆作出验证.,阿凡提不愧为聪明人.他的机灵之处不仅在于找出了7的完备分拆,而且按照巴依只准断开一个环的限制,准确地选择了7的一个部分数最小的完备分拆1,2,4.对于不大的数7,阿凡提当然能凭他的机智的直觉.然而,对于任意一个n,如何能够做到,无须把所有完备分拆罗列出來,就直接找出具有最小的部分的一个呢? 这必须依靠比阿凡提更聪明的数学了.注意到(3)式,用数学的语言表达,我们的问题是:在约束条件q1q2qk=n+1,qi2下,求目标函数(3)的最小值. 乍看起來,这似乎是一个熟知的极值问题:在k个正数积为定值时,求它们和的极小值.然而,注意到目标函数Q右边的k仍是一个变
9、量, 我们就不能用惯常的手法去求解.,为此,先证明下列 引理1: 设m= q1q2ql, qi2,i = 1,2,l且(m)=q1+q2+ql,则(m)m. 证明:因qi2,i=1,2,l, 故 引理2: 设m=q1q2qk,qi2,i=1,2,k,则当且仅当q1,q2,qk均是素数时,k最大,因而(m)最小. 证明:设m=q1q2ql (4) = p1p2pk (5) 这里(5)是m的一个素分解.熟知,若不考虑因子的次序,m的素分解是唯一的,故lk,若且唯若(4)是素分解时l=k.注意到(4)中有可能有合数的因子,依据引理1,便得p1+p2+pkq1+q2+ql. 反之,若k最大(m)最小)
10、,显然,m必是素分解.,定理2: 设n+1=q1q2qk,qi2,i=1,2,k,若且唯若q1,q2,qk均是素数时,其对应的n的完备分拆 的部分数Q=(q1+qk)-k最小. 定理2告诉我们: 对于任一个给定的正整数n, 欲做出它的部分数最小的完备分拆,只需写出n+1的素分解式并作出相应的完备分拆, 而无须把所有的完备分拆都列出來加以比较.由于n+1的素分解可有多种顺序的因子排列,故n对应的部分数最小的完备分拆不是唯一的. 具体地,若n+1=p11*p22 pkk,p1,p2,pk 是不同的素数.由定理2,容易知道,(1). n 带最小部分数的完备分拆有 部分。 (2).n带最小部分数的完备
11、分拆个数: 例如,考察35 的完备分拆.,因35+1=2232,在35的所有完备分拆中,最小部分数是2(2-1)+2(3-1)=6.这一类完备分拆共有(2+2)!/(2!2!)=6个.它们是 (1)1, 2, 42, 122 (2)1, 22, 6, 122 (3)1, 22, 62, 18 (4)12, 32, 9, 18 (5)12, 3, 62, 18 (6)12, 3, 6, 122 (想想看, 它們是怎样构作出來的?),五. 递归用电脑求出完备分拆个数,为了敘述方便,我们把n的完备分拆的个数记作Pe(n).既然,仅对于较大的n,求Pe(n)难于对付,那么,一个自然的想法是,能否把Pe
12、(n) 用一些Pe(k)(kn)表示.这就是数学上的递归思想.如果有了Pe(n)的递归式,我们就能按n的数值从小到大地求出Pe(n).运用电脑及递归式,我们将容易求得任何Pe(n). 由定理1,我们已经知道, “” 意义见定理1.,解:11+1=223,12的真因子是2,3,4,6 Pe(2-1)=1, Pe(3-1)=1, Pe(4-1)=2, Pe(6-1)=3， 故Pe(11)=Pe(1)+Pe(2)+Pe(3)+Pe(5)+1=8,这表明: k-1的一个完备分拆对应于n的一个完备分拆.易见,n+1的不同真因子k(因而,不同的k-1)的完备分拆对应于n的不同完备分拆。 最后, 我们还应注意一个事实:若n+1沒有大于1的真因子, 即n+1=q1 (等价于q1-1=n) 它一一对应于n 的平凡完备分拆n1n.于是,我们得到下列递归关系. 定理3: (6) 初始值Pe(1)=Pe(2)=1. 例: 求Pe(11).,The end,thank you!,
