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