六年级下册奥数讲解共2课《整数的分拆》及《图论中的匹配与逻辑推理问题》试题附答案

小学六年级下册数学奥数知识点讲解第7课《整数的分拆》试题附答案

第七讲整数的分拆

整数分拆是数论中一个既古老又活跃的问题.把自然数n分成为不计顺序的

若干个自然数之和

n=nl+n2+…+nm（nl）n2》nm》l）的一种表示法，叫做n的一种分拆.

对被加项及项数疝口以一些限制条件，就得到某种特殊类型的分拆.早在中世

纪，就有关于特殊的整数分拆问题的研究.1742年德国的哥德巴赫提出“每个

不小于6的偶数都可以写成两个奇质数的和“，这就是著名的哥德巴赫猜想，

中国数学家陈景润在研究中取得了突出的成果.下面我们通过一些例题，简单

介绍有关整数分拆的基本知识.

一、整数分拆中的计数问题

例1有多少种方法可以把6表示为若干个自然数之和？

例2有多少种方法可以把1994表示为两个自然数之和?

例3有多少种方法可以把100表示为（有飒序的）3个自然数之和？（例

如，把3+5+92与5+3+92看作为100的不同的表示法）

例4用1分、2分和5分的硬币凑成一元钱，共有多少种不同的凑法？（第

二届“华罗庚金杯”少年数学邀请赛决赛第二试第4题）

例5试把14分拆为两个自然数之和，使它们的乘积最大.

例6试把14分拆为3个自然数之和，使它们的乘积最大.

答案

第七讲整数的分拆

整数分拆是数论中一个既古老又活跃的问题.把自然数n分成为不计顺序的

若干个自然数之和

n=nl+n2+…+nm(nl)n2》nm>l)的一种表不法，叫做n的一种分拆.

对被加项及项数加口以一些限制条件，就得到某种特殊类型的分拆.早在中世

纪，就有关于特殊的整数分拆问题的研究.1742年德国的哥德巴赫提出“每个

不小于6的偶数都可以写成两个奇质数的和”，这就是著名的哥德巴赫猜想，

中国数学家陈景润在研究中取得了突出的成果.下面我们通过一些例题，简单

介绍有关整数分拆的基本知识.

一、整数分拆中的计数问题

例1有多少种方法可以把6表示为若干个自然数之和？

解：根据分拆的项数分别讨论如下：

①把6分拆成一个自然数之和只有1种方式；

②把6分拆成两个自然数之和有3种方式

6=54-1=4+2=3+3；

③把6分拆成3个自然数之和有3种方式

6=44-1+1=3+2+1=2+2+2；

④把6分拆成4个自然数之和有2种方式

6=3+1+1+1=2+24-1+1；

⑤把6分拆成5个自然数之和只有1种方式

6=2+1+1+1+1；

⑥把6分拆成6个自然数之和只有1种方式

6=1+1+1+1+14-1.因此，把6分拆成若干个自然数之和共有

1+3+3+2+1+1=11种不同的方法.

说明：本例是不加限制条件的分拆，称为无限制分拆，它是一类重要的分

拆.

例2有多少种方法可以把1994表示为两个自然数之和？

解法L采用有限穷举法并考虑到加法交换律：

1994=1993+1=1+1993

=1992+2=2+1992

=998+996=996+998

=997+997

因此，一共有997种方法可以把1994写成两个自然数之和.

解法2：构造加法算式：

1994=1+1+1+-+1+1

Iy，

1994个1相加

于是，只须考虑从上式右边的1993个加号“+”中每次确定一个，并把其

前、后的1分别相加，就可以得到一种分拆方法；再考虑到加法交换律，因此

共有997种不同的分拆方式.

说明：应用本例的解法，可以得到一般性结论：把自然数n》2表示为两个

自然数之和，一共有k种不同的方式，其中

y（n是偶数）

k=<,

彳2（n是奇数）.

例3有多少种方法可以把100表示为（有HI更序的）3个自然数之和？（例

如，把3+5+92与5+3+92看作为100的不同的表示法）

分析本题仍可运用例1的解法2中的处理办法.

解：构造加法算式

100=1+14-1+-+1+1

100个1相加

于是，考虑从上式右边的99个加号“+”中每次选定两个，并把它们所隔

开的前、中、后三段的1分别相加，就可以得到一种分拆方法.因此，把100表

示为3个自然数之和有99X98Xg=4851种不同的方式.

说明：本例可以推广为一般性结论：“把自然数n33表示为（有顺序

的）3个自然数之和.共有g（n-1）（n-2）种不同的方式“（第一届莫斯科

奥林匹克数学竞赛第10题）.

例4用1分、2分和5分的硬币凑成一元钱，共有多少种不同的凑法？（第

二届“华罗庚金杯”少年数学邀请赛决赛第二试第4题）

分析用1分、2分和5分硬币凑成一元钱与用2分和5分硬币凑成不超过一元

钱的凑法数是一样的.于是，本题转化为：“有2分硬币50个，5分硬币20个，

凑成不超过一元钱的不同凑法有多少种？

解：按5分硬币的个数分21类计数；

假若5分硬币有20个，显然只有一种凑法；

假若5分硬币有19个，则2分硬币的币值不超过100-5X19=5（分），于是2

分硬币可取0个、1个、或2个，即有3种不同的凑法；

假若5分硬币有18个，则2分硬币的币值不超过100-5X18=10（分），于是

2分硬币可取。个、1个、2个、3个、4个、或5个，即有6种不同的凑法；

…如此继续下去，可以得到不同的凑法共有：

1+3+6+8+11+13+16+18+21+…+48+51

=5X（1+3+6+8）+4X（10+20+30+40）+51

=90+400+51

=541(种).

说明：本例实际上是求三元一次不定方程x+2片5z=l00的非负整数解的组

数.

上述例2、例3、例4都是有限制条件的特殊的整数分拆问题.

二、整数分拆中的最值问题

在国内外的数学竞赛试题中经常出现与整数分拆有关的最大值或最小值的

问题.

例5试把14分拆为两个自然数之和，使它们的乘积最大.

解：由例2可知，把14分拆成两个自然数之和，共有7种不同的方式.对每

一种分拆计算相应的乘积：

14=1+13,1X13=13；

14=2+12,2X12=24；

14=3+11,3X11=33；

14=4+10,4X10=40；

14=5+9,5X9=45；

14=6+8,6X8=48；

14=7+7,7X7=49.

因此，当把14分拆为两个7之和的时候，乘积(7X7=49)最大.

说明：本例可以推广为一般性结论：“把自然数n>2分拆为两个自然数a

与b(a>b)之和，使其积aXb取最大值的条件是a=b或a-b=l(a>b)”.事实

上,截设a-b=l+m(箕中遥一个白然数)，显然n=a+b=(a-1)+(b+1),

而有(a-1)X(b+1)=aXb+a-b-1=aXb+m〉aXb.

换句话说，假设n=a+b且a-b〉l,那么乘积aXb不是最大的.这样，

若n是偶数，贝IJa=b=g时，乘积有最大值aXb=，；若n是奇数，则

a=^，b=展时，乘积有最大值aXb=一

例6试把14分拆为3个自然数之和，使它们的乘积最大.

分析由例5的说明可知，假设n=a+b+c(a》b》c)且a-c〉l时，乘积a

XbXc未是最大的.换句括说，若n=a+b+c(a3b>c),当a、b、c中的任意

两数相等或差为1时，乘积aXbXc取最大值.

解：因为14=3X4+2,由分析可知：当a=b=5且c=4时，乘积aXbXc=5X5

X4=100为最大值.

说明：本题可以推广为一般结论：把自然数n>3分拆为3个自然数a、

b,c(a)b》c)之和，若n=3q(q是自然数)，贝Ua=b=c=5时乘积

aXbXc有最大值多；若n=3q+l(q是自n+2n-1然数)，则a=「；之,

n-1,1

b=c=-j—时乘积aXbXc有最大值号(n+2)(n-1)(n-1)；若门=

3q+2(q是自然数)，则a=b=n+ln-2时乘积aXbXc有最大值，(n

+1)(n+1)(n-2).

下面我们再研究一个难度更大的拆数问题.

问题：给定一个自然数N,把它拆成若干个自然数的和，使它们的积最大.

这个问题与前面研究的两个拆数问题的不同点是：问题中没有规定把晰

成几个自然数的和.这也正是这题的难点，使分拆的种类要增加许多.我们仍旧

走实验-观察-归纳结论这条路.先选择较小的自然数5开始实验.并把数据列表

以便比较.

实验表1：

自然数5

拆分的数(1,1,1,1,1)a,Lb2)(1,1,3)(1,2,2)(1,4)(2,3)

拆分数的积123446

结果：5拆成2+3时，其积6最大.

你注意到了吗？我们的实验结果是按把5拆分数的个数多少，由多到少的

次序进行的.再注意，当被拆数n〉3时（这里n=5）,为了使拆分数的乘积最

大，拆分数中不能有1.因为当n〉3,n=l+（n-1）=2+（n-2）,且2X大-2）

>1X（n-l）.

实验表2：

自然数6

拆分的数(2,2,2)(3,3)(4,2)

拆分数的积898

结果：6拆分成3+3时，其积9最大.

实验表3:

自然数7

拆分的数(2,2,3)(3,4)⑸2)

拆分数的积121210

结果：7拆分成2+2+3时.其积12最大.

注意，分拆数中有4时，总可把4再分拆成2与2之和而不改变分拆的乘积.

实验结果4：8拆分成2+3+3时，其积最大.

实验结果5：9拆分成3+3+3时，其积最大.

实验结果6：10拆分成3+3+2+2时，其积最大.

观察分析实验结果，要使拆分数的乘积最大，拆分数都由2与3组成，其形

式有三瓶

①自然数=（若干个3的和）；

②自然数;（若干个3的和）+2；

③自然数二（若干个3的和）+2+2.

因此，我们得到结论：把一个自然数厮分成若干个自然数的和，只有当

这些分拆数由2或3组成，其中2最多为2个时，这些分拆数的乘积最大.（因为

2+2+2=3+3,2X2X2C3X3,所以分拆数中2的个数不能多于2个.）

例分别拆分1993、1994、2001三个数，使分拆后的积最大.

解：•「1993=664X3+1.

「.199盼拆成3+3+…+3+2+2时，其积最大.

\___________________________>

663个3

V1994=664X3+2

・•.1994分拆成（664个3的和）+2时，其积最大.

...2001=667X3「.2001分拆成（667个3的和）时，其积最大.

我们以上采用的“实验-观察-归纳总结”方法，在数学上叫做不完全归纳

法.我国著名数学家华罗庚讲过：难处不在于有了公式去证明，而在于没有公

式之前怎么去找出公式.不完全归纳法正是人们寻找公式的重要方法之一.但是

这种方法得出的结论有时会不正确，所以所得结论还需要严格证明.这一步工

作要等到学习了中学的课程才能进行.

习题七

1.两个十位数1111111111和9999999999的乘积中有几个数字是奇数？

2.计算：

987X655-321

666+987X654

3.计算：9999X2222+3333X3334.

4.在周长为18,边长为整数的长方形中，面积最大的长方形的长和宽各是

多少？

5.用6米长的篱笆材料在围墙角修建如下图所示的鸡圈.问鸡圈的长与宽分

别是多少时，鸡圈的面积最大？

6.把17、18两个自然数拆成若干个自然数的和，并分别求这些分拆的自然

数的乘积的最大值.

六年级奥数下册：第七讲整数的分拆习题解答

习题七解答

1.解:1111111111X9999999999

=11-1X(100-0-1)

10个110个0

=11-100-0-11-1

'---V-------V---''---V---'

10个110个010个1

=1T"1088…89

9个19个8

因此，这两个十位数的乘积中有10个数字是奇数.

2.1.

3.33330000.

4.长为5,宽为4.

5.当鸡圈的长=宽=3米时，鸡圈的面积最大.

6.17分拆成3+3+3+3+3+2时，其乘积最大，最大值是空X2=486.

18分拆成6个3的和时，其积最大，最大值是3=729.

小学六年

级下册数学奥数知识点讲解第8课《图论中的匹配与逻辑推理问题》试题附答案

第八讲图论中的匹配与逻辑推理问题

先看一个例题.中、日、韩三个足球队进行比赛，己知A不是第一名，B不

是韩国队，也不是第二名，第一名不是日本队，中国队第二.问A、B、C各代表

哪国队？各是第几名？

一般解这类题都归于逻辑推理类问题.

我们先来降低难度.先只要求你判断出中、日、韩各是第几名（不必判断

A、B、C）.可以把中、日、韩各用一个点代表，列于上一行.第一、二、三名

各用一个点代表，列于下一行，记为：

Vl=仲,日，韩｝,V2=｛第1名，第2名，第3名｝.

①②③

V1中的点与V2中某一个点有肯定关系的，就画一条实线，如⑥和②.否定

关系的两点之间画一条虚线，如⑥不是②；闻不是①.把已知条件不加任何推

理地表现于图上.虚线2条，实线1条，共3条线.

现在，有两个明显的事实；第一，VI中每点有且只有一条实线与V2中相应

点配对，V2中每点有且只有一条实线与V1中相应点配对.V1内部点之间不会有线

相联结，V2内部点之间也不会有线相联结.第二，从VI（或V2）中某一个点，例

如说a点如发出了一条实线向着V2（或V1）中某一个点，例如说x点，那么a点与

V2（或VI）中其他点之间必然只能用虚线联结.（这是逻辑推理中的排它性）

由此，我们很容易将中、日、韩的名次判出.

④回⑥

这样的问题，抽象起来可归属于图论中称之为“二分图的匹配”问题.

图论的名词术语太多，这里不作详细定义，只是描述性介绍一下，大家以

前在“一笔画”等讲中己初步接触.所谓二分图，就是顶点集合可以划分成两

个部分，V=V1+V2,如V1有P个点，记为Vl={vl,V2…,vp},V2有q个点，记

为V2={vp+1,vp+2…，vp+q},而中任意一点，不会与V1中其他点联结，而

只能与V2中某些点联结；V2也如此.大家看几个例.

一般的图记为G=（V,E）,V是顶点集合，E是边（也可称为线）的集合.

大家在哥尼斯堡七桥问题中己领略过这种抽象.现在的二分图是一类特殊的

图，只不过顶点集分为两部分，而这只能“跨越”于VI中某个点和V2中另一

个点.二分图的匹配问题，就是找一个边的集合，这些边之间都没有公共的端

点.

关于二分图的匹配，要研究的是“最大匹配”，即找一个边最多的匹配.

就本讲开始引入的问题看，我们还没有解完，因为还有A、B、C三个代号

到底如何归于中,日、韩三队的问题.一种解题办法，是把己判出的国籍和名

次捆绑在一个顶点内，如（中2）、（韩1）、（日3）,再和A、B、C构造一个

新的二分图：

/©

显然，推知B是（日3）,因为B有2条虚线，而必然有1条实线，只能推出B

与（日3）之间为实线.同理，（韩1）只能为C；剩下的唯一的情况留给了A为

（中2）.全部问题解决了.

再看最初的题目，如果你选择先判断中、日、韩和A、B、C三个代号之间

的匹配关系，将会怎样呢？画一个图看，利用已知条件画出实、虚线.

④@.

®®©

只能利用B不是韩国队及中国队第二，B不是第二（因此B不是中国队）这

样一些条件，题目中另二句话：A不是第一名，第一名不是日本队，这种否定

关系之间，没有传递性，你不能判定A是不是日本队.因此根据己知条件所画的

图中只有两条虚线，之后最多只能确定日、B之间为实线.所以对这样的二分

图，无法找出合理的最大匹配.这方法使问题求解走进了死胡同.

那么你选择先判A、B、C和第一、第二、第三名之间的匹配关系，又会怎

样呢？画一个图看.

现在也只有二条虚线,仍然无法找出最大匹配，或说解不唯一，对求解问

题无助.

现在回过头来看，先找国别与名次之间的匹配，似乎有些“碰运气”，因

为完全可以把题目改动，使先找国别与名次的匹配无法解决，例如叙述改为：

中、日、韩三足球队比赛，已知结果为：第1名不是A,第2名不是韩国队

也不是B,A不是日本队，中国队为B,问A、B、C,和1、2、3名与各国队如何

匹配？

细心读者发现，这只是把原题中A、B、C的地位与1、2、3名的地位互换而

己.所以现在改动后的题目，再先抓“国别”和“名次”的匹配，就无法求解.

但是数学要求找出一种解一般问题的方法而不是“碰运气”，而且完全可

以找一个例子，使得无论取国别与名次；或国别与代号（A,B,C）；或代号

与名次这三类二分图的匹配都无法求解，而必须找更广泛意义下的匹配才能解

决，为此先介绍一般的三个因素一起考虑的“匹配”方法.

先结合前例，将国别用三个不同点表示于上方，三个名次点表示于左下

方，三个代号点表示于右下方.用实线的肯定关系和虚线的否定关系把已知条

件“翻译”于图上.

3

我们现在的目的是要寻找一个捆绑三条实线边的一条广义边，使每个国别

与一个名次及一个代号捆绑在一起，使问题一次性解决，遵循的原则有以下4

条：

①肯定关系具有排它性（如中二第2名，则中卢第1名，中产第3名，第2名

沪日，第2名卢韩）.

②肯定关系具有传递性（如已知中=第2名，一旦推知肯定关系第2名=人，

那么中=A）.

③任意两个类别的点之间要建立一种合理的完全匹配.（如国别和名次之

间；名次与代号之间；国别与代号之间）.

④如果某一点与另一类点中除一点以外都是否定关系，那么与这一点只能

是肯定亲家.

现在把这些原则具体操作于这个图上，就能把问题求解，请读者看图，不

赘述.

=>=>

去捷己无用的国别用原则（4）

与名次间的虚线知8=日»C=韩；

又用原则C2）B=3,C=1；

反用原则（2），知A#韩，捆绑成：B=B=3,C=^=l

知中

最后则原则（3*=中=2

这类问题的思想方法上升到图论中，已经可以用一种更抽象的术语“超

图”来描述，也就是顶点集合，仍用V来表示，而超图的边是一种抽象的“广

义边“，把原来简单边捆绑在一起形成的一种“捆绑的边”.在这个具体例题

中，就是要找出一套捆绑边，每一捆绑边，捆着一个国别，一个名次，一个代

号.找出三套捆绑边，每套与别的套之间没有公共的点，也就是超图的匹配用

了这种思想方法，去解决某些逻辑推理问题，变的非常快捷而准确了.

再看例子，

有A、B、C三位大学生，一位北京人，一位上海人，一位广州人，每人的

业余爱好只是足球、围棋和歌舞三种中的一种.已知：A不喜欢足球，B不喜欢

歌舞；喜欢足球的不是上海人；喜欢歌舞的是北京人；B不是广州人.请判断三

市人的代号（指A、B、C）及爱好.

现在把此逻辑推理问题，转化为图论中的“捆绑边”匹配问题，大家不难

把此题的图和我们最初的例比较，它们完全“同构

答为：B上海人，喜欢围棋；A喜欢歌舞，北京人；C喜欢足球，广州人.

关于匹配问题本身，有很多问题和方法已经充分研究和圆满解决，并找到

了可以利用电脑解决的很好的算法.例如从二分图的求最大匹配算法发展出称

之为“交错路”的方法，直到网络上带权的最大（或最小）匹配.

六年级奥数下册：第八讲图论中的匹配与逻辑推理习题

习题八

1.小明、小强、小华三人参赛迎春杯，分别来自金城、沙市、水乡，并分

获一、二、三等奖.现知：

①小明不是金城选手；

②小强不是沙市选手；

③金城选手不是一等奖；

④沙市选手得二等奖；

⑤小强不是三等奖；问小华是何处选手，得几等奖？

2.下面是一'一般的图，有9个点，V={vl,v2,,,,,v9）,有16条边，E

={el,e2,e®.请找一个边装最多的匹配（即找一个最大匹配）.

3.有一个残缺棋盘（下图中的白格部分）.问是否可用1X2的骨牌将它完

全覆盖？

4.一张8X8的黑白相间国际象棋盘，任意挖去一个黑格和另一处的一个白

格，剩下的62格残盘，可否用31张IX2骨牌完全覆盖？

六年级奥数下册：第八讲图论中的匹配与逻辑习题解答

习题八解答

1.作图，求捆绑的边匹配.

夕明小强小华

//X

//\

金城乙—/-----\------------一等

/\

沙市乙--------------\