组合构造答案解析与讲稿

《组合构造答案解析与讲稿》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

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

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

3、都要向其余点共发出条线，诸线不同色，这样至少需要色，只要证，色已足够．构造，仍用分别表示这色，暂不考虑点，先对前个点两两间的连线依照上述个点的情形染色，我们注意到，对于其中任意两点的连线染色时，要求，也就是说，由点发出的条线的颜色代号，，为模的完系中缺少了一个剩余．现将点与前个点中任一点的连线染第色，由于当时与模不同余，故由点发出的条线互不同色，由其它点发出的条线也互不同色，故这种染色方案合于条件．因此，，从而．于是对于个点或是个点，都至少需要种颜色的线．下面的图形是和的情况．由此可以看到，利用数论构造法给出的染色方

4、案，优美和谐，浑然天成．、证明：可以将集合中的元素分成组，使得每组的元素和相等．证：我们可一般化为下述命题：若奇数，则集合可以分拆成个两两不交的元素之和相等的子集之并．在集合中添加元素，并将诸元素依自小到大的顺序排列，然后按每个数一段分成三段：．易知，对于两个具有个项的递增连续自然数数列及，它们按相反次序相加的每两项之和为常数：即；因此只要证，可以将第一段的个数适当排成，第二段的个数适当排成，使得恰好组成个连续自然数；（此时只要将所得的这个数与第三段的数反序相加，就得到相等的个和．）若将第二段的每个数各减，问题又化为

5、：若奇数，存在前个自然数的两个排列：及，使得恰好组成个连续自然数；为此，采用构造法，设个连续自然数中，最小的一数为，则此个数为，其和为，又据，故由，得，这样，问题化为：若奇数，存在前个自然数的两个排列：及，使得，为直观起见，记为；注意到，时，，而；时，，而；时，，而；若用记号表示整数被除得的最小非负余数，，据上述情况可以推测，对于奇数，可以构作满足条件的两个数列，其中，．先说明，以及，各自通过模的最小非负完全剩余系，事实上，对每个，，并且这个中，任两个不相等，因为若有使，即，也就是，由于为奇数，则，而，矛盾！同理可知

6、，，也通过模的最小非负完全剩余系；于是，分别是的一个排列；又注意，，，因此构成以为最小数的个连续自然数．于是所证的结论成立．、给定两个正整数，其中，且；试求最小的正整数，使得在任意个满足条件：“对一切，”的整数中，都存在两个整数和，使得可被整除．解：由于所考虑的是“被整除”这一特征，故可将题中所涉整数皆替换为“被除得的余数”来考虑；用表示整数被除得的最小正余数，即，；为了探求本题结论的一般性结构，先分析以下特例：例、取，这时，且当且仅当，即；于是，有两种情况：、；、，即．问题化为，从中取个数，为了保证这个数中必有两数

7、之差（大数减小数）为或，求的最小值.为此，将数排列于一个圆周之上，使得相邻两两数之差（大数减小数）都为或，有右图的排法：从其中任取个不同的数，为了保证取出的数中必有两个相邻，则至少要取六个数，即；例、取，这时，且当且仅当，此时也有两种情况：；或．将数排列于一个圆周之上，使得相邻两两数之差（大数减小数）都为或，这时排出三个圈：此处作成三个圈是因为的缘故．从中任取个不同的数，为了保证取出的数中必有两个相邻，则在三个圈中，总共至少要取七个数，即；（若总共只取六个数，可以选择每个圈上各取两个数，且不相邻，这样得到的六数不能满

8、足条件）现分析的数字结构：．其中是圆周的个数；数是在同一个取出的元素个数，使得在同一个圆周上可能不存在相邻数的最大允许值，它当然与该圆周上元素的个数有关，而，；于是猜测，一般有：……．其中，.今考虑一般情况：由等价于，而，所以，条件等价于，且，而条件等价于，即，于是，由，得或，即，或，……①记，设，则，据①得或……②由知，，而由得；因此由①得，