组合构造答案及讲稿.docx

文档介绍：【组合十讲】
组合构造
陶平生
构造法是解证组合问题的重要方法与根本手段，使用它，常常可以将问题化难为易，化抽象为直观， 它需要较强的构造转化与知识综合能力．常用的构造方法有：数论构造法；几何构造法；模型构造法；旋转、置换〔群〕构，且不相邻，这样得到的六数不能满足条件〕
现分析的数字构造：．
其中是圆周的个数；数是在同一个取出的元素个数，使得在同一个圆周上可能不存在相邻数的最大允许值，它当然与该圆周上元素的个数有关，而，；
于是猜想，一般有： ……．其中，.
今考虑一般情况：由等价于，而，所以，条件
等价于，且，
而条件等价于，即，于是
，由，得 或，
即，或，……①
记，设，那么，据①得
或 ……②
由知，，而由得；
因此由①得 ，设，；，
……③
今按的取值情况讨论：
、假设，那么②化为，或……④
且因及，由③知均不为，即，改记，那么，，于是④式可改写为对称形式：和．
引理：设，，为正整数，从中取出一个元子集，使得中的任两数之差，既不为，也不为，那么的最大值为．
采用数论构造法．为了导出一般性方法，先分析一个特例:取，将按图中顺序排列于圆周上，使得相邻两数之差或者为，或者为，而不相邻的任两数之差，既不是，也不是；假设将圆周上的
个数按顺时针方向读出，，就是：，圈中不相邻的数最多可取到个．
由于对一般的，我们不可能一个个地去构造，为此，重新研究这组数的构造，对于，不难发现，前三项分别可看作
，由此想到，后续的项当是，即是说，对于一般的，填写于圆周上的个数顺次为；
另一方面，据对称性，我们也可顺次写出，它与上面填写于圆周上的个数实际上是重合的一组，只不过是按相反的方向从圆周上读出而已．
下面证明，排在圆周上的这组数符合要求.
由，知，即，而是整数被除得的最小正余数，故上述个数，每个皆属于
；这组数中，任两个皆不相等：假假设，，那么
，即，于是
，而，矛盾！
因此就是的一个排列；
并且相邻两数之差满足：，
……⑤
由于中的数，任两个不等，，故相邻两数之差〔大数减小数〕属于集，而为模的一个完全剩余系，故其中与同余的只有，与同余的只有，因此由⑤中两式得，相邻两数之差，要么是，要么是．
因此，要想在此圆周上所取的数不含相邻数，至多只能取个数．而当取出个数时，其中必有两数相邻，其差为或．
、当时，由③得，，即，②式化为，
或，这与④的形式完全一样，因此仿照的讨论可知，对于每个，我们也分别可以得到一个含有个数的圈，使得相邻两数之差，要么是，要么是．为了在每个圈上不取到相邻的数，至多只能取个数．而当取出个数时，其中必有两数相邻，其差为或．
并且，任两个圈上的数显然不同：假假设，那么，
于是，得，矛盾！
假设取出的元素个数，那么上述个圈中，必有一个圈至少取出了个数，导致该圈上必有两数相邻，即有，使；
另一方面，假设取出的元素个数时，那么有取法，即在每个圈上各取个数，使得任两数在圈上都不相邻，这时
，
因此，适合条件的的最小值是，〔其中〕．
、支足球队进展单循环赛，即每轮将支球队分成组，每组的两队比赛一场，下一轮重新分组进展比赛，共赛轮，使得每队都与另外支球队各赛一场．按任意可行的程序比赛了轮之后，总存在支球队，它们之间总共只赛了一场；
求的最大可能值．
解：先构造一种比赛方案：将支球队顺次编号为，并按奇数与偶数分成两个子集：，，再将每场比赛的队依照其和被除的余数情况而规定轮次，并且先在同奇偶的队之间各安排场，再将“挂单〞的两个队安排一场比赛；即要求，第轮中每场比赛的队满足：．即
第一轮的：：；
第二轮的：：；
第三轮的：：；
第四轮的：：；
第五轮的：：；
第六轮的：：；
第七轮的：：；
第八轮的：：；
第九轮的：：；
在这九轮比赛中，共含有个〔奇、奇〕型搭配，个〔偶、偶〕型搭配，
而，故知在这九轮中，一切〔奇、奇〕型搭配，〔偶、偶〕型搭配均已出现，即任一对〔奇、奇〕号球队都比赛过，任一对〔偶、偶〕号球队也都比赛过．
于是，当赛完上述的九轮后，在这支球队中任取四个队，设其编号为，由于三数中必有两数同奇偶，设为，那么他们已赛过，去掉，在三数中，又有两数同奇偶，他们也已赛过；因此假设按这种分组方式进展了轮比赛之后，任何四个队之间都至少比赛过两场，于是适合条件的必应满足：．
此外，我们尚需补充说明，上述的轮比赛确实是一种符合要求安排中的前轮．即，在以上轮赛完后，我们还可以继续安排后续轮比赛，从而保证全部轮比赛可以顺利进展下去．
为此，作两个同心圆盘，且各分成个相等的扇形小格，按反时针方向顺次将九个奇数
以及九个偶数分别填入外盘及内盘的格子中，然后转动内盘，使得在前九轮中已经比赛过的每一对〔奇、偶〕型搭配，分别位