数学自主招生精品讲练组合构造法

《数学自主招生精品讲练组合构造法》由会员分享，可在线阅读，更多相关《数学自主招生精品讲练组合构造法（33页珍藏版）》请在装配图网上搜索。

1、【组合十讲】组合构造构造法是解证组合问题的重要方法与基本手段，使用它，常常可以将问题化难为易，化抽象为直观， 它需要较强的结构转化与知识综合能力常用的构造方法有：数论构造法；几何构造法；模型构造法；旋转、置换（群）构造法；图表构造法；图论构造法等、空间有个点，无三点共线，现将每两点之间用一种颜色的线连接，使得对于其中任意一点而言，由该点发出的任两条线皆不同色，问至少需要多少种不同颜色的线？证明你的结论若将个点改为个点，情况又将如何？、证明：可以将集合中的元素分成组，使得每组的元素和相等、给定两个正整数，其中，且；试求最小的正整数，使得在任意个满足条件：“对一切，”的整数中，都存在两个整数和，使

2、得可被整除、支足球队进行单循环赛，即每轮将支球队分成组，每组的两队比赛一场，下一轮重新分组进行比赛，共赛轮，使得每队都与另外支球队各赛一场按任意可行的程序比赛了轮之后，总存在支球队，它们之间总共只赛了一场；求的最大可能值、集合组由个五元集组成，其中任意两个集合的交都不是空集，令，中含有元素的集合数目为，记，求的最小值、在一个圆周上给定个点求最小的正整数，使得以这个点为顶点的任意个三角形中，必存在两个有公共边的三角形、将时钟盘面上标有数字的十二个点分别染上红、黄、蓝、绿四色，每色三个点，现以这些点为顶点构作个凸四边形，使其满足：（）每个四边形的四个顶点染有不同的颜色；（）对于其中任何三个四边形，

3、都存在某一色，染有该色的三个顶点所标数字互不相同求的最大值、设有个正整数及，满足：证明：可以从方格表中选出个方格，在选出的每格中各填写一个自然数，使得表中第行的填数和为，而第列的填数和为、一百个正数满足：，证明：中必有三数之和大于、平面上给定个点，无三点共线，现将每两点用一线段连接，并在每条线段上配置一个箭头，以给定点为顶点的三角形称为“环形”的，如果从任一顶点出发，沿箭头方向可环绕三角形周界行走一周，而返回原出发顶点；试求环形三角形个数的最大值与最小值、设的个七元子集满足：、，；、对于的任何元子集，都存在某个，使得求这组子集个数的最小值、给定个正整数，若其中至少有对数互质，证明：其中必存在四

4、个数，满足：、个正整数的和为，如果这个数既可分为和相等的个组，又可分为和相等的个组，求的最小值、设，求最小的正整数，使得的任一个元子集中，都存在两个不同的数和，满足：、数学奥林匹克集训队中共有名队员，其中每人在队中具有同样多的朋友，已知在一次考试中，所有人的得分各不相同；若某个队员在他的朋友圈中比多数人的得分都高，则称该队员为“高手”，问集训队中至多有几名“高手”？、（售票问题）个游客排队购买参观票，每张票价元，其中人各持有一张元币，另外人各持有一张元币，开初时售票机中无零钱可找，试确定，使得不发生售票困难的排队方法有几种？、对于正整数，证明：（单身汉引理）、一副纸牌共张，其中“方块”、“梅花

5、”、“红心”、“黑桃”每种花色的牌各张，标号依次是，其中相同花色、相邻标号的两张牌称为“同花顺牌”，并且与也算是顺牌（即可以当成使用）. 试确定，从这副牌中取出张牌，使每种标号的牌都出现，并且不含“同花顺牌”的取牌方法数、将周长为的圆周等分成段，从个分点中选取个点，使得其中任何两点间所夹的弧长都不等于和；问满足要求的点组的不同取法共有多少种？说明理由【组合十讲】组合构造构造法是解证组合问题的重要方法与基本手段，使用它，常常可以将问题化难为易，化抽象为直观， 它需要较强的结构转化与知识综合能力常用的构造方法有：数论构造法；几何构造法；模型构造法；旋转、置换（群）构造法；图表构造法；图论构造法等一

6、、数论构造法我们通过一些具体例子来说明这一方法的运用、空间有个点，无三点共线，现将每两点之间用一种颜色的线连接，使得对于其中任意一点而言，由该点发出的任两条线皆不同色，问至少需要多少种不同颜色的线？证明你的结论若将个点改为个点，情况又将如何？解：一般化，将改为，其中正整数，线段颜色数的最小值记为，易知， 今证明，一般情况下有设个点为，由于每点都要发出条线，诸线不同色，这样至少需要色；再证色不够，若总共只有色，则每点都要恰好属于各色线的端点一次现在设总共有条红色线，它们总共有个两两互异端点，于是，矛盾！因此，即下面说明最小值可以取到，采用数论构造法：用分别表示这色，而表示整数模的最小非负余数，即

7、，对于任意两点，将连线染第色，于是，对于任意一点，发自的任两条线皆不同色事实上，假若与同色，则有，即，得，因，故有，矛盾！故这种染色方案合于条件，因此，又对于个点，由于每点都要向其余点共发出条线，诸线不同色，这样至少需要色，只要证，色已足够构造，仍用分别表示这色，暂不考虑点，先对前个点两两间的连线依照上述个点的情形染色，我们注意到，对于其中任意两点的连线染色时，要求，也就是说，由点发出的条线的颜色代号，为模的完系中缺少了一个剩余现将点与前个点中任一点的连线染第色，由于当时与模不同余，故由点发出的条线互不同色，由其它点发出的条线也互不同色，故这种染色方案合于条件因此，从而于是对于个点或是个点，都

8、至少需要种颜色的线 下面的图形是和的情况由此可以看到，利用数论构造法给出的染色方案，优美和谐，浑然天成、证明：可以将集合中的元素分成组，使得每组的元素和相等证：我们可一般化为下述命题：若奇数，则集合可以分拆成个两两不交的元素之和相等的子集之并在集合中添加元素，并将诸元素依自小到大的顺序排列，然后按每个数一段分成三段：易知，对于两个具有个项的递增连续自然数数列及，它们按相反次序相加的每两项之和为常数：即；因此只要证，可以将第一段的个数适当排成，第二段的个数适当排成，使得恰好组成个连续自然数；（此时只要将所得的这个数与第三段的数反序相加，就得到相等的个和）若将第二段的每个数各减，问题又化为：若奇数

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

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

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

12、得 或，即，或，记，设，则，据得或 由知，而由得；因此由得 ，设，；， 今按的取值情况讨论：、若，则化为，或 且因及，由知均不为，即，改记，则，于是式可改写为对称形式：和引理：设，为正整数，从中取出一个元子集，使得中的任两数之差，既不为，也不为，则的最大值为采用数论构造法为了导出一般性方法，先分析一个特例:取，将按图中顺序排列于圆周上，使得相邻两数之差或者为，或者为，而不相邻的任两数之差，既不是，也不是；若将圆周上的个数按顺时针方向读出，就是：，圈中不相邻的数最多可取到个由于对一般的，我们不可能一个个地去构造，为此，重新研究这组数的结构，对于，不难发现，前三项分别可看作，由此想到，后续的项当是

13、，即是说，对于一般的，填写于圆周上的个数顺次为；另一方面，据对称性，我们也可顺次写出，它与上面填写于圆周上的个数实际上是重合的一组，只不过是按相反的方向从圆周上读出而已下面证明，排在圆周上的这组数符合要求.由，知，即，而是整数被除得的最小正余数，故上述个数，每个皆属于；这组数中，任两个皆不相等：假若，则，即，于是，而，矛盾！因此就是的一个排列；并且相邻两数之差满足：， 由于中的数，任两个不等，故相邻两数之差（大数减小数）属于集，而为模的一个完全剩余系，故其中与同余的只有，与同余的只有，因此由中两式得，相邻两数之差，要么是，要么是因此，要想在此圆周上所取的数不含相邻数，至多只能取个数而当取出个数

14、时，其中必有两数相邻，其差为或、当时，由得 ，即，式化为，或，这与的形式完全相同，因此仿照的讨论可知，对于每个，我们也分别可以得到一个含有个数的圈，使得相邻两数之差，要么是，要么是为了在每个圈上不取到相邻的数，至多只能取个数而当取出个数时，其中必有两数相邻，其差为或并且，任两个圈上的数显然不同：假若，则，于是，得，矛盾！若取出的元素个数，则上述个圈中，必有一个圈至少取出了个数，导致该圈上必有两数相邻，即有，使；另一方面，若取出的元素个数时，则有取法，即在每个圈上各取个数，使得任两数在圈上都不相邻，这时 ，因此，适合条件的的最小值是，（其中）、支足球队进行单循环赛，即每轮将支球队分成组，每组的两

15、队比赛一场，下一轮重新分组进行比赛，共赛轮，使得每队都与另外支球队各赛一场按任意可行的程序比赛了轮之后，总存在支球队，它们之间总共只赛了一场；求的最大可能值解：先构造一种比赛方案：将支球队顺次编号为，并按奇数与偶数分成两个子集：，再将每场比赛的队依照其和被除的余数情况而规定轮次，并且先在同奇偶的队之间各安排场，再将“挂单”的两个队安排一场比赛；即要求，第轮中每场比赛的队满足：即第一轮的：；第二轮的：；第三轮的：；第四轮的：；第五轮的：；第六轮的：；第七轮的：；第八轮的：；第九轮的：；在这九轮比赛中，共含有个（奇、奇）型搭配，个（偶、偶）型搭配，而，故知在这九轮中，一切（奇、奇）型搭配，（偶、偶

16、）型搭配均已出现，即任一对（奇、奇）号球队都比赛过，任一对（偶、偶）号球队也都比赛过于是，当赛完上述的九轮后，在这支球队中任取四个队，设其编号为，由于三数中必有两数同奇偶，设为，则他们已赛过，去掉，在三数中，又有两数同奇偶，他们也已赛过；因此若按这种分组方式进行了轮比赛之后，任何四个队之间都至少比赛过两场，于是适合条件的必应满足：此外，我们尚需补充说明，上述的轮比赛确实是一种符合要求安排中的前轮即，在以上轮赛完后，我们还可以继续安排后续轮比赛，从而保证全部轮比赛可以顺利进行下去为此，作两个同心圆盘，且各分成个相等的扇形小格，按反时针方向顺次将九个奇数以及九个偶数分别填入外盘及内盘的格子中，然后

17、转动内盘，使得在前九轮中已经比赛过的每一对（奇、偶）型搭配，分别位于对齐后的同一个小扇形中，于是得到图一在前九轮比赛中，外圈的任两队之间，内圈的任两队之间，以及任一个小扇形中的两队之间都已比赛过为叙述方便，令向量，这样图一便可改记为图二在前九轮比赛中，已赛过，已赛过，已赛过，而未赛过，今用下述方法安排后续轮比赛：将内盘固定，让外盘绕中心作反时针旋转，每次转过一格，对齐后，便在每一扇形内的两队之间各安排一场比赛，个扇形中的两队共安排出场比赛，这样便构成一轮比赛；八次旋转共得轮比赛，其中第次旋转后的场比赛是：，（约定），经过这样的轮比赛后，所有都已赛过，从而在全部轮比赛过后，这支球队的任两支球队都

18、赛过一场，且仅赛过一场，因此这轮比赛是符合要求的比赛，从而它的前九轮及后八轮比赛都合要求 接下来考虑比赛轮数的情况，我们若将上述轮比赛的顺序颠倒过来，即先安排后面的轮比赛，再安排前面的轮比赛，显然，这也是一种可行的安排经过这样的轮比赛后，支球队满足：未赛过，未赛过，未赛过，而皆已赛过 今从支球队中任取四个队，据对称性，不妨设，取自中的球队较多，则有以下三种情况：、若四个队全取自中，则这四个队两两之间皆未赛过；、若三个队来自，一个队来自，设为及，由于中至少有两个数异于，因此至少与中的两个队赛过，于是这四个队之间至少赛过两场；、若两个队来自，两个队来自，设为与，则至少和中的一个队赛过，也至少和中的

19、一个队赛过，于是这四个队之间至少赛过两场因此，按这种分组方式比赛轮之后，任何四个队之间，或者没有赛过，或者至少赛了两场，也就是不存在恰好只赛了一场的情况于是适合条件的应当满足： 下面证明，的最大值就是即需证，无论每一轮怎样分组，当比赛轮数时，其中必有四个队，他们两两之间恰好只比赛了一场设支球队按任一可行的方式分组，并赛完轮，则每一队恰好赛过场（与个队赛过），而与另外的个队未赛过（这里注意，）今用个点表示这支球队，如果两队赛过，则在点间连一条边，于是得阶图，的每个顶点的度数皆为（记为）在中取两个不相邻的顶点，因，故在中异于的个点中，必有一点，它与都不相邻于是中的点互不相邻，将中由其余个顶点组成的

20、集记为，由于的三点互不相邻，每点的度数为，故连接之间的边恰有条，（注意）、若集合中有一点，例如，向集合只发了一条边，则四点为所求（它们之间恰有一条边）；、若中的每个点，或者向不发边，或者向发出的边数，由于连接之间的总边数，则的个点之中，向发边的点不能多于个点，即至少有个点与中的点不相邻，设这点为；若这点中有某两点相邻，设为，则四点为所求；若中的任两点不相邻，则将其并入；令，这时中有个点、改记，其余点构成集合集中，任两点不相邻，每点的度数为，则连接之间的边数为，于是的个点之中必有一点向发出的边数，设此点为若，即是说，至少与中的两个点不相邻，且必与中的一点相邻，数与不相邻，而与相邻，则四点为所求；

21、若，即与中的每个点都不相邻，改记为，且将其并入；令，；中任两点不相邻，每一点度数为，故连接之间的边有条；由于中的个点，每点的度数也是，则的每点必须向发出条边，故中任两点也不相邻取，由于向发出条边，而，故中必有两点与不相邻，设为，且必有一点与相邻，设为，则四点为所求综以上讨论得，当比赛轮数时，按任何可行的方案分组，当赛完轮后，总有四个队，它们之间恰好只赛了一场因此，的最大可能值是二、旋转、置换（群）构造法、集合组由个五元集组成，其中任意两个集合的交都不是空集，令，中含有元素的集合数目为，记，求的最小值解：易得 这一事实利用“算两次”原理可立即得到：作一张的表，若，则在表中第行、列的交叉处填写一个

22、“*”号；*于是若按行计算，第行共有个“*”号，全表共有个“*”号，再按列计算，由于每列恰有个“*”号，全表的“*”号数是个，因此含有的个集合，共作成个“集合对”，由于任两个集合的交不是空集，故和式包含了所有的“集合对”，其中含有重复（因为有些集合对可能不止一个公共元，有些元素可能属于多个集合）据条件，集合组中的个集两两的交不空，它们构成个不重复的“集合对”，因此，即 ，据，则由，所以再证，反证法，若有，即对任何，皆有，这时将会导致所有；事实上，若有某个，即含有元素的集合不多于个，于是集合组中至少有个集不含，设不含的集合是，而含，记，由于，则，因此四个元素中，必有一个元素，例如，要属于中至少三

23、个集合，即属于中至少四个集合，这与矛盾！于是所有；但这又导致，矛盾！所以，即再说明，是可以取到的，为此，采用几何构造法，考虑如图的五角星，它的个结点以及各边中点，共得个点，分别标志为，今构造集合的个五元集如下：由五角星的外接圆上个点，五条边上的各个点，五个形如的“十字架”上的个点，分别作为一个集，这样共得个集，它们分别是：，因此，的最小值为（注意，也可将集合换成集合，同样可以确保任两个集的交不空）、在一个圆周上给定十二个红点；求的最小值，使得存在以红点为顶点的个三角形，满足：以红点为端点的每条弦，都是其中某个三角形的一条边解：设红点集为：，过点的弦有条，而任一个含顶点的三角形，恰含两条过点的弦

24、，故这条过点的弦，至少要分布于个含顶点的三角形中；同理知，过点的弦，也各要分布于个含顶点的三角形中，这样就需要个三角形，而每个三角形有三个顶点，故都被重复计算了三次，因此至少需要个三角形再说明，下界可以被取到不失一般性，考虑周长为的圆周，其十二等分点为红点，以红点为端点的弦共有条若某弦所对的劣弧长为，就称该弦的刻度为；于是红端点的弦只有种刻度，其中，刻度为的弦各条，刻度为的弦共条； 如果刻度为（）的弦构成三角形的三条边，则必满足以下两条件之一：或者；或者；于是红点三角形边长的刻度组只有如下种可能：；下面是刻度组的一种搭配：取型各六个，型四个；这时恰好得到条弦，且其中含刻度为的弦各条，刻度为的弦

25、共条；今构造如下：先作型的三角形各六个，型的三角形三个，再用三个型的三角形来补充型六个：其顶点标号为：；型六个：其顶点标号为：；型六个：其顶点标号为：；型三个：其顶点标号为：；型三个：其顶点标号为：（每种情况下的其余三角形都可由其中一个三角形绕圆心适当旋转而得）这样共得到个三角形，且满足本题条件，因此，的最小值为、在一个圆周上给定个点求最小的正整数，使得以这个点为顶点的任意个三角形中，必存在两个有公共边的三角形解：先考虑两两无公共边的三角形个数的最大值个点，每两点连一条弦，共得条弦，若每条弦只属于一个三角形，则这些弦至多能构成两两无公共边的三角形个数个，但若有个这样的三角形，共得个顶点，则八边

26、形必有一顶点，至少属于个三角形，设为，共顶点的个三角形，的对边都是之中的两点连线，其中必有一点，设为，出现了两次，那么相应的两个三角形将有一条公共边，这不可能；故另一方面，当时，我们确实可以作出这样的个三角形，使得其中任两个三角形都无公共边；注意这样的个三角形，共产生个顶点，若使每点所参与的三角形个数都小于，那么每点恰好属于个三角形，也就是说，每个点，恰与其余七点中的点有边相连，而与另一点不连边；考虑每点度数皆为的八阶图：为简明起见，取圆周的八等分点作为图的八个顶点，作阶完全图，然后去掉其中条直径，这样共得条边，且每点均属于条边；在由这些边所构成的三角形中，选取八个等腰三角形：以及它们两两无公

27、共边；（每一组的四个三角形，皆可由其中一个三角形绕圆心适当旋转而得到）因此，从而所求的最小值、将时钟盘面上标有数字的十二个点分别染上红、黄、蓝、绿四色，每色三个点，现以这些点为顶点构作个凸四边形，使其满足：（）每个四边形的四个顶点染有不同的颜色；（）对于其中任何三个四边形，都存在某一色，染有该色的三个顶点所标数字互不相同求的最大值解：为叙述方便，改用分别表示这四种颜色，而同色的三点，则分别用；以及来表示今考虑其中一色，例如色；若在这个四边形中，色点出现的次数分别为，则，设；如果，则；再考虑这个四边形（其色顶点要么是，要么是），它们中色点出现的次数分别为，则，据对称性，可设，则，即；继续考虑这个

28、四边形（其色顶点要么是，要么是；色顶点要么是，要么是），它们中色点出现的次数分别为，则，据对称性，可设，则，即；最后考虑这个四边形，记为（其色顶点要么是，要么是；色顶点要么是，要么是；色顶点要么是，要么是），由于色点只有三个，故其中必有两个四边形，其色点相同，设的色点都为；那么，三个四边形中，无论哪种颜色的顶点，所标数字皆有重复，这与条件相矛盾！因此，再说明，最大值可以取到；采用构造法，我们只要作出这样的九个四边形即可作三个“同心圆环图”，给出标号，并适当旋转相应的圆，标号对齐后，图中的每根线（半径）上的四个点分别表示一个四边形的四个顶点颜色及其标号，九条半径共给出九个四边形，且都满足条件（）

29、；再说明，它们也满足条件（）：从中任取三条半径（三个四边形）；如果三条半径（三个四边形）来自同一个图，则除了色之外，其余每色的顶点，三数全有；如果三条半径（三个四边形）分别来自三个图，则色的顶点，三数全有；如果三条半径（三个四边形）分别来自两个图：将三个图分别称为图、图、图，每图的三条半径分别称为“向上半径”、“向左半径”、“向右半径”；且分别记为来自两个图的三条半径，如果“向上”、“向左”、“向右”三种半径都有，那么相应的三个四边形，色的顶点，三数全有；如果三条半径，只涉及两个图，两个方位，将图分别简记为，则按三个图的搭配情况，可得下表：因此本题所求的的最大值为三、几何构造法、设有个正整数及

30、，满足：证明：可以从方格表中选出个方格，在选出的每格中各填写一个自然数，使得表中第行的填数和为，而第列的填数和为证：采用几何构造法，设，则为正整数，在坐标系数第一象限作一个边长为的正方形，在上顺次截出长度为的线段，得到个分点，其中，；（称为型线段）在上顺次截出长度为的线段，得到个分点，其中，；又在上顺次截出长度为的段，得到个分点，其中，；（称为型线段）在上顺次截出长度为的段，得到个分点，其中，；过诸点，分别作的垂线，再过点，分别作的垂线过第条型线段两端点的垂线所夹矩形长条称为第个型条，过第条型线段两端点的垂线所夹矩形长条称为第个型条，线段上的分点各有个（其中有些分点可能是重合），它们将线段，各

31、分成段，每一段的长度都是整数（重合的分点构成的线段长度为）；两组垂线构成了许多正方形，我们主要关注对角线在上且未被其它正方形所覆盖的正方形，称为单纯正方形（有些正方形可能蜕化成一个点），这种正方形共有个，它们的边长皆为非负整数；现在我们这样在方格表上填数：如果一个单纯正方形夹在第个型条与第个型条中，则将正方形的边长填入方格表第行、列的交叉处；由于这些单纯正方形的对角线覆盖了正方形的对角线，且互不重叠，所以第个型条中的单纯正方形的边长之和恰等于第个型条的宽度，第个型条中的单纯正方形的边长之和恰等于第个型条的宽度，即有，表中第行的填数和为，而第列的填数和为因此结论得证下面的例子是的情形、一百个正数

32、满足：，证明：中必有三数之和大于证：据对称性，不妨设，只要证，；反证法，假若，作三个边长为的正方形，拼成一个矩形，再把边长为的小正方形一个接一个依次放入矩形中，恰好铺成由到的一长条，记为，据反证法假设知，小正方形都在大正方形内，长条含于正方形内的这一部分，被的矩形所覆盖，而落入大正方形中的部分当被的矩形所覆盖，落入大正方形中的部分当被的矩形所覆盖，因此全体小正方形的面积和应不大于三个矩形的面积和；另一方面，由于，我们可以在正方形中剪出的三个矩形；因此可以将矩形分别放置于大正方形中的处，于是，全体小正方形的面积和不大于正方形的面积，即，此为矛盾！因此假设不真，从而本题结论成立、平面上给定个点，无

33、三点共线，现将每两点用一线段连接，并在每条线段上配置一个箭头，以给定点为顶点的三角形称为“环形”的，如果从任一顶点出发，沿箭头方向可环绕三角形周界行走一周，而返回原出发顶点；试求环形三角形个数的最大值与最小值解：配置箭头后的三角形只有“环形”与“非环形”两种形状，因此，环形三角形个数非环形三角形个数全体三角形个数先求，我们注意到，一个三角形是“非环形”的，当且仅当其三个顶点中，恰有一个顶点发出两个箭头，也有一个顶点收到两个箭头我们将“发自同一顶点的一对箭头”或者“指向同一顶点的一对箭头”统称为一个“同型对”于是，一个“非环形”三角形恰有两个“同型对”对于一个确定的顶点而言，关联的每一个“同型对

34、”，恰好产生一个“非环形”三角形设是任一个给定的点，以为端点的线段共有条，设点发出个箭头，收到个箭头，自发出的个箭头，组成个同型对，收到的个箭头，组成个同型对，因此关联的同型对有个为求的最小值，即需求的最大值当为奇数，则在时，有最大值；此时；当为偶数，则在或时，有最大值；此时让跑遍全部个点，得到个“非环形”三角形，由于每个“非环形”三角形恰有两个同型对，故均被计算了两遍，因此，“非环形”三角形共有个，当每个点所关联的“非环形”三角形个数都取得最小值时，全体“非环形”三角形个数也取得最小值，所以，则此值可以取到，构造法，考虑圆周的等分点，对于不经过圆心的每条弦配置箭头时，可使绕圆周成反时针方向（

35、即，顺着箭头方向沿每条弦行走时，圆心总在左侧），而对于经过圆心的弦（直径），箭头方向可任意配置，这样，每个点的出入箭头数至多相差一个再求环形三角形个数的最小值，（注意上面的方法不能用于此情形，因为上面的公式是对于每个点都使关联的“非环形”三角形个数取得最小值时求得的）我们指出，环形三角形个数的最小值为构造法，将个点分别标号为，配置箭头按小数指向大数进行、设的个七元子集满足：、，；、对于的任何元子集，都存在某个，使得求这组子集个数的最小值解：采用“元素跟踪”法，因中有个元素，其中含的元子集，共计（不重不漏）.此外，若元素在个子集中出现，每个有个元素，其中含的元子集有个，个这种子集共收集到这种元子

36、集（在不同的元子集中，有些元子集可能会出现重复，这是因条件的缘故）（不漏但可重）.于是.因为整数，则.再从元素个数考虑，个元子集共得个元素（它们来自，且有重复）.另一方面，中的每个元素在诸中至少出场次，而这种有个,故个集中的元素个数和至少是个（可重，但为“至少重”）所以，则.以下说明确为所求的最小值。需构造集的个元子集,使其覆盖的全体元子集（以下称为“三角形”）.(注意，本题的构造过程是一项比前一阶段论证过程更为精细的工作，仍采用几何构造法，以便于检验).先计算一下中的“三角形”个数，为个.再分析的数字结构，其中有个偶数，个奇数.进而对中的“三角形”按“顶点”分类.(偶 偶 偶)型三角形，共个

37、；(偶 偶 奇)型三角形，共个；(奇 奇 偶)型三角形，共个；(奇 奇 奇)型三角形，共个为解决第一类(偶 偶 偶)型三角形，只须取即可.而为满足，每个后续的至多只能含有个偶数，并且必需覆盖所有后三类三角形.因此，这个集，每个集必须取三个偶数，四个奇数.先考虑偶数搭配.顺次将个偶数填写于圆周的个等分点上，易知圆内接正边形只有三种长度的弦.将其搭配成一个三角形，然后顺时针旋转次，得到个三角形：.这组三角形有特征：任二个三角形恰有一个公共顶点，而无公共边；任一个偶点恰属于三个三角形.每个三角形有三条边，共得条偶顶线段.任二条皆不相同.它恰好穷尽了所有个二元的偶数子集.由于只有个偶顶三角形，为组成个

38、元子集，每个偶顶三角形必须使用二次，称为一对“重置偶三角”，对于“重置偶三角”，需要将个奇数分成互补的两组，不能有公共元素,又因任两个“相异偶三角”恰有一个公共元，因此，与之搭配的四元奇数集，至少允许有两个相同元素.据此，我们来对个奇数构成的集，设计种互补分拆，使之满足条件.将个奇数顺次填写于圆周的八等分点上，然后作种形状的元分拆（四边形分拆）：十字分拆（正方形分拆）：半圆分拆（薄梯形分拆）：，矩形分拆：，梯形分拆（厚梯形分拆）：，易知，分拆有特征：同一分拆中的两组奇数，无公共元素（互补）；不同分拆中的任二组奇数（任二个四边形）恰有二个公共元（一条线段）；任一条线段（一个奇数对）恰好出现三次.

39、每个完全四边形有条边，个四边形共得条边，而每条边重复三次，故得条不同的边.另一方面，八个奇数的集共有个二元奇子集.因此，这些四元奇数组穷尽了所有二元奇数子集.又知，每个四元组产生个三元子集，且任二个四元组没有共同的三元子集（因至多一条公共边）.故个四元组共得个三元奇子集.它们恰穷尽了所有个三元奇子集.下面，我们来完成后续个元子集的搭配.首先,只要个四元集一齐用上,便完成了对所有的奇顶三角形的覆盖；只要每一对“重置三角形”分别搭配一对互补的元分拆，便完成了对所有“偶偶奇”型三角形的覆盖.在满足前述情况的前提下，我们作出搭配，使之满足对于全部“奇奇偶”型三角形（共个）的覆盖.据前面的讨论知，每个偶

40、顶在七个三角形中出现三次，而每条“奇顶边”在个四边形中也出现三次.由对称性，只要考虑元子集对于偶数和奇数对所形成的“奇奇偶”型三角形的覆盖.采用“先入为主”的办法.先从和入手.含的偶顶三角形有三个：和含的四边形也有三个：和先让它们任意对搭配，而让其互补四边形与相应的重置偶顶三角形搭配，这样得到六个元组：； （*）；不含的偶顶三角形有个，为，和，而含的四边形（四元组）也剩了个，为，和，今让一对一搭配，而让其互补四边形与相应的重置偶顶三角形搭配，于是得到个元组：，；，；，； （），；由（*）（）共得到个元子集.由于每一条奇顶线段（这种线段共条）在三个四边形中出现，而与这三个四边形搭配的三个偶顶三角

41、形含有全部偶点（例如，与所在四边形搭配的偶顶三角形为，这三个三角形含有全部个偶点，因此型三角形全被覆盖，其余可类似检查，全部检验共次）.因此，个奇奇偶型三角形全被覆盖.于是，个元集满足条件，的最小值为.四、图论、图形、图表构造法、给定个正整数，若其中至少有对数互质，证明：其中必存在四个数，满足：证：采用图形构造法：用点分别代表这个正整数，若，则令相应点相邻，于是得阶简单图，设点的度数为，据条件，图至少有条边，不妨设，图恰有条边，否则我们就去掉其中一些边，并不影响问题的性质；与点相邻的点有个，它们构成个“点对”，据条件，；若记 ，则，由柯西不等式，因此，故在中必有两个点，其所邻接的点中，具有相同

42、的一个“点对”，设为，即为四边形，从而，、个正整数的和为，如果这个数既可分为和相等的个组，又可分为和相等的个组，求的最小值解：设分成的个组为，每组中的各数和皆为，称这种组为类组；而分成的个组为，每组中的各数和皆为，称这种组为类组显然，每个项恰好属于一个类组和一个类组，即同类组之间没有公共项，如果两个组中有两个公共项，则可以将这两个数合并为一个项，这样可使值减少，故不妨设，每对至多有一个公共项构造图论模型：今用点分别表示，而点表示组，如果组有公共项，则在相应的点之间连一条边，于是得二部图，它恰有条边和个顶点下面证明是连通图如果图的最大连通分支为，其顶点数少于，设在分支中，有个类顶点和个类顶点，其

43、中，则在相应的类组和类组中，类组中的每个数都要在某个类组中出现；而类组中的每个数也都要在某个类组中出现，（否则将有边与分支外的顶点连接，发生矛盾），因此个类组中各数的和应等于个类组中各数的和，即有，由此得，所以，矛盾！因此是连通图于是图至少有条边，即；另一方面，我们可实际构造一个具有项的数列，满足本题条件例如取，（该数组有个取值为的项；个取值为的项；另将其余七个拆成七对，其中四对，两对，一对，又得到个项），于是，每个类组可由一个，一个，或者由一个，添加一对和为的项组成；这样共得个类组，每组各数的和皆为；为了获得和为的个类组，可使各成一组，其余的数可以拼成八个类组：的组四个，的组两个，的组一个，

44、的组一个故的最小值为 、设，求最小的正整数，使得的任一个元子集中，都存在两个不同的数和，满足：解：设中不同的数和，满足：，记，有，其中为正整数，且，则，由，得，又由得，所以从而 ，则，因为互异，则，又由互异，且由，则，即，于是 ，可取不妨设，讨论不同情况、若，则，由，则，可取，所以，；、当，则，由，则，可取，；、当，则或，前者可取，后者可取，；、当，则，；、当，则，故；、当，则，因，去掉这组，；、当，则，去掉后两组，则以上我们共得到个数对，其中每个数对都满足：为了找出满足条件的最小的，先求最大的，使得存在的元子集，其中任一对数都不满足条件为此，构作阶图，以中的数为顶点，如果两数属于以上数对，则

45、令相邻，于是图恰有条边（图中的孤立点未标出）从中删去一些点，使得图中的边一起被删去，则至少要删去个点，例如将点集中的点删去，这时，图还剩下个点，由这个数作成集合，则中不含以上任一个数对即中任一个数对都不满足条件因此，故所求的最小数以下证，满足条件首先从图中取条两两无公共顶点的边（个数对）：，（其中每条边恰有一个点在集中），这条边的顶点共有个，相应的个数构成的元子集；中其余的数共有个，它们构成子集；今从中任取一个元子集，则至多有个数取自中，也就是至少有个数取自，其中必有两个数取自上述个数对中的同一对，设为，则因此，满足条件的最小的值为、数学奥林匹克集训队中共有名队员，其中每人在队中具有同样多的朋

46、友，已知在一次考试中，所有人的得分各不相同；若某个队员在他的朋友圈中比多数人的得分都高，则称该队员为“高手”，问集训队中至多有几名“高手”？解：设每名队员有个朋友，而这次考试总共产生了个“高手”，队中成绩最好的一名队员，在他的个“朋友对”中成绩也是最好的，当然是“高手”；而其余的每个“高手”，都至少在其个朋友对中，成绩占优所以“高手”们至少一共在个朋友对成绩占优由于任一个“朋友对”至多为“高手”作一次贡献，故不会被重复计算，因此上述数目不会超过集训队中“朋友对”的总数，即（这相当于一个阶图，每点的度数为，其边数为）所以，故得 另一方面，集训队中比最差的“高手”的成绩还差的队员人数不多于个（其中

47、是“高手”总数），由于最差的“高手”也至少胜了人，所以，即 代入式，并注意的右边是的增函数，则得到，即 ， 也就是 ，（注意），则满足及条件的正整数的最大值是，即“高手”数不超过个；另一方面，我们可说明，个“高手”的情况是可能的，采用构造法：用表示队员的排名（成绩好的排名在前），当时，由得，即每人恰有个朋友；今列出一张的表，并这样定义朋友关系：若某对学生为朋友，当且仅当满足以下三情形之一：、两人同在第一行；、两人在同一列，但其中一人位于最下面一行；、两人分别在相邻的两行，但是不同列；这样，每人恰有个朋友，并且前名都是“高手”五、模型构造法、（售票问题）个游客排队购买参观票，每张票价元，其中人各

48、持有一张元币，另外人各持有一张元币，开初时售票机中无零钱可找，试确定，使得不发生售票困难的排队方法有几种？解：将换为一般的正整数；如果某人持有一张元票，则赋值“”，（即，售票机可以收到一张元票）；若某人持有一张元票，则赋值“”，（即，售票机需要付出一张元票用来找另）；这样，个人的一个排队状态便对应于个数（其中含有个和个“”）的一个排列：，记，则，一个排队方式不发生售票困难，当且仅当对每个，皆有在直角坐标系中标出点，依次连接得到一条折线，称长度为，斜率为的线段为，长度为，斜率为的线段为，因此，折线由条和条按适当排列顺序首尾连接而组成，因条和条的排列方式有种（从个位置中任取个位置放置，其余位置为的

49、放置方法有种），所以这种折线一共有条；每个发生售票困难的排法所对应的折线都与直线接触；为了计算与直线接触的折线条数，对每条这种折线，从第一个接触点开始，把以后的折线部分以直线为对称轴翻转，这样就得到一条由原点到点的折线，所有这种折线都由条和条按适当排列顺序首尾连接而组成，一共有条，因此，不发生售票困难的排队方法有种、对于正整数，证明：（单身汉引理）证：采用组合模型法，设想某社区共有户人家，其中有户夫妻家庭和一户单身汉家庭，共计人，今从中任选人参加一项活动，则共有种选择方案另一方面，该事件也可作如下分类：对任一数，户夫妻家庭中恰有户家庭各派出了一人，其余户夫妻家庭皆为两人同去，显然，当为奇数时，

50、单身汉必须参加；而当为偶数时，则单身汉肯定不能参加从对夫妻中选取对，有种方法，再从选出的对中各派出一人，有种派法，剩下人中，共含有对夫妻，他们来自剩下的个家庭，选法种数为，因此按这种分类，得选法种数，所以，、一副纸牌共张，其中“方块”、“梅花”、“红心”、“黑桃”每种花色的牌各张，标号依次是，其中相同花色、相邻标号的两张牌称为“同花顺牌”，并且与也算是顺牌（即可以当成使用）. 试确定，从这副牌中取出张牌，使每种标号的牌都出现，并且不含“同花顺牌”的取牌方法数解：先一般化为下述问题：设 从 ，这四个数列中选取个项，且满足：、每个下标都出现；、下标相邻的任两项不在同一个数列中（下标与视为相邻），其

51、选取方法数记为，今确定的表达式:将一个圆盘分成个扇形格，顺次编号为，并将数列各染一种颜色，对于任一个选项方案，如果下标为的项取自某颜色 数列，则将第号扇形格染上该颜色.于是就成为将圆盘的个扇形格染四色，使相邻格不同色的染色方法数，易知， , 将写作 因此 ；相加得，于是 .因此 . 这就是所求的取牌方法数.、将周长为的圆周等分成段，从个分点中选取个点，使得其中任何两点间所夹的弧长都不等于和；问满足要求的点组的不同取法共有多少种？说明理由解：将各分点顺次编号为，再按点间所夹弧长为或的情形，列出一张数表：表中同行相邻两点间所夹弧长为（首尾两数属于相邻情况），同一列的三点之中任两点间所夹弧长为今要所取的数满足要求，必须每列恰取一数，且相邻两列所取的数不同行（第一列与第八列视为相邻）一般化，考虑的数表 ，从中选取个数，使每列恰取一数，且相邻两列所取的数不同行（第一列与第列视为相邻）不同的取法种数记为，将第一、二、三行的数分别染红、黄、蓝三色；作一个圆盘，并将其分成个扇形小格，顺时针编号为；今作如下映射，若表中第列所选出的为某色的数，则将圆盘第号格染上该颜色，易知这种对应是一一的，于是问题转化为，求用三色分别染圆盘的个扇形格，使邻格不同色的方法数易知 ，当，即 ，令，有， ，相加得，所以，当 ，便得本题答案为