1 / 30
文档名称:

组合构造答案及讲稿.doc

格式:doc   大小:3,758KB   页数:30页
下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

组合构造答案及讲稿.doc

上传人:2286107238 2018/10/21 文件大小:3.67 MB

下载得到文件列表

组合构造答案及讲稿.doc

相关文档

文档介绍

文档介绍:【组合十讲】
组合构造
陶平生
构造法是解证组合问题的重要方法与基本手段,使用它,常常可以将问题化难为易,化抽象为直观, :数论构造法;几何构造法;模型构造法;旋转、置换(群)构造法;图表构造法;图论构造法等.
一、数论构造法
我们通过一些具体例子来说明这一方法的运用.
、空间有个点,无三点共线,现将每两点之间用一种颜色的线连接,使得对于其中任意一点而言,由该点发出的任两条线皆不同色,问至少需要多少种不同颜色的线?,情况又将如何?
解:一般化,将改为,其中正整数,线段颜色数的最小值记为,
易知,……
今证明,一般情况下有.
设个点为,由于每点都要发出条线,诸线不同色,这样至少需要色;
再证色不够,若总共只有色,,它们总共有个两两互异端点,于是,矛盾!
因此,即.
下面说明最小值可以取到,采用数论构造法:
用分别表示这色,而表示整数模的最小非负余数,即
,对于任意两点,将连线染第色,于是,对于任意一点,,假若与同色,则有
,即,得,因,故有,矛盾!故这种染色方案合于条件,因此,.
又对于个点,由于每点都要向其余点共发出条线,诸线不同色,这样至少需要色,只要证,色已足够.
构造,仍用分别表示这色,暂不考虑点,先对前个点两两间的连线依照上述个点的情形染色,我们注意到,对于其中任意两点
的连线染色时,要求,也就是说,由点发出的条线的颜色代号,,为模的完系中缺少了一个剩余.
现将点与前个点中任一点的连线染第色,由于当时与模不同余,故由点发出的条线互不同色,由其它点发出的条线也互不同色,故这种染色方案合于条件.
因此,,从而.
于是对于个点或是个点,都至少需要种颜色的线.
,利用数论构造法给出的染色方案,优美和谐,浑然天成.
、证明:可以将集合中的元素分成组,使得每组的元素和相等.
证:我们可一般化为下述命题:若奇数,则集合可以分拆成个两两不交的元素之和相等的子集之并.
在集合中添加元素,并将诸元素依自小到大的顺序排列,然后按每个数一段分成三段:.
易知,对于两个具有个项的递增连续自然数数列及,它们按相反次序相加的每两项之和为常数:即;
因此只要证,可以将第一段的个数适当排成,第二段的个数适当排成,使得恰好组成个连续自然数;(此时只要将所得的这个数与第三段的数反序相加,就得到相等的个和.)
若将第二段的每个数各减,问题又化为:若奇数,存在前个自然数的两个排列:及,使得恰好组成个连续自然数;
为此,采用构造法,设个连续自然数中,最小的一数为,
则此个数为,其和为,又据
,故由,得,
这样,问题化为:若奇数,存在前个自然数的两个排列:及,使得
,
为直观起见,记为;
注意到,时,,而;
时,,而;
时,,而;
若用记号表示整数被除得的最小非负余数,,
据上述情况可以推测,对于奇数,可以构作满足条件的两个数列,
其中,.
先说明,以及,各自通过模的最小非负完全剩余系,事实上,对每个,,并且这个中,任两个不相等,因为若有使,即,也就是,由于为奇数,则
,而,矛盾!
同理可知,,也通过模的最小非负完全剩余系;于是,分别是的一个排列;
又注意,
,,
因此构成以为最小数的个连续自然数.
于是所证的结论成立.
、给定两个正整数,其中,且;试求最小的正整数,使得在任意个满足条件:“对一切,”的整数中,都存在两个整数和,使得可被整除.
解:由于所考虑的是“被整除”这一特征,故可将题中所涉整数皆替换为“被除得的余数”来考虑;用表示整数被除得的最小正余数,即
,;
为了探求本题结论的一般性结构,先分析以下特例:
例、取,这时,且
当且仅当,即;
于是,有两种情况:、; 、,即.
问题化为,从中取个数,为了保证这个数中必有两数之差(大数减小数)为或,求的最小值.
为此,将数排列于一个圆周之上,使得相邻两两数之差(大数减小数)都为或,有右图的排法:
从其中任取个不同的数,为了保证取出的数中必有两个相邻,则至少要取六个数,即;
例、取,这时,且
当且仅当,
此时也有两种情况:;或.
将数排列于一个圆周之上,使得相邻两两数之差(大数减小数)都为或,这时排出三个圈:
此处作成三个圈是因为
的缘故.
从中任取个不同的数,为了保证取出的数中必有两个相邻,则在三个圈中,总共至少要取七个数,即;
(若总共只取六个数,可以选择每个圈上各取两个数,且不相邻,这样得到的六数不能满足条件)
现分析的数字结构:.
其中是圆周的个数;数是在同一个取出的元