阿凡提巧拆金环与完备分拆.ppt

阿凡提巧拆金环与完备分拆
目录
阿凡提的故事
1
并非用在打赌上
2
一一对应找出完备分析
3
数学比阿凡提更聪明
4
阿凡提是维吾尔族传说中的聪明人,在民间中流传着不少关于他机灵智巧的故事.
一次,阿凡提给巴依打短工,,,当着大家的面对阿凡提打赌道:“是7个环连成的金链,如果从今天起,你能够第一天取1个环,第二天取2个环,第三天取3个环…第七天取7个环,,,別说金链,甚至工钱也休想拿走,十天的工作也算是白干了.〞阿凡提默然应允.
他把金链的第3个环砍断,七个环的链就被分成1个,2个,4个环的小链.
第一天,阿凡提拿走1个环.
第二天,他把1个环放回去拿走2个环.
第三天,他把1个与2个环一起拿走.
第四天,放回3个环拿走4个环.
第五天,把1个与4个环一起拿走.
第六天,放回1个换走2个, 即共拿走6个环.
第七天,把整条金链拿走.
愚蠢的巴依捶胸顿足地哀叹:“跟有学问的人是不能随便开玩笑的.〞
,他确实用到了“数分拆〞,今后我们无须企望再遇见第二个如此愚蠢的巴依,然而,深入思考和探索故事中的数学,,要解決它仍然需要阿凡提式的机智.
问题1: 有一堆重量为整数克的零件,其重量范围是1克至n克均要用天平在一边放砝码的方法秤量它们,如何选取一组砝码,使每个零件可用唯一的一中方法秤出來.
问题2: 找一组电阻,使它可用唯一的方法配成1到n 个单位齐全的电阻箱.
这类问题,在数学上称为完备分拆(perfect partition) 问题.
众所周知,,
7=3+4=1+2+4=1+1+2+3=1+1+1+1+1+1+1,
这里的每一个和式,称为7的一个分拆(partition).如果和式中有r项,,2分拆,3分拆,4分拆,,我们并不考虑各局部的次序.
因此,上述各分拆可分別记为3,4; 1,2,4; 1²,2,3; ,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 的所有完备分拆都找出來呢?答复是肯定的.
我们注意到一个的事实: 一个完备分拆必须含有一个局部是1,否那么,它就不能包含1这个正整数的分拆.
设分拆中有q1-1个1(q1>1),那么所有小于q1的数都必可唯一地(用1),要把数q1表成分拆,(q2-1),那么所有小于q1q2的数都可用1ˆ(q1-1)*q1ˆ(q2-1)唯一地表成分拆,但数q1q2表成分拆,(q1q2)ˆ(q3-1)(q3>1),那么所有小于q1q2q3的数可用1ˆ(q1-1)*q1ˆ(q2-1)*(q1q2)ˆ(q3-1),必须增加另一局部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)
n+1=q1q2…qk, (qi>1,i=1,2,…,k),
那么n 的完备分拆是1ˆ(q1-1)*q1ˆ(q2-1)*(q1q2)ˆ(q3­1)*(q1q2q3)ˆ(q4-1)…(q1q