组合构造答案与讲稿

组合构造答案与讲稿

ID:47530487

大小:3.77 MB

页数:38页

时间:2020-01-13

组合构造答案与讲稿_第1页
组合构造答案与讲稿_第2页
组合构造答案与讲稿_第3页
组合构造答案与讲稿_第4页
组合构造答案与讲稿_第5页
资源描述:

《组合构造答案与讲稿》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、......【组合十讲】组合构造陶平生构造法是解证组合问题的重要方法与基本手段,使用它,常常可以将问题化难为易,化抽象为直观,它需要较强的结构转化与知识综合能力.常用的构造方法有:数论构造法;几何构造法;模型构造法;旋转、置换(群)构造法;图表构造法;图论构造法等.一、数论构造法我们通过一些具体例子来说明这一方法的运用.、空间有个点,无三点共线,现将每两点之间用一种颜色的线连接,使得对于其中任意一点而言,由该点发出的任两条线皆不同色,问至少需要多少种不同颜色的线?证明你的结论.若将个点改为个点,情况又将如何?解:一般化,将改为,其中正整数,线段颜色数的最小值记为,易知,…

2、…今证明,一般情况下有.设个点为,由于每点都要发出条线,诸线不同色,这样至少需要色;再证色不够,若总共只有色,则每点都要恰好属于各色线的端点一次.现在设总共有条红色线,它们总共有个两两互异端点,于是,矛盾!因此,即.下面说明最小值可以取到,采用数论构造法:用分别表示这色,而表示整数模的最小非负余数,即,对于任意两点,将连线染第色,参考材料......于是,对于任意一点,发自的任两条线皆不同色.事实上,假若与同色,则有,即,得,因,故有,矛盾!故这种染色方案合于条件,因此,.又对于个点,由于每点都要向其余点共发出条线,诸线不同色,这样至少需要色,只要证,色已足够.构造,仍用

3、分别表示这色,暂不考虑点,先对前个点两两间的连线依照上述个点的情形染色,我们注意到,对于其中任意两点的连线染色时,要求,也就是说,由点发出的条线的颜色代号,,为模的完系中缺少了一个剩余.现将点与前个点中任一点的连线染第色,由于当时与模不同余,故由点发出的条线互不同色,由其它点发出的条线也互不同色,故这种染色方案合于条件.因此,,从而.于是对于个点或是个点,都至少需要种颜色的线.下面的图形是和的情况.由此可以看到,利用数论构造法给出的染色方案,优美和谐,浑然天成.参考材料......、证明:可以将集合中的元素分成组,使得每组的元素和相等.证:我们可一般化为下述命题:若奇数,

4、则集合可以分拆成个两两不交的元素之和相等的子集之并.在集合中添加元素,并将诸元素依自小到大的顺序排列,然后按每个数一段分成三段:.易知,对于两个具有个项的递增连续自然数数列及,它们按相反次序相加的每两项之和为常数:即;因此只要证,可以将第一段的个数适当排成,第二段的个数适当排成,使得恰好组成个连续自然数;(此时只要将所得的这个数与第三段的数反序相加,就得到相等的个和.)若将第二段的每个数各减,问题又化为:若奇数,存在前个自然数的两个排列:及,使得恰好组成个连续自然数;为此,采用构造法,设个连续自然数中,最小的一数为,参考材料......则此个数为,其和为,又据,故由,得,

5、这样,问题化为:若奇数,存在前个自然数的两个排列:及,使得,为直观起见,记为;注意到,时,,而;时,,而;时,,而;若用记号表示整数被除得的最小非负余数,,据上述情况可以推测,对于奇数,可以构作满足条件的两个数列,其中,.先说明,以及,各自通过模的最小非负完全剩余系,事实上,对每个,,并且这个中,任两个不相等,因为若有使,即,也就是,由于为奇数,则,而,矛盾!参考材料......同理可知,,也通过模的最小非负完全剩余系;于是,分别是的一个排列;又注意,,,因此构成以为最小数的个连续自然数.于是所证的结论成立.、给定两个正整数,其中,且;试求最小的正整数,使得在任意个满足条

6、件:“对一切,”的整数中,都存在两个整数和,使得可被整除.解:由于所考虑的是“被整除”这一特征,故可将题中所涉整数皆替换为“被除得的余数”来考虑;用表示整数被除得的最小正余数,即,;为了探求本题结论的一般性结构,先分析以下特例:例、取,这时,且当且仅当,即;于是,有两种情况:、;、,即.问题化为,从中取个数,为了保证这个数中必有两数之差(大数减小数)为或,求的最小值.为此,将数排列于一个圆周之上,使得相邻两参考材料......两数之差(大数减小数)都为或,有右图的排法:从其中任取个不同的数,为了保证取出的数中必有两个相邻,则至少要取六个数,即;例、取,这时,且当且仅当,此

7、时也有两种情况:;或.将数排列于一个圆周之上,使得相邻两两数之差(大数减小数)都为或,这时排出三个圈:此处作成三个圈是因为的缘故.从中任取个不同的数,为了保证取出的数中必有两个相邻,则在三个圈中,总共至少要取七个数,即;(若总共只取六个数,可以选择每个圈上各取两个数,且不相邻,这样得到的六数不能满足条件)现分析的数字结构:.其中是圆周的个数;数是在同一个取出的元素个数,使得在同一个圆周上可能不存在相邻数的最大允许值,它当然与该圆周上元素的个数有关,而,;于是猜测,一般有:…….其中,.今考虑一般情况:由等价于,而,所以,条件参

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。