全国高中数学联赛试题分类汇编15 组合与构造 Word版含答案.doc

1、1981年2019年全国高中数学联赛试题分类汇编组合与构造部分2019A四、（本题满分 50 分）设V 是空间中 2019 个点构成的集合，其中任意四点不共面某些点之间连有线段，记 E 为这些线段构成的集合试求最小的正整数n，满足条件：若 E 至少有n个元素，则 E 一定含有 908 个二元子集，其中每个二元子集中的两条线段有公共端点，且任意两个二元子集的交为空集解析：为了叙述方便，称一个图中的两条相邻的边构成一个“角”先证明一个引理：设是一个简单图，且是连通的，则含有个两两无公共边的角（这里表示实数的整数部分）引理的证明：对的元素个数归纳证明当时，结论显然成立下面假设，并且结论在较小时均成立

2、只需证明，在中可以选取两条边构成一个角，在中删去这两条边后，剩下的图含有一个连通分支包含条边对这个连通分支应用归纳假设即得结论成立考虑中的最长路，其中是互不相同的顶点因为连通，故.情形1：,由于是最长路，的邻点均在中，设，其中则是一个角，在中删去这两条边若处还有第三条边，则剩下的图是连通的；若处仅有被删去的两条边，则成为孤立点，其余顶点仍互相连通总之在剩下的图中有一个连通分支含有条边情形 2：， 则 是一个角，在中删去这两条边后，都成为孤立点，其余的点互相连通，因此有一个连通分支含有条边情形 3：，且与中某个点相邻则是一个角，在中删去这两条边后，成为孤立点，其余点互相连通，因此有一个连通分支含

3、有 条边情形 4：，且与某个相邻由于是最长路，故的邻点均在之中因是一个角，在中删去这两条边，则是孤立点若处仅有边，则删去所述边后也是孤立点，而其余点互相连通若处还有其他边，则删去所述边后，除外其余点互相连通总之，剩下的图中有一个连通分支含有.引理获证20 分回到原题，题中的和可看作一个图首先证明设在中，首先两两连边，再删去其中条边（例如），共连了条边，则这个点构成的图是连通图再将剩余的个点配成对，每对两点之间连一条边，则图中一共连了条线段由上述构造可见，G 中的任何一个角必须使用相连的边，因此至多有个两两无公共边的角故满足要求的不小于30 分另一方面，若，可任意删去若干条边，只考虑的情形设有个

4、连通分支，分别有个点，及条边下面证明中至多有个奇数反证法，假设中有至少个奇数，由于是奇数， 故中至少有 981 个奇数，故不妨设 都是奇数，显然令，则有（），故，利用组合数的凸性，即对，有。可知当由个以及一个构成时，取得最大值于是，这与矛盾从而中至多有 979 个奇数40 分对每个连通分支应用引理，可知中含有个两两无公共边的角，其中。综上，所求最小的是50 分2019B四、（本题满分50分）将一个凸边形的每条边任意染为红、黄、蓝三种颜色之一，每种颜色的边各条证明：可作这个凸边形的条在内部互不相交的对角线将其剖分成个三角形，并将所作的每条对角线也染为红、黄、蓝三种颜色之一，使得每个三角形的三条边

5、或者颜色全部相同，或者颜色互不相同证明：我们对归纳证明加强的命题：如果将凸边形的边染为三种颜色，并且三种颜色的边均至少有一条，那么可作满足要求的三角形剖分10 分 当时，若三种颜色的边数为,由对称性，只需考虑如下两种情形， 分别可作图中所示的三角形剖分若三种颜色的边数为,由对称性，只需考虑如下三种情形，分别可 作图中所示的三角形剖分20 分 假设结论对（）成立，考虑的情形，将凸边形记为 情形 1：有两种颜色的边各只有一条不妨设色边各只有一条由于，故存在连续两条边均为色，不妨设是作对角线，并将 染为 色，则三角形的三边全部同色此时凸边形的三种颜色的边均至少有一条，由归纳假设，可对其作符合要求的三

6、角形剖分30分情形 2：某种颜色的边只有一条，其余颜色的边均至少两条不妨设色边只有一条，于是可以选择两条相邻边均不是色，不妨设均不是色，作对角线，则有唯一的染色方式，使得三角形的三边全部同色或互不同色此时凸边形的三种颜色的边均至少有一条，由归纳假设，可对其作符合要求的三角形剖分 40 分情形 3：每种颜色的边均至少两条作对角线，则 有唯一的染色方式，使得三角形的三边全部同色或互不同色此时凸边形 的三种颜色的边均至少有一条，由归纳假设，可对其作符合要求的三角形剖分 综合以上种情形，可知的情形下结论也成立 由数学归纳法，结论获证 50 分2017A三、（本题满分50分）将方格纸中每个小方格染三种颜

7、色之一，使得每种颜色的小方格的个数相等。若相邻两个小方格的颜色不同，则称他们的公共边为“分割边”。试求分割边条数的最小值。解析：记分割边的条数为.首先，将方格纸按如图所示分成三个区域，分别染成三种颜色，粗线上均为分割边，此时共有56条分割边，即。下面证明.将方格纸的行从上至下依次记为,列从左至右依次记为,行中方格出现的颜色数记为，列中方格出现的颜色数记为，三种颜色分别记为，对于一种颜色，设是表示含有色方格的函数与列数之和.记，同理定义，则由于染色的方格有个，设含有色方格的行有个，列有个，则色方格一定在这行和列的交叉方格中，因此.从而即.由于在行中有种颜色的方格，因此至少有条分割边，同理在行中有

8、种颜色的方格，因此至少有条分割边，于是，下面分两种情形讨论.当有一行或有一列全部方格同色时，不妨设有一行全为色，从而方格纸的33列中均含有的方格，由于的方格有363个，故至少有行中含有色方格。于是。由得没有一行或没有一列全部方格同色时，则对任意，均有，从而由知，综上可知，分割边条数的最小值为。2017A四、（本题满分50分）。设均是大于的整数，是个不超过的互不相同的正整数，且互素。证明：对任意实数，均存在一个（），使得，这里表示实数到它最近的整数的距离。证明：首先证明两个引理：引理1：存在整数，满足，并且，.由于互素，即，有裴蜀定理，存在整数，满足。下面证明，通过调整，存在一组满足，且，记，。

9、如果，那么存在，于是，又是大于1的整数，故由可知，存在，令，（，），则， 并且，所以，如果，则存在，因此有一个.令，（，），那么成立，并且，与上面类似可以证明到：，即说明与均是非负整数，故通过有限次上述的调整，可以得到一组使得成立，并且结论获证。引理2：对任意的实数，均有；对任意整数和实数，有；由于对任意整数和实数，均有，于是不妨设，此时，若，不妨设，则，从而若，不妨设同号，则当时，有，此时；当时，注意到总有，故；故得证；又，由知，是成立的。接下来回到原题，由结论存在整数，满足，并且，.于是，由引理2得，因此，若，则由知，若，则在中存在两个相邻的正整数。不妨设相邻，则，故与中有一个不小于。综上

10、，总存在存在一个（），使得2016A三、（本题满分50分）给定空间个点，其中任意四点不在一个平面上。将某些点之间用线段相连，若得到的图形中没有三角形也没有空间四边形，试确定所连线段数目的最大值。解析：以这10个点为顶点，所连线段为边，得到一个10阶简单图G，下证明G的变数不超过15.设G的顶点为，一共有条边，用表示顶点的度。若对都成立，则。假设存在满足，不妨设，且与均相邻.于是之间没有边，否则就成三角形，所以与之间恰有条边.对每个（），至多与中的一个顶点相邻（否则设与，（）相邻，则，就对应了一个空间四边形的四个顶点，这与题意矛盾），从而与之间的边数至多条。在这个顶点之间，由于没有三角形，由托兰

11、定理，至多条边，因此G的边数例如如图所示的就有条边，且满足要求。综上所述，所连线段数目的最大值为。2014B四、（本题满分50分）设是一个边长为的等边三角形，在的内部和边界上任取 个点. (1) 证明：一定存在两个点，它们之间的距离小于或等于；（20分） (2) 证明：一定存在两个点，它们之间的距离严格小于；（30分）证明：(1)如左下图1，我们将分成个边长为的小等边三角形；对于中间的图2中六个灰色的小三角形，我们将它们剖分成三个全等的三角形；这样，我们就可以看出就可以被右图3的个正六边形所覆盖。 图1 图2 图3不难看出，这里的个正六边形的直径为，它们可以被看做只“抽屉”，对于三角形内部和边

12、界上任取个点，根据抽屉原理，至少有一个正六边形包含两个点。而在这个正六边形中，任意两点间的距离不超过，这样便证明了我们所要的结论。（要注意，我们的抽屉的构造并不是唯一的，我们还可以用下图4所示的个直径为的圆覆盖，也可以得到同样的结论） 图4 图5(2)这部分要求证明的是严格不等号。我们要证明在个点中存在两个点，他们间的距离严格小于，注意到直径为的正六边形中，间距恰好为的两个点一定是距离最远的一对点，另一方面，上面所构造的正六边形抽屉在边和顶点处是由重复的，我们通过指定一条边或者顶点属于那一个特定的正六边形来改造我们的“抽屉”，使得每一个抽屉不包含正六边形中距离为的顶点对，当然，在目前的情况我们

13、只需关心怎么改造顶点即可。我们在每一个正六边形抽屉上去掉一些顶点，使得每一个抽屉不在包含正六边形中距离为的顶点对，如图5就是一个办法，图中空心的点表示正六边形中去掉该点，不难看出，这样的改造还是覆盖了原来得三角形，且每一个抽屉不在包含正六边形中距离为的顶点对，根据抽屉原理，我们就证明了：任取个点，一定存在两个点，它们之间的距离严格小于。（这样的抽屉构造也是不唯一的）2013B四、（本题满分50分）用若干单位小正方形和由三个单位小方格组成的 形“砖”铺满一个的方格棋盘的所有不同可能铺法的数目是下面的图是时的两种不同的铺法：求；求的个位数证明：由题意显然，当时，我们从左向右地铺的方格棋盘，无论哪一

14、种铺法，至多铺到，我们一定会完成一个（）的矩形。这样我们计算时，就可以去寻找与的关系，又由下图我们得到由，得，,依次下去可得由，可知，一定是奇数。我们由计算，对每一个，我们有：(,),可知，的个位数的周期是。而，又等于的奇数也一定等于，所以的个位数为。2012A三、（本题满分50分）设是平面上个点，它们两两间的距离的最小值为，求证：证明：证法一:不妨设先证明:对任意正整数,都有显然, 对均成立,只有时右边取等号10分所以,只要证明当时,有即可.以为圆心,为半径画个圆,它们两两相离或外切;以圆心，为半径画圆，这个圆覆盖上述个圆20分所以30分由易知40分所以对时也成立.综上,对任意正整数都有.因

15、而50分证法二: 不妨设以为圆心,为半径画个圆,它们两两相离或外切; 10分设是是圆上任意一点,由于20分因而,以为圆心, 为半径的圆覆盖上述个圆30分故40分所以50分2011A三、（本题满分50分）设是给定的正实数，对任意正实数，满足的三元数组的个数记为证明：证明：对给定的，满足，且的三元数组的个数记为注意到，若固定，则显然至多有一个使得成立因，即有种选法，故同样地，若固定，则至多有一个使得成立因，即有种选法，故从而 因此，当为偶数时，设，则有 当为奇数时，设，则有 综上所述， 2011A四、（本题满分50分）设A是一个的方格表，在每一个小方格内各填一个正整数称A中的一个方格表为“好矩形”

16、，若它的所有数的和为10的倍数称A中的一个的小方格为“坏格”，若它不包含于任何一个“好矩形”求A中“坏格”个数的最大值解析：首先证明A中“坏格”不多于25个用反证法假设结论不成立，则方格表中至多有1个小方格不是“坏格”由表格的对称性，不妨假设此时第1行都是“坏格”设方格表第列从上到下填的数依次为记，这里 我们证明：三组数；及都是模10的完全剩余系事实上，假如存在，使，则，即第1行的第至第列组成一个“好矩形”，与第1行都是“坏格”矛盾 又假如存在，使，则，即第2行至第3行、第列至第列组成一个“好矩形”，从而至少有2个小方格不是“坏格”，矛盾类似地，也不存在，使因此上述断言得证故，所以，矛盾！故假

17、设不成立，即“坏格”不可能多于25个 另一方面，构造如下一个的方格表，可验证每个不填10的小方格都是“坏格”，此时有25个“坏格”11121111101111111111111011112综上所述，“坏格”个数的最大值是25 2011B四、（本题满分50分）给定个不同实数，其所有全排列组成的集合为.对于，若恰有两个不同的整数使得成立，则称该排列为“好排列”.求中“好排列”的个数.解析：首先定义：对于中的一个排列，如果满足，则称该排列为自然排列；对于中的一个排列，如果有整数，使得则称和构成一个“相邻逆序”；对于，如果它恰有一个“相邻逆序”，则称该排列为“一阶好排列”，中所有“一阶好排列”的个数记

18、为；如果它恰有两个“相邻逆序”，则称该排列为“二阶好排列”，中所有“二阶好排列”的个数记为；依题意知，恰好是要求的中“好排列”的个数。由题意知：，。以下为了叙述简便，我们把由给定的个不同实数的所有全排列构成的集合记为（），其次求。我们先来考察与之间的递推关系。对中的每一个“一阶好排列”（记为），我们考虑从中取出最大的数后剩下的个数按原来的顺序构成的排列（记为）。如果排列是中的“一阶好排列”，且“相邻逆序”为，那么，在排列中，的位置只能在之间或最后；如果排列不是中的“一阶好排列”，则排列中的“相邻逆序”的个数不为，显然排列中“相邻逆序”的个数不能大于（否则，排列不是“一阶好排列”，理由是：因为是

19、最大的数，所以排列中“相邻逆序”的个数一定不少于排列中“相邻逆序”的个数），从而排列中“相邻逆序”的个数为，此时排列是一个自然排列，而排列是“一阶好排列”，所以的位置不能在最后（有种可能的位置）。综合上面的分析可知：，即，所以，即。最后求。我们先来考察与之间的递推关系。对中的每一个“二阶好排列”（记为），我们考虑从中取出最大的数后剩下的个数按原来的顺序构成的排列（记为）。如果排列是中的“二阶好排列”，且“相邻逆序”为，那么在排列中，的位置只能在之间或之间，或者排在最后；如果排列不是中的“二阶好排列”，则它一定是中的“一阶好排列”，设“相邻逆序”为，因为排列是“二阶好排列”，所以的位置不能在之间

20、，也不能排在最后，其余位置都行，有种可能。综合上面分析可知：，又，所以，变形为所以，即，因此中“好排列”的个数为个。2010A四、（本题满分50分）一种密码锁的密码设置是在正边形的每个顶点处赋值和两个数中的一个，同时在每个顶点处染红、蓝两种颜色之一，使得任意相邻的两个顶点的数字或颜色中至少有一个相同.问：这种密码锁共有多少种不同的密码设置。解析：对于该种密码锁的一种密码设置，如果相邻两个顶点上所赋值的数字不同，在它们所在的边上标上a，如果颜色不同，则标上b，如果数字和颜色都相同，则标上c于是对于给定的点上的设置（共有4种），按照边上的字母可以依次确定点上的设置为了使得最终回到时的设置与初始时相

21、同，标有a和b的边都是偶数条所以这种密码锁的所有不同的密码设置方法数等于在边上标记a，b，c，使得标有a和b的边都是偶数条的方法数的4倍 设标有a的边有条，标有b的边有条，选取条边标记a的有种方法，在余下的边中取出条边标记b的有种方法，其余的边标记c由乘法原理，此时共有种标记方法对i，j求和，密码锁的所有不同的密码设置方法数为 这里我们约定 当n为奇数时，此时 代入式中，得 当n为偶数时，若，则式仍然成立；若，则正n边形的所有边都标记a，此时只有一种标记方法于是，当n为偶数时，所有不同的密码设置的方法数为 综上所述，这种密码锁的所有不同的密码设置方法数是：当n为奇数时有种；当n为偶数时有种 2

22、009*四、（本题满分50分）在非负数构成的数表中每行的数互不相同，前列中每列的三数之和为，均大于。如果的前三列构成的数表满足如下性质（）：对于数表中任意一列（）均存在某个使得。求证：最小值，一定来自数表的不同列；存在数表中唯一的一列，使得数表仍然具有性质（）。证明：（i）假设最小值不是取自数表的不同列。则存在一列不含任何.不妨设由于数表P中同一行中的任何两个元素都不等，于是另一方面，由于数表具有性质（），在（3）中取=2，则存在某个使得.矛盾。(ii)由抽屉原理知中至少有两个值取在同一列。不妨设.由前面的结论知数表的第一列一定含有某个，所以只能是.同样，第二列中也必含某个不妨设.于是，即是数

23、表中的对角线上数字：记M=1，2，.，9，令集合显然且.因为，所以.故.于是存在使得.显然， 下面证明数表具有性质（）.从上面的选法可知这说明又由满足性质（），在（3）中取，推得于是下证对任意的存在某个使得.假若不然，则且.这与的最大性矛盾。因此，数表满足性质（）。下证唯一性。设有使得数表，具有性质（）.不失一般性，我们假定（4） ，。由于，及（i），有又由（i)知：或者，或者如果成立，由数表具有性质（），则，（5） ，由数表满足性质（），则对于至少存在一个使得，又由（4），（5）式知，所以只能有同样由数表满足性质（），可推得于是，即数表 如果成立，则，（6） ，由数表满足性质（），对于，存在

24、某个使得，由及（4）和（6）式知，于是只能有类似地，由满足性质（）及可推得，从而。2007*二、（本题满分40分）。如图所示，在的长方形棋盘的每个小方格的中心点各放一个棋子。如果两个棋子所在的小方格共边或者共顶点，那么称这两个棋子相连。现从这个棋子中取出一些，使得棋盘上剩下的棋子，没有五个在一条直线（横竖斜方向）上依次相连。问最少取出多少个棋子才能满足要求？并说明理由。解析：解：最少要取出11个棋子，才可能满足要求。其原因如下：如果一个方格在第i行第j列，则记这个方格为(i，j)。第一步证明若任取10个棋子，则余下的棋子必有一个五子连珠，即五个棋子在一条直线（横、竖、斜方向）上依次相连。用反证

25、法。假设可取出10个棋子，使余下的棋子没有一个五子连珠。如图1，在每一行的前五格中必须各取出一个棋子，后三列的前五格中也必须各取出一个棋子。这样，10个被取出的棋子不会分布在右下角的阴影部分。同理，由对称性，也不会分布在其他角上的阴影部分。第1、2行必在每行取出一个，且只能分布在(1，4)、(1，5)、(2，4)、(2，5)这些方格。同理(6，4)、(6，5)、(7，4)、(7，5)这些方格上至少要取出2个棋子。在第1、2、3列，每列至少要取出一个棋子，分布在(3，1)、(3，2)、(3，3)、(4，1)、(4，2)、(4，3)、(5，1)、(5，2)、(5，3)所在区域，同理(3，6)、(3

26、，7)、(3，8)、(4，6)、(4，7)、(4，8)、(5，6)、(5，7)、(5，8)所在区域内至少取出3个棋子。这样，在这些区域内至少已取出了10个棋子。因此，在中心阴影区域内不能取出棋子。由于、这4个棋子至多被取出2个，从而，从斜的方向看必有五子连珠了。矛盾。图1图2第二步构造一种取法，共取走11个棋子，余下的棋子没有五子连珠。如图2，只要取出有标号位置的棋子，则余下的棋子不可能五子连珠。综上所述，最少要取走11个棋子，才可能使得余下的棋子没有五子连珠。2005*12、如果自然数的各位数字之和等于，那么称为“吉祥数”.将所有吉祥数从小到大排成一列，若，则 答案：解析：因为方程的非负整数

27、解的个数为，而使，（）的整数解个数为。现取，可知，位吉祥数的个数为因为是形如的数中最小的一个吉祥数，且，对四位吉祥数，其个数为满足的非负整数解的个数，即个。又是第个吉祥数，即，从而，。又，而所以从大到小最后六个五位吉祥数依次是，所以第个吉祥数是，即2003*三、（本题满分50分）。由个点和这些点之间的条连线段组成一个空间图形，其中，。已知此图中任四点不共面，每点至少有一条连线段，存在一点至少有条连线段证明：图中必存在一个空间四边形(即由四点和四条连线段组成的图形)证明：证明：设点集为，与连线的点集为，且于是又显然有，若存在一点与其余点都连线，不妨设则中个点的连线数(注意：)(由)但若在这个点内

28、，没有任一点同时与其余两点连线，则这个点内至多连线 条，故在中存在一点，它与两点、(互不相等，且)连了线，于是连成四边形现设任一点连的线数且设且设图中没有四边形于是当时，与没有公共的点对，即 ()记，则由，得 ()，且当且时，与无公共点对从而中点对个数即(由平均不等式) (注意)，即得到 (两边同乘以)即(注意到)得(各取部分因数比较)又（这里用到前面所得到的式子，） （这里也用到前面所得到的式子，）又、均为正整数，从而由、得，由、矛盾，知原命题成立又证：画一个表格，记题中个点为，若与连了线，则将表格中第行列的方格中心涂红于是表中共有个红点，当时，则表格中的行及列各有个红点且表格的主对角线上的

29、方格中心都没有涂红由已知，表格中必有一行有个红点不妨设最后一行前格为红点其余格则不为红点(若有红点则更易证)，于是：问题转化为：证明存在四个红点是一个边平行于格线的矩形顶点若否，则表格中任何四个红点其中心都不是一个边平行于格线的矩形顶点于是，前行的前个方格中，每行至多有个红点去掉表格的第行及前列，则至多去掉个红点于是在余下方格表中，至少有个红点设此表格中第行有()个红点，于是，同行的红点点对数的总和为其中(由于当时，故当红点总数为个时，可取行每行取个红点，行每行取个红点时取最小值，由下证可知红点数多于此数时更有利于证明)，但由假设，不存在处在不同行的2个红点对，使此四点两两同列，所以，有(由于

30、去掉了列，故还余列，不同的列对数为)即，所以即即显然矛盾故证2001*三、（本题满分50分） ) 将边长为正整数m，n的矩形划分成若干边长均为正整数的正方形每个正方形的边均平行于矩形的相应边试求这些正方形边长之和的最小值解析：记所求最小值为，我们可以证明(*)其中表示和的最大公约数事实上，不妨设，(1)关于归纳，可以证明存在一合乎题意的分法，使所得正方形边长之和恰为当时,命题显然成立 假设当时，结论成立（）当时，若，则命题显然成立若，从矩形中切去正方形（如图），由归纳假设矩形有一种分法使得所得正方形边长之和恰为.于是原矩形有一种分法使得所得正方形边长之和为。(2)关于归纳可以证明(*)成立当时

31、,由于，显然假设当mk时，对任意1nm有f (m，n)= m+n- (m，n)若，当时显然)当时，设矩形按要求分成了个正方形，其边长分别为，不妨设显然或若，则在与之间的与平行的任一直线至少穿过二个分成的正方形（或其边界），于是不小于与之和所以若，则一个边长分别为和的矩形可按题目要求分成边长分别为的正方形，由归纳假设。从而于是当时，再由(1)可知。1997*三、（本题满分50分）在的长方形表格中每一格填入一个非负实数，第行第列中填入的数为（，）如表，然后将表每列中的数按从小到大的次序从上到下重新排列为（）。如表。求最小的自然数，使得只要表中填入的数满足（），则当时，在表中就能保证。解析：在表1中

32、，取 ()，其余各数均取，于是，每列各数之和均等于但重新填入后，前行之和均等于第行之和等于故反之，如果表中第行的个数涂黄， 行共个数涂红，则这些涂红的数在表中至多分布在行中，于是除这行外的其余各行中的每个数都不小于同列中涂黄的数，即涂黄个数的和没有涂红数的行的每一行数的和1于是表2中第行的数的和1，故第行的数的和1即能保证表2中第行的数的和11996*四、（本题满分35分）有（）个人聚会，已知：每人至少同其中个人互相认识；对于其中任意个人，或者其中有人相识，或者余下的任中有人相识。证明：这个人中必有三人两两相识。证明：作一个图，用个点表示这个人，凡二人认识，则在表示此二人的点间连一条线问题即，

33、在题设条件下，存在以这点中的某三点为顶点的三角形设点连线条数最多，在与连线的所有点中点连线最多，与连线的点除外的集合为，与连线的点除外的集合为1 设，则每点至少连条线， 中都至少有个点若存在一点，与都连线，则满足要求；若没有任何两点与此二点都连线(图1)， 则由， ， 故得，且图中每点都连条线若 (或)中存在两点，这两点间连了一条线，则此二点与连出三角形，若中任何两点间均未连线，中任两点也未连线，则中不存在两点连线，中也不存在两点连线与已知矛盾2 设则每点至少连条线，中都至少有个点若存在一点，与都连线，则满足要求；若没有任何两点与此二点都连线，且，则由时(图2)，则由， 故得，若(或)中存在两

34、点，这两点间连了一条线，则此二点与连出三角形，若中任何两点间均未连线，中任两点也未连线，则中不存在两点连线，中也不存在两点连线与已知矛盾 若没有任何两点与此二点都连线，且，即每点都只连条线这时，必有一点与均未连线，设为与中个点连线，与中个点连线，且否则若，则中各点均未连线，中各点也未连线矛盾故且由于，即中至少有一个，不妨设，现任取中与连线的一点，由于与中其余各点均未连线，若与中的所有与连线的点均未连线，则连线数，矛盾，故至少与此个点中的一点连线故证1995*四、（本题满分35分）将平面上的每个点都以红，蓝两色之一着色。证明：存在这样两个相似的三角形，它们的相似比为，并且每一个三角形的三个顶点同

35、色。证明：首先证明平面上一定存在三个顶点同色的直角三角形任取平面上的一条直线，则直线上必有两点同色设此两点为，不妨设同着红色过作直线的垂线、，若或上有异于的点着红色，则存在红色直角三角形若、上除外均无红色点，则在上任取异于P的两点，则必着蓝色，过R作的垂线交于T，则T必着蓝色即为三顶点同色的直角三角形设直角三角形三顶点同色(为直角)把补成矩形 (如图)把矩形的每边都分成等分(为正奇数，本题中取)连结对边相应分点，把矩形分成个小矩形边上的分点共有个，由于为奇数，故必存在其中两个相邻的分点同色，(否则任两个相邻分点异色，则可得异色)，不妨设相邻分点同色考察所在的小矩形的另两个顶点，若异色，则或为三

36、个顶点同色的小直角三角形若同色，再考察以此二点为顶点而在其左边的小矩形，这样依次考察过去，不妨设这一行小矩形的每条竖边的两个顶点都同色同样，边上也存在两个相邻的顶点同色，设为，则考察所在的小矩形，同理，若所在小矩形的另一横边两个顶点异色，则存在三顶点同色的小直角三角形否则，所在列的小矩形的每条横边两个顶点都同色现考察所在行与所在列相交的矩形，如上述，都与同色，为顶点同色的直角三角形由，故，且相似比为，且这两个直角三角形的顶点分别同色证明2：首先证明：设为任意正实数，存在距离为的同色两点任取一点(设为红色点)，以为圆心，为半径作圆，若圆上有一个红点，则存在距离为的两个红点，若圆上没有红点，则任一

37、圆内接六边形的六个顶点均为蓝色，但此六边形边长为故存在距离为的两个蓝色点下面证明：存在边长为，的直角三角形，其三个顶点同色如上证，存在距离为的同色两点(设为红点)，以为直径作圆，并取圆内接六边形，若中有任一点为红色，则存在满足要求的红色三角形若为蓝色，则存在满足要求的蓝色三角形下面再证明本题：由上证知，存在边长为，及的两个同色三角形，满足要求证明3：以任一点为圆心，及为半径作两个同心圆，在小圆上任取9点，必有5点同色，设为，作射线，交大圆于，则此五点中必存在三点同色，设为则与为满足要求的三角形1994*四、（本题满分35分）给定平面上的点集，中任意三点均不共线，将中的所有的点任意分成组，使得每

38、组至少有个点，且每点恰好属于一组，然后黄在同一组的任意两点用一条线段相连，不在同一组的两点不连线段，这样得到一个图案，不同的分组方式得到不同的图案，将图案中所含的以中的点为顶点的三角形个数记为。求的最小值；设是的一个图案，若中的线段（指以的点为端点的线段）用种颜色染色，每条线段恰好染一种颜色。证明：存在一个染色方案，使染色后不含以的点为顶点的三边颜色相同的三角形。证明：设中分成的个子集的元素个数分别为()，且则即求此式的最小值设即则这就是说，当与的差大于1时，可用及代替与，而其余的数不变此时，的值变小于是可知，只有当各的值相差不超过1时，才能取得最小值故当组中有个点，组中有个点时，达到最小值

39、取个点为一小组，按图1染成二色这样的五个小组，如图2，每个小圆表示一个五点小组同组间染色如图1，不同组的点间的连线按图2染成两色这个点为一组，共得组染色法相同其中组去掉个点及与此点相连的所有线即得一种满足要求的染色1992*三、（本题满分35分）在平面直角坐标系中，任取个格点()满足：， ()； 任何三点不在一条直线上试证明：在以 ()为顶点的所有三角形中，必有一个三角形的面积不大于证明：如图，满足条件的格点只能是图中这个格点中的个把这个格点分成三个矩形：矩形、若所取的个点中有三个点在上述三个矩形中的某一个中，则此三点即满足要求若三个矩形中均无所取点中的点，则必是每个矩形中有所取的个点 若中有

40、所取的点，则此点与矩形中的两点满足要求； 若上述点均未取，则中必有两点，此时若中有所取的点，则亦有三点满足要求； 若亦未取，则必在中取了点，矩形中取了点：此时取两点，或两点，或两点，或两点，或两点，则无论中取任一点，与之组成三角形面积均满足要求若取两点，则矩形中必有一点异于，取此点与满足要求综上可知，必有满足要求的点存在1990*三(本题满分35分)某市有所中学，第所中学派出名代表(，)来到体育馆观看球赛，全部学生总数为看台上每一横排有个座位，要求同一学校的学生必须坐在同一横排，问体育馆最少要安排多少横排才能够保证全部学生都能坐下解析：首先，故每排至少可坐所学校的学生，故如果没有“同一学校的学

41、生必须坐在同一横排”的限制，则全部学生只要坐在排就够了现让这些学生先按学校顺序入坐，从第一排坐起，一个学校的学生全部坐好后，另一个学校的学生接下去坐，如果在某一行不够坐，则余下的学生坐到下一行这样一个空位都不留，则坐排，这些学生就全部坐完这时，有些学校的学生可能分坐在两行，让这些学校的学生全部从原坐处起来，坐到第排去由于，这种情况只可能在第一行末尾与第二行开头、第二行末尾与第三行开头、第九行末尾与第十行开头这处发生，故需要调整的学校不超过所，于是第行至多各坐所学校的学生，就可全部坐完这说明行保证够坐其次证明，行不能保证就此学生按条件全部入坐：取所学校，其中所学校人，所学校人则对前所学校的学生，

42、每排只能坐所学校而不能坐所学校故排只能坐其中所学校的学生即排不够坐综上可知，最少要安排横排才能保证全部学生都能坐下1987*二在坐标平面上，纵横坐标都是整数的点称为整点试证：存在一个同心圆的集合，使得 每个整点都在此集合的某个圆周上； 此集合的每个圆周上，有且只有一个整点(辛泽尔定理)证明：取一点，其两个坐标都是无理数，例如，先证明，以为圆心，任意长为半径作的圆，至多通过一个格点设某个以为圆心的圆通过两个格点，()，则展开整理得，左边是有理数，右边当且仅当时为有理数故证于是可知以为圆心的圆至多通过一个格点现考虑，平面上所有的点与的距离，这些距离没有两个相等故可以把所有的距离按从小到大排队对应的

43、整点依次为以W为圆心，以为半径作圆，则此圆恰经过整点且此圆只经过这个整点现取以为圆心，所有为半径的同心圆集则每个整点都在此同心圆集合中的某个圆上，且每个圆上都有且只有一个整点1987*三()名乒乓球选手单打若干场后，任意两个选手已赛过的对手恰好都不完全相同，试证明：总可以从中去掉一名选手，而使在余下的选手中，任意两个选手已赛过的对手仍然都不完全相同证明：证明1：用表示选手，而用表示已赛过的对手集合设是对手集中元素最多的的选手若命题不成立，则存在两个选手使去掉后，的对手集相同，由于，故必属于与之一不妨设，同样存在，使，去掉后，由于，故 ：又，故，即，从而，而去掉后，的对手集相同，从而于是，即比少一个元素，这与是“对手集中元素最多的”矛盾故证又证：把这些选手编为至号，以个点表示这个人，各点也相应编为1至号反设去掉任何一各选手后都有两个选手的已赛过的对手完全相同于是先去掉1号选手，则有两个选手的已赛过的对手完全相同，设为第i号与第j号，在表示