《数学自主招生精品讲练组合构造法》由会员分享，可在线阅读，更多相关《数学自主招生精品讲练组合构造法（33页珍藏版）》请在金锄头文库上搜索。
1、【组合十讲】组合构造构造法是解证组合问题的重要方法与基本手段，使用它，常常可以将问题化难为易，化抽象为直观， 它需要较强的结构转化与知识综合能力常用的构造方法有：数论构造法；几何构造法；模型构造法；旋转、置换（群）构造法；图表构造法；图论构造法等、空间有个点，无三点共线，现将每两点之间用一种颜色的线连接，使得对于其中任意一点而言，由该点发出的任两条线皆不同色，问至少需要多少种不同颜色的线？证明你的结论若将个点改为个点，情况又将如何？、证明：可以将集合中的元素分成组，使得每组的元素和相等、给定两个正整数，其中，且；试求最小的正整数，使得在任意个满足条件：“对一切，”的整数中，都存在两个整数和，使
2、得可被整除、支足球队进行单循环赛，即每轮将支球队分成组，每组的两队比赛一场，下一轮重新分组进行比赛，共赛轮，使得每队都与另外支球队各赛一场按任意可行的程序比赛了轮之后，总存在支球队，它们之间总共只赛了一场；求的最大可能值、集合组由个五元集组成，其中任意两个集合的交都不是空集，令，中含有元素的集合数目为，记，求的最小值、在一个圆周上给定个点求最小的正整数，使得以这个点为顶点的任意个三角形中，必存在两个有公共边的三角形、将时钟盘面上标有数字的十二个点分别染上红、黄、蓝、绿四色，每色三个点，现以这些点为顶点构作个凸四边形，使其满足：（）每个四边形的四个顶点染有不同的颜色；（）对于其中任何三个四边形，
3、都存在某一色，染有该色的三个顶点所标数字互不相同求的最大值、设有个正整数及，满足：证明：可以从方格表中选出个方格，在选出的每格中各填写一个自然数，使得表中第行的填数和为，而第列的填数和为、一百个正数满足：，证明：中必有三数之和大于、平面上给定个点，无三点共线，现将每两点用一线段连接，并在每条线段上配置一个箭头，以给定点为顶点的三角形称为“环形”的，如果从任一顶点出发，沿箭头方向可环绕三角形周界行走一周，而返回原出发顶点；试求环形三角形个数的最大值与最小值、设的个七元子集满足：、，；、对于的任何元子集，都存在某个，使得求这组子集个数的最小值、给定个正整数，若其中至少有对数互质，证明：其中必存在四
4、个数，满足：、个正整数的和为，如果这个数既可分为和相等的个组，又可分为和相等的个组，求的最小值、设，求最小的正整数，使得的任一个元子集中，都存在两个不同的数和，满足：、数学奥林匹克集训队中共有名队员，其中每人在队中具有同样多的朋友，已知在一次考试中，所有人的得分各不相同；若某个队员在他的朋友圈中比多数人的得分都高，则称该队员为“高手”，问集训队中至多有几名“高手”？、（售票问题）个游客排队购买参观票，每张票价元，其中人各持有一张元币，另外人各持有一张元币，开初时售票机中无零钱可找，试确定，使得不发生售票困难的排队方法有几种？、对于正整数，证明：（单身汉引理）、一副纸牌共张，其中“方块”、“梅花
5、”、“红心”、“黑桃”每种花色的牌各张，标号依次是，其中相同花色、相邻标号的两张牌称为“同花顺牌”，并且与也算是顺牌（即可以当成使用）. 试确定，从这副牌中取出张牌，使每种标号的牌都出现，并且不含“同花顺牌”的取牌方法数、将周长为的圆周等分成段，从个分点中选取个点，使得其中任何两点间所夹的弧长都不等于和；问满足要求的点组的不同取法共有多少种？说明理由【组合十讲】组合构造构造法是解证组合问题的重要方法与基本手段，使用它，常常可以将问题化难为易，化抽象为直观， 它需要较强的结构转化与知识综合能力常用的构造方法有：数论构造法；几何构造法；模型构造法；旋转、置换（群）构造法；图表构造法；图论构造法等一
6、、数论构造法我们通过一些具体例子来说明这一方法的运用、空间有个点，无三点共线，现将每两点之间用一种颜色的线连接，使得对于其中任意一点而言，由该点发出的任两条线皆不同色，问至少需要多少种不同颜色的线？证明你的结论若将个点改为个点，情况又将如何？解：一般化，将改为，其中正整数，线段颜色数的最小值记为，易知， 今证明，一般情况下有设个点为，由于每点都要发出条线，诸线不同色，这样至少需要色；再证色不够，若总共只有色，则每点都要恰好属于各色线的端点一次现在设总共有条红色线，它们总共有个两两互异端点，于是，矛盾！因此，即下面说明最小值可以取到，采用数论构造法：用分别表示这色，而表示整数模的最小非负余数，即
7、，对于任意两点，将连线染第色，于是，对于任意一点，发自的任两条线皆不同色事实上，假若与同色，则有，即，得，因，故有，矛盾！故这种染色方案合于条件，因此，又对于个点，由于每点都要向其余点共发出条线，诸线不同色，这样至少需要色，只要证，色已足够构造，仍用分别表示这色，暂不考虑点，先对前个点两两间的连线依照上述个点的情形染色，我们注意到，对于其中任意两点的连线染色时，要求，也就是说，由点发出的条线的颜色代号，为模的完系中缺少了一个剩余现将点与前个点中任一点的连线染第色，由于当时与模不同余，故由点发出的条线互不同色，由其它点发出的条线也互不同色，故这种染色方案合于条件因此，从而于是对于个点或是个点，都
8、至少需要种颜色的线 下面的图形是和的情况由此可以看到，利用数论构造法给出的染色方案，优美和谐，浑然天成、证明：可以将集合中的元素分成组，使得每组的元素和相等证：我们可一般化为下述命题：若奇数，则集合可以分拆成个两两不交的元素之和相等的子集之并在集合中添加元素，并将诸元素依自小到大的顺序排列，然后按每个数一段分成三段：易知，对于两个具有个项的递增连续自然数数列及，它们按相反次序相加的每两项之和为常数：即；因此只要证，可以将第一段的个数适当排成，第二段的个数适当排成，使得恰好组成个连续自然数；（此时只要将所得的这个数与第三段的数反序相加，就得到相等的个和）若将第二段的每个数各减，问题又化为：若奇数
9、，存在前个自然数的两个排列：及，使得恰好组成个连续自然数；为此，采用构造法，设个连续自然数中，最小的一数为，则此个数为，其和为，又据，故由，得，这样，问题化为：若奇数，存在前个自然数的两个排列：及，使得，为直观起见，记为；注意到，时，而；时，而；时，而；若用记号表示整数被除得的最小非负余数，据上述情况可以推测，对于奇数，可以构作满足条件的两个数列，其中，先说明，以及，各自通过模的最小非负完全剩余系，事实上，对每个，并且这个中，任两个不相等，因为若有使，即，也就是，由于为奇数，则，而，矛盾！同理可知，也通过模的最小非负完全剩余系；于是，分别是的一个排列；又注意，因此构成以为最小数的个连续自然数于
10、是所证的结论成立、给定两个正整数，其中，且；试求最小的正整数，使得在任意个满足条件：“对一切，”的整数中，都存在两个整数和，使得可被整除解：由于所考虑的是“被整除”这一特征，故可将题中所涉整数皆替换为“被除得的余数”来考虑；用表示整数被除得的最小正余数，即，；为了探求本题结论的一般性结构，先分析以下特例：例、取，这时，且当且仅当，即；于是，有两种情况：、； 、，即问题化为，从中取个数，为了保证这个数中必有两数之差（大数减小数）为或，求的最小值.为此，将数排列于一个圆周之上，使得相邻两两数之差（大数减小数）都为或，有右图的排法：从其中任取个不同的数，为了保证取出的数中必有两个相邻，则至少要取六个
11、数，即；例、取，这时，且当且仅当， 此时也有两种情况：；或将数排列于一个圆周之上，使得相邻两两数之差（大数减小数）都为或，这时排出三个圈：此处作成三个圈是因为的缘故从中任取个不同的数，为了保证取出的数中必有两个相邻，则在三个圈中，总共至少要取七个数，即；（若总共只取六个数，可以选择每个圈上各取两个数，且不相邻，这样得到的六数不能满足条件）现分析的数字结构：其中是圆周的个数；数是在同一个取出的元素个数，使得在同一个圆周上可能不存在相邻数的最大允许值，它当然与该圆周上元素的个数有关，而，； 于是猜测，一般有： 其中，.今考虑一般情况：由等价于，而，所以，条件等价于，且，而条件等价于，即，于是，由，
12、得 或，即，或，记，设，则，据得或 由知，而由得；因此由得 ，设，；， 今按的取值情况讨论：、若，则化为，或 且因及，由知均不为，即，改记，则，于是式可改写为对称形式：和引理：设，为正整数，从中取出一个元子集，使得中的任两数之差，既不为，也不为，则的最大值为采用数论构造法为了导出一般性方法，先分析一个特例:取，将按图中顺序排列于圆周上，使得相邻两数之差或者为，或者为，而不相邻的任两数之差，既不是，也不是；若将圆周上的个数按顺时针方向读出，就是：，圈中不相邻的数最多可取到个由于对一般的，我们不可能一个个地去构造，为此，重新研究这组数的结构，对于，不难发现，前三项分别可看作，由此想到，后续的项当是
13、，即是说，对于一般的，填写于圆周上的个数顺次为；另一方面，据对称性，我们也可顺次写出，它与上面填写于圆周上的个数实际上是重合的一组，只不过是按相反的方向从圆周上读出而已下面证明，排在圆周上的这组数符合要求.由，知，即，而是整数被除得的最小正余数，故上述个数，每个皆属于；这组数中，任两个皆不相等：假若，则，即，于是，而，矛盾！因此就是的一个排列；并且相邻两数之差满足：， 由于中的数，任两个不等，故相邻两数之差（大数减小数）属于集，而为模的一个完全剩余系，故其中与同余的只有，与同余的只有，因此由中两式得，相邻两数之差，要么是，要么是因此，要想在此圆周上所取的数不含相邻数，至多只能取个数而当取出个数
14、时，其中必有两数相邻，其差为或、当时，由得 ，即，式化为，或，这与的形式完全相同，因此仿照的讨论可知，对于每个，我们也分别可以得到一个含有个数的圈，使得相邻两数之差，要么是，要么是为了在每个圈上不取到相邻的数，至多只能取个数而当取出个数时，其中必有两数相邻，其差为或并且，任两个圈上的数显然不同：假若，则，于是，得，矛盾！若取出的元素个数，则上述个圈中，必有一个圈至少取出了个数，导致该圈上必有两数相邻，即有，使；另一方面，若取出的元素个数时，则有取法，即在每个圈上各取个数，使得任两数在圈上都不相邻，这时 ，因此，适合条件的的最小值是，（其中）、支足球队进行单循环赛，即每轮将支球队分成组，每组的两
15、队比赛一场，下一轮重新分组进行比赛，共赛轮，使得每队都与另外支球队各赛一场按任意可行的程序比赛了轮之后，总存在支球队，它们之间总共只赛了一场；求的最大可能值解：先构造一种比赛方案：将支球队顺次编号为，并按奇数与偶数分成两个子集：，再将每场比赛的队依照其和被除的余数情况而规定轮次，并且先在同奇偶的队之间各安排场，再将“挂单”的两个队安排一场比赛；即要求，第轮中每场比赛的队满足：即第一轮的：；第二轮的：；第三轮的：；第四轮的：；第五轮的：；第六轮的：；第七轮的：；第八轮的：；第九轮的：；在这九轮比赛中，共含有个（奇、奇）型搭配，个（偶、偶）型搭配，而，故知在这九轮中，一切（奇、奇）型搭配，（偶、偶）型搭配均已出现，即任一对（奇、奇）号球队都比赛过，任一对（偶、偶）号球队也都比赛过
