数论1981-2018年历年数学联赛48套真题WORD版分类汇编含详细答案.pdf

《数论1981-2018年历年数学联赛48套真题WORD版分类汇编含详细答案.pdf》由会员分享，可在线阅读，更多相关《数论1981-2018年历年数学联赛48套真题WORD版分类汇编含详细答案.pdf（60页珍藏版）》请在三一文库上搜索。

1、1981 年2018 年全国高中数学联赛二试试题分类汇编 组合与构造 1981-2018年历年数学联赛 48 套真题 2017A 三、 （本题满分50 分）将3333方格纸中每个小方格染三种颜色之一，使得每种颜色的小方 格的个数相等。若相邻两个小方格的颜色不同，则称他们的公共边为“分割边”。试求分割边条数的 最小值。 解析： 记分割边的条数为L.首先，将方格纸按如图所示分成三 个区域，分别染成三种颜色，粗线上均为分割边，此时共有56 条 分割边，即56L。 下面证明56L. 将方格纸的行从上至下依次记为 1 A, 2 A, 33 ,A,列从左至右依次记为 1 B, 2 B, 33 ,B,行 i

2、 A中方格出现的颜色数记为 i An， 列 i B中方格出现的颜色数记为 i Bn，三种颜色分别记为 1 c， 2 c， 3 c， 对于一种颜色 j c，设 i cn是表示含有 j c色方格的函数与列数之和. 记 色方格中不含 色方格中含有 ， ， ji ji ji cA cA cA 0 1 ,，同理定义 色方格中不含 色方格中含有 ， ， ji ji ji cB cB cB 0 1 ,， 则 3 1 33 1 3 1 33 1 3 1 33 1 , jij jjiji ij jiji i ii cncBcAcBcABnAn 由于染 j c色的方格有36333 3 1 2 个，设含有 j c色

3、方格的行有a个，列有b个，则 j c色方格一定 在这a行和b列的交叉方格中，因此363ab.从而3836322 abbacn i 即39 i cn.,3 ,2, 1j 由于在行 i A中有 i An种颜色的方格，因此至少有1 i An条分割边，同理在行 i B中有 i Bn种颜 色的方格，因此至少有1 iBn条分割边，于是， 666611 3 1 33 1 33 1 33 1j j i ii i i i i cnBnAnBnAnL 下面分两种情形讨论. 当有一行或有一列全部方格同色时，不妨设有一行全为 1 c色，从而方格纸的33 列中均含有 1 c的方 格，由于 1 c的方格有363 个，故至

4、少有11行中含有 1 c色方格。于是443311 1 cn。 由得566639394466 321 cncncnL 没有一行或没有一列全部方格同色时，则对任意 331i ，均有2 i An，2 i Bn，从而由 知，566643366 33 1i ii BnAnL 综上可知，分割边条数的最小值为56。 2017A 四、 （本题满分50 分） 。设nm,均是大于1的整数，nm， n aaa, 21 是n个不超过m的 互不相同的正整数，且 n aaa, 21 互素。证明：对任意实数x，均存在一个i（ni1） ，使得 x mm xai )1( 2 ，这里y表示实数y到它最近的整数的距离。 证明： 首

5、先证明两个引理： 引理 1：存在整数 n ccc, 21 ，满足1 2211nna cacac，并且mci，ni1. 由 于 n aaa, 21 互 素 ， 即 1, 21n aaa， 有 裴 蜀 定 理 ， 存 在 整 数 n ccc, 21 ， 满 足 1 2211nna cacac。 下面证明，通过调整，存在一组 n ccc, 21 满足，且mci，记0, 211 mc in i ccccS， 0, 211 mc jn j ccccS。 如果0 1 S，那么存在1mci ，于是1 iic a，又 n aaa, 21 是大于1 的整数，故由可知， 存在0 j c，令 jii acc / ，

6、 ijj acc / ， kk cc / （nk1，jik,） ，则 1 / 2 / 21 / 1nna cacac，并且 iij ccam / 0，macc kjj / ， 所以 nn cccScccS, 211 / 211 、 ， nn cccScccS, 212 / 212 、 如果0 2 S， 则存在mcj， 因此有一个0 i c.令 jii acc / ， ijj acc / ， kk cc / （nk1， jik,）， 那 么 成 立 ， 并 且0, / jjii ccccm， 与 上 面 类 似 可 以 证 明 到 ： nn cccScccS, 211 / 211 、 ， nn

7、cccScccS, 212 / 212 、 ，即说明 1 S与 2 S均是非 负整数，故通过有限次上述的调整，可以得到一组使得成立，并且0 21 SS结论获证。 引理 2：对任意的实数ba,，均有baba；对任意整数u和实数v， 有vuuv； 由于对任意整数u和实数x， 均有xxu， 于是不妨设 2 1 , 2 1 ,ba， 此时aa，bb， 若0ab，不妨设ba0，则 2 1 , 2 1 ba，从而babababa 若0ab，不妨设ba,同号，则当 2 1 ba时，有 2 1 , 2 1 ba， 此时babababa；当 2 1 ba时，注意到总有 2 1 ba，故 bababa 2 1 ；

8、故得证； 又yy，由知，是成立的。 接下来回到原题，由结论存在整数 n ccc, 21 ，满足1 2211nna cacac，并且mci， ni1.于是，xxac n i ii 1 ，由引理2 得 n i i n i ii n i ii xamxacxacx 111 ， 因此，x mn xai ni 1 max 1 若 2 1m n，则由知， 1 2 1 max 1 mm x x mn xai ni 若 2 1m n， 则 在 n aaa, 21 中 存 在 两 个 相 邻 的 正 整 数 。 不 妨 设 21,a a相 邻 ， 则 xaxaxaxax 1212 ，故xa2 与xa1中有一个不

9、小于 1 2 2mm xx 。 综上，总存在存在一个i（ni1） ，使得x mm xai )1( 2 2016A 三、 （本题满分50 分）给定空间10个点，其中任意四点不在一个平面上。将某些点之间用线 段相连，若得到的图形中没有三角形也没有空间四边形，试确定所连线段数目的最大值。 解析： 以这 10 个点为顶点，所连线段为边，得到一个10 阶简单图G，我们证明G 的变数不超过 15. 设 G的顶点为 1021 ,vvv， 一共有k条边，用 i vD表示顶点 i v的度。若3 i vD对10,3 ,2, 1i 都成立，则15310 2 1 2 1 10 1i i vDk。 假设存在 i v满足

10、4 i vD，不妨设4 1 nvD，且 1 v与 12 , n vv均相邻 . 于是 12 , n vv之间 没有边，否则就成三角形，所以 1 v与 12 , n vv之间恰有n条边 . 对每个j（102jn） ， j v至多与 12 , n vv中的一个顶点相邻（否则设 j v与 s v， t v （12nts）相邻，则 1 v， 2 v， j v ， t v就对应了一个空间四边形的四个顶点，这与题意矛 盾） ，从而 12 , n vv与 102 ,vvn 之间的边数至多nn9)1(10条。 在 nn vv, 2 这n9个顶点之间，由于没有三角形，由托兰定理，至多 4 9 2 n 条边，因此

11、G的 边数 15 4 25 9 4 9 9 4 9 )9( 22 nn nnk 例如如图所示的就有 15条边，且满足要求。 综上所述，所连线段数目的最大值为15。 2014B 四、 （本题满分50 分）设ABC是一个边长为32的等边三角形， 在ABC的内部和边界上 任取11个点 . (1) 证明：一定存在两个点，它们之间的距离小于或等于1； （20 分） (2) 证明：一定存在两个点，它们之间的距离严格小于1； （30 分） 证明： (1)如左下图 1，我们将 ABC分成16个边长为 2 3 的小等边三角形；对于中间的图2 中六 个灰色的小三角形，我们将它们剖分成三个全等的三角形；这样，我们就

12、可以看出ABC就可以被 右图 3 的10个正六边形所覆盖。 图 1 图 2 图 3 不难看出，这里的10个正六边形的直径为1，它们可以被看做10只“抽屉”，对于三角形ABC内 部和边界上任取 11个点，根据抽屉原理，至少有一个正六边形包含两个点。而在这个正六边形中， 任意两点间的距离不超过1，这样便证明了我们所要的结论。 （要注意，我们的抽屉的构造并不是唯一的，我们还可以用下图4 所示的10个直径为1的圆覆盖 ABC，也可以得到同样的结论） 图 4 图 5 (2)这部分要求证明的是严格不等号。我们要证明在11个点中存在两个点，他们间的距离严格小于1， 注意到直径为1的正六边形中，间距恰好为1的

13、两个点一定是距离最远的一对点，另一方面，上面所 构造的正六边形抽屉在边和顶点处是由重复的，我们通过指定一条边或者顶点属于那一个特定的正 六边形来改造我们的“抽屉”，使得每一个抽屉不包含正六边形中距离为1的顶点对，当然，在目前 的情况我们只需关心怎么改造顶点即可。 我们在每一个正六边形抽屉上去掉一些顶点，使得每一个抽屉不在包含正六边形中距离为1的顶点 对，如图5 就是一个办法，图中空心的点表示正六边形中去掉该点，不难看出，这样的改造还是覆 盖了原来得三角形ABC，且每一个抽屉不在包含正六边形中距离为1的顶点对，根据抽屉原理， 我们就证明了：任取 11个点，一定存在两个点，它们之间的距离严格小于1

14、。 （这样的抽屉构造也是 不唯一的） 2013B 四、 （本题满分50 分）用若干单位小正方形和由三个单位小方格组成的形“砖”铺满一 个2n的方格棋盘的所有不同可能铺法的数目是 n T下面的图是3n时的两种不同的铺法： 求 10 T； 求 2013 T的个位数 证明： 由题意显然1 1 T，5 2 T， 当 3n 时，我们从左向右地铺 n2 的方格棋盘，无论哪一种铺法，至多铺到 32 ，我们一定会完 成一个k2（,3 ,2, 1k）的矩形。这样我们计算 n T时，就可以去寻找与 321 , nnn TTT的关系，又 由下图 我们得到 321 24 nnnn TTTT 由1 1 T，5 2 T，

15、得11 3 T，33 4 T,87 5 T,依次下去可得13377 10 T 由 321 24 nnnn TTTT，1 1 T，5 2 T，11 3 T，可知， n T一定是奇数。 我们由5mod计 算 2013 T，对每一个 n T，我们有： (1 1 T,0 2 T,1 3 T,3 4 T,2 5 T,1 6 T,0 7 T,3 8 T,0 9 T,2 10 T,3 11 T,1 12 T, 2 13 T,2 14 T,2 15 T,4 16 T,1 17 T,1 18 T,3 19 T,4 20 T,3 21 T,0 22 T,0 23 T, 1 24 T,)1 25 T,0 26 T,

16、1 27 T,3 28 T,2 29 T,1 30 T, 可知， n T的个位数的周期是24。而21201324mod，又5mod等于3的奇数10mod也一定等 于3，所以 2013 T的个位数为3。 2012A 三、 （本题满分50 分）设 012 , n P P PP是平面上1n个点，它们两两间的距离的最小值为 (0)d d，求证： 01020 ()(1)! 3 n n d P PP PP Pn 证明： 证法一 : 不妨设 01020 . n PPP PP P先证明 : 对任意正整数k, 都有 0 1 3 k d P Pk 显然 , 0 1 3 k d P Pdk对1,2,8k均成立 ,

17、只有8k时右边取等号10 分 所以 , 只要证明当 9k 时, 有 0 1 3 k d P Pk即可 . 以(0,1,2, ) i P ik为圆心 , 2 d 为半径画1k个圆 , 它们两两相离或外切; 以 0 P圆心， 0 2 k d P P为 半径画圆，这个圆覆盖上述1k个圆20 分 所以 22 00 ()(1) ()(11) 222 kk ddd P PkP Pk30 分 由9k易知 111 23 kk 40 分 所以 0 1 3 k d P Pk对9k时也成立 . 综上 , 对任意正整数k都有 0 1 3 k d P Pk. 因而 01020 ()(1)! 3 n n d P PP P

18、P Pn50 分 证法二 : 不妨设 01020 . n P PPPPP 以(0,1,2, ) i P ik为圆心 , 2 d 为半径画1k个圆 , 它们两两相离或外切; 10 分 设Q是是圆 i P上任意一点 , 由于 000000 13 222 iiikkk d PQP PPQP PP PP PP P20 分 因而 , 以 0 P为圆心 , 0 3 2 k P P为半径的圆覆盖上述个圆30 分 故 22 00 3 ()(1) ()1(1,2, ) 223 kk dd P PkP Pkkn40 分 所以 01020 ()(1)! 3 n n d P PP PP Pn50 分 2011A 四、

19、 （本题满分50 分）设 A是一个93的方格表， 在每一个小方格内各填一个正整数称 A 中的一个)91, 31(nmnm方格表为“好矩形” ，若它的所有数的和为10 的倍数称A中的 一个11的小方格为“坏格” ，若它不包含于任何一个“好矩形”求 A中“坏格”个数的最大值 解析： 首先证明A 中“坏格”不多于25 个 用反证法假设结论不成立，则方格表A中至多有1个小方格不是“坏格” 由表格的对称性， 不妨假设此时第1 行都是“坏格” 设方格表A第i列从上到下填的数依次为9,2, 1,icba iii 记9 ,2, 1 ,0, )(, 11 kcbTaS k i iik k i ik ，这里0 0

20、0 TS 我们证明：三组数 910 ,SSS； 910 ,TTT及 991100 ,TSTSTS都是模10 的完 全剩余系 事实上，假如存在90,nmnm，使)10(mod nm SS，则 )10(mod0 1 mn n mi i SSa， 即第 1 行的第 1m 至第n列组成一个“好矩形” ，与第 1 行都是“坏格”矛盾 又假如存在90,nmnm，使)10(mod nmTT ，则)10(mod0)( 1 mn n mi iiTTcb ， 即第 2 行至第 3 行、第1m列至第n列组成一个“好矩形” ，从而至少有2 个小方格不是“坏格” ， 矛盾 类似地，也不存在90,nmnm，使)10(mo

21、d nnmm TSTS 因此上述断言得证故 )10(mod59210)( 9 0 9 0 9 0k kk k k k k TSTS， 所以)10(mod055)( 9 0 9 0 9 0k k k k k kk TSTS， 矛盾！故假设不成立，即“坏格”不可能多于25 个 另一方面，构造如下一个93的方格表，可验证每个不填10 的小方格都是“坏格”，此时有 25 个“坏格” 综上所述，“坏格”个数的最大值是25 2011B 四 、 （ 本 题 满 分50 分 ） 给 定n个 不 同 实 数 ， 其 所 有 全 排 列 组 成 的 集 合 为 n A.对 于 12 (,) nn a aaA，若恰

22、有两个不同的整数,1,2,1 i jn使得 11 , iijj aaaa成立， 则称 该排列为“好排列”.求 n A中“好排列”的个数. 解析： 首先定义： 对于A中的一个排列 n aaa, 21 ，如果满足 n aaa 21 ，则称该排列为自然排列； 对于A中的一个排列 n aaa, 21 ，如果有整数1,2, 1ni，使得 1ii aa则称 i a和 1i a构成一个“相邻逆序” ； 对于Aaaa n , 21 ，如果它恰有一个“相邻逆序”，则称该排列为“一阶好排列”，A中所 有“一阶好排列”的个数记为)( 1 nf；如果它恰有两个“相邻逆序”，则称该排列为“二阶好排列”， A中所有“二阶

23、好排列”的个数记为)( 2 nf；依题意知，)( 2 nf恰好是要求的A中“好排列”的个 数。 由题意知：0)1 ( 1 f，1)2( 1 f，0)2() 1( 22 ff，1)3( 2 f。 以 下 为 了 叙 述 简 便 ， 我 们 把 由 给 定 的k个 不 同 实 数 的 所 有 全 排 列 构 成 的 集 合 记 为 k A 1 1 1 2 1 1 1 1 10 1 1 1 1 1 1 1 1 1 1 1 1 10 1 1 1 1 2 （nk,2, 1） ，其次求)( 1 nf。 我们先来考察)1( 1 kf与)( 1 kf之间的递推关系。 对 1k A中的每一个“一阶好排列”（记为

24、a） ，我们考虑从中取出最大的数 1k a后剩下的k个数 k aaa, 21 按原来的顺序构成的排列（记为b） 。 如果排列b是 k A中的“一阶好排列” ，且“相邻逆序”为 1ii aa，那么，在排列a中， 1k a的 位置只能在 1 , ii aa之间或最后； 如果排列b不是 k A中的“一阶好排列” ，则排列b中的“相邻逆序”的个数不为1，显然排列b 中“相邻逆序”的个数不能大于1（否则，排列a不是“一阶好排列” ，理由是：因为 1k a是最大的 数，所以排列a中“相邻逆序” 的个数一定不少于排列b中“相邻逆序” 的个数），从而排列b中“相 邻逆序”的个数为0，此时排列b是一个自然排列，

25、而排列a是“一阶好排列” ，所以 1k a的位置不 能在最后（有 k种可能的位置） 。 综合上面的分析可知：kkfkf)(2)1( 11 ，即1)(21)1()1( 11 kkfkkf， 所以 2 1 241)( n nnf，即12)( 1 nnf n 。 最后求)( 2 nf。 我们先来考察) 1( 2 kf与)( 2 kf之间的递推关系。 对 1k A中的每一个“二阶好排列”（记为c） ，我们考虑从中取出最大的数 1k a后剩下的k个数 k aaa, 21 按原来的顺序构成的排列（记为d） 。 如果排列d是 k A中的“二阶好排列” ，且“相邻逆序”为 1ii aa， 1jj aa，那么在

26、排列c 中， 1k a的位置只能在 1 , ii aa之间或 1 , jj aa 之间，或者排在最后； 如果排列d不是 k A中的“二阶好排列” ，则它一定是 k A中的“一阶好排列” ，设“相邻逆序” 为 1ii aa，因为排列c是“二阶好排列” ，所以 1k a的位置不能在 1 , ii aa之间，也不能排在最后， 其余位置都行，有1k种可能。 综合上面分析可知：)(1)(3)1( 122 kfkkfkf，又12)( 1 nnf n ，所以 )12(1)(3)1( 22 kkkfkf k ，变形为 )1( 2 1 21)(3)2)(1( 2 1 2)2() 1( 2 1 2 kkkkfkk

27、kkf kk 所以 3 2327)1( 2 1 21)( nn nnnnf，即1 2 1 2)1(3)(2nnnnf nn ， 因此 n A中“好排列”的个数为1 2 1 2)1(3nnn nn 个。 2010A 四、 （本题满分50 分） 一种密码锁的密码设置是在正n边形 n AAA 21 的每个顶点处赋值 0和 1两个数中的一个，同时在每个顶点处染红、蓝两种颜色之一，使得任意相邻的两个顶点的数字或颜 色中至少有一个相同.问：这种密码锁共有多少种不同的密码设置。 解析： 对于该种密码锁的一种密码设置，如果相邻两个顶点上所赋值的数字不同，在它们所在的 边上标上a，如果颜色不同，则标上b，如果数

28、字和颜色都相同，则标上c于是对于给定的点 1 A上 的设置（共有 4 种） ，按照边上的字母可以依次确定点 23 , n AAA上的设置 为了使得最终回到 1 A 时的设置与初始时相同，标有a 和 b 的边都是偶数条所以这种密码锁的所有不同的密码设置方法 数等于在边上标记a，b， c，使得标有a 和 b 的边都是偶数条的方法数的4 倍 设标有 a 的边有2i条，0 2 n i，标有 b 的边有2 j条， 2 0 2 ni j选取2i条边标 记 a 的有 2i n C种方法， 在余下的边中取出2 j条边标记b的有 2 2 j ni C种方法， 其余的边标记c由乘法 原理，此时共有 2i n C

29、2 2 j ni C种标记方法对i，j 求和，密码锁的所有不同的密码设置方法数为 2 22 22 2 00 4 nni ij nni ij CC 这里我们约定 0 0 1C 当 n 为奇数时，20ni，此时 2 2 221 2 0 2 ni jni ni j C 代入式中，得 2 2222 2222122 2 0000 44222 nninn ijiniini nninn ijii CCCC 00 22( 1)(21)(21) nn knkkn kknn nn kk CC 31 n 当 n 为偶数时，若 2 n i，则式仍然成立；若 2 n i，则正 n 边形的所有边都标记a，此时 只有一种标

30、记方法于是，当n 为偶数时，所有不同的密码设置的方法数为 2 22 22 2 00 4 nni ij nni ij CC 1 2 221 0 412 n ini n i C 2 221 0 24233 n inin n i C 综上所述，这种密码锁的所有不同的密码设置方法数是：当n 为奇数时有31 n 种；当 n 为 偶数时有33 n 种 2009* 四、 （本题满分50 分）在非负数构成的93数表 393837363534333231 292827262524232221 191817161514131211 xxxxxxxxx xxxxxxxxx xxxxxxxxx P 中每行的数互不相同

31、，前6列中每列的三数之和为1，0 392817 xxx， 291938183727 ,xxxxxx 均大于1。如果P的前三列构成的数表 333231 232221 131211 xxx xxx xxx S满足如下性质（O） ：对于数表P中任 意一列 k k k x x x 3 2 1 （9, 2, 1k）均存在某个3 ,2, 1i使得 13211,minxxxuxiiik。求证： 最小值 1321 ,minxxxu iii ，3,2, 1i一定来自数表S的不同列； 存在数表P中唯一的一列 k k k x x x 3 2 1 ，3 ,2, 1 k，使得33数表 k k k xxx xxx xxx

32、 S 3 3231 2 2221 1 1211 仍然具有 性质（O） 。 证明：（i ）假设最小值3, 2, 1,min 321 ixxxu iiii 不是取自数表S的不同列。 则存在一列不含 任 何 i u. 不 妨 设.3,2, 1, 2 ixu ii 由 于 数 表P 中 同 一 行 中 的 任 何 两 个 元 素 都 不 等 ， 于 是 .3 ,2, 1, 2 ixu ii 另一方面，由于数表 S具有性质 （ ） ，在（3）中取k=2，则存在某个 3 ,2, 1 0 i 使得 002ii ux. 矛盾。 (ii)由抽屉原理知,min,min,min 323122211211 xxxxx

33、x 中至少有两个值取在同一列。不妨设 323231222221 ,min,minxxxxxx. 由前面的结论知数表S的第一列一定含有某个 i u，所以只能是 111 ux. 同样，第二列中也必含某个 .2, 1,iui 不妨设 222 ux. 于是 333 xu，即 i u是数表S中的对角线上数字： 111213 212223 313233 xxx Sxxx xxx 记 M= 1， 2，.，9 ，令集合 3, 1,min| 21 ixxxMkI iiik 显然,| 323111 xxxxMkI kk 且I3 ,2, 1. 因为 32113818 ,1,xxxx，所以I8. 故I. 于是存在Ik

34、 * 使得|max 2 2 *Ikxx k k . 显然，.3, 2, 1 * k 下面证明33数表 * * * 1112 1 2122 2 3132 3 k k k xxx Sxxx xxx 具有性质（）. 从上面的选法可知).3 , 1(,min,min: 2121 *ixxxxxu ii ik iii 这说明 33231 3 11211 1 ,min,min *uxxxuxxx kk 又由S满足性质（） ，在（ 3）中取 * kk，推得, 2 2 *ux k 于是 * 22 2221 2 ,min kk xxxxu 下证对任意的,Mk存在某个3,2, 1i使得 iki xu . 假若不然

35、，则3 , 1,min 21 ixxx iiik 且 * 2 2 k k xx. 这与* 2k x的最大性矛盾。因此，数表 S满足性质（） 。 下证唯一性。设有 Mk 使得数表 S， k k k xxx xxx xxx S 33331 22221 11211 ? 具 有 性 质 （） .不 失 一 般 性 ， 我 们 假定 111312111 ,minxxxxu（ 4 ） 222322212 ,minxxxxu， 333332313 ,minxxxxu。 3132 xx 由 于 3132 xx， 2122 xx， 及 （ i ）， 有.,min? 11112111 xxxxu k 又 由 （

36、i)知 ： 或 者 kk xxxxua 3332313 ,min?)(，或者.,min?)( 2222212kk xxxxub 如果)(a成立，由数表S ?具有性质（ ） ，则 11112111 ,min?xxxxu k ， （5） 22222212 ,min?xxxxu k ， kk xxxxu 3332313 ,min? 由数表S ?满足性质（ ） ，则对于M3至少存在一个3,2, 1i使得 3 ? ii xu，又由（ 4） ， （5）式 知，.?,? 2322213111 xxuxxu所以只能有.? 3333 xxu k 同样由数表S满足性质（） ，可推得 .333k xx于是3k，即数

37、表SS ? 如 果)(b成 立 ， 则 11112111 ,min?xxxxu k ， 11112111 ,min?xxxxu k ，（ 6 ） kk xxxxu 2222212 ,min?， 32332313 ,min?xxxxu k 由数表S ?满足性质（ ） ，对于Mk * ，存在某个3, 2, 1i使得*? ik i xu ， 由Ik * 及（ 4）和（ 6）式知，.?,? 332 3 111 1 *uxxuxx kk 于是只能有.? 22 2 * k k xux类似地，由S满足性质（）及Mk可推得 * 2 22 k k xux，从而 kk * 。 2007* 二、 （本题满分40 分

38、） 。如图所示， 在87的长方形棋盘的每个小方格的中心点各放一个棋子。 如果两个棋子所在的小方格共边或者共顶点，那么称这两个棋子相连。现从这56个棋子中取出一些， 使得棋盘上剩下的棋子，没有五个在一条直线（横竖斜方向）上依次相连。问最少取出多少个棋子 才能满足要求？并说明理由。 解析： 解： 最少要取出11 个棋子，才可能满足要求。其原因如下： 如果一个方格在第i 行第 j 列，则记这个方格为(i，j)。 第一步证明若任取10 个棋子，则余下的棋子必有一个五子连 珠，即五个棋子在一条直线（横、竖、斜方向）上依次相连。 用反证法。假设可取出10 个棋子，使余下的棋子没有一个五 子连珠。如图1，在

39、每一行的前五格中必须各取出一个棋子， 后三列的前五格中也必须各取出一个棋子。这样，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，7)、(3，8)、(4，6)、

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

41、若2005 n a，则 n a5 答案：5200 解析：因为方程mxxx k21 的非负整数解的个数为 m km C 1 ， 而使1 1 x，0 i x（2i） 的整数解个数为 1 2 m kmC 。现取7m，可知，k位吉祥数的个数为 6 5)(kCkp 因为2005是形如abc2的数中最小的一个吉祥数，且1)1(p，7)2(p，28)3(p，对四位吉 祥数abc1，其个数为满足6cba的非负整数解的个数，即28 6 136 C个。 又2005是第651282871个吉祥数，即2005 66 a，从而65n，3255n。 又84)4(p，210)5(p，而330)5()4()3()2()1(p

42、pppp 所以从大到小最后六个五位吉祥数依次是52000,60001,60010,60100,61000,70000， 所以第325个吉祥数是52000，即52000 5n a 2003* 三、 （本题满分50 分）。由n个点和这些点之间的l条连线段组成一个空间图形，其中 1 2 qqn，1)1( 2 12 qql，2q，Nq。已知此图中任四点不共面，每点至少有一条 连线段， 存在一点至少有2q条连线段 证明： 图中必存在一个空间四边形( 即由四点DCBA,和 四条连线段DACDBCAB,组成的图形 ) 证明： 证明：设点集为 110 , n AAAV， 与 i A连线的点集为 i B， 且

43、ii bB 于是11nbi 又 显然有212 2 1 0 qqlb n i i ， 若存在一点与其余点都连线，不妨设1 0nb 则 0B中1n个点的连线数111 2 12 0 nqqbl( 注意：11 2 nqqqq) 1 2 1 111 2 1 1111 2 1n nqnnq( 由2q) 但若在这1n个点内，没有任一点同时与其余两点连线，则这1n个点内至多连线 2 1n 条， 故在 0 B中存在一点 i A， 它与两点 j A 、 k A(kji,互不相等， 且1,kji) 连了线，于是 kij AAAA, 0 连成四边形 现设任一点连的线数2n且设22 0 nqb且设图中没有四边形于是当j

44、i时， i B与 j B没有公共的点对，即1 ji BB (1,0nji) 记 00 BVB，则由1 0 BBi， 得1 0ii bBB (1,2, 1ni) ，且当1,1nji且ji时， 0 BBi与 0 BBj无公共点 对从而 0 B中点对个数 1 1 0 n i i BB中点对个数即 1 1 1 1 2 1 1 2 1 1 2 1 1 1 22 123 1 1 2 1 23 2 1 0 0 n i i n i i n i ii n i b n i BB bn nbb n bbCCC i i ( 由平均不等式) 12232 1 1 2 1 0 2 0nblbl n 2 0 2 0 1221

45、32 1 1 2 1 nblnbl n 22212 12 1 00 nblnbl n ( 注意211212 2 qnqql) ， 即得到 00 2 21121 12 1 0 bqnbqn n C bn ( 两边同乘以12 n) 即 00 1bnbn 00 21121bqnbqn( 注意到11qqn) 得 00 11bnbnqq 00 32bnnqbqnq( 各取部分因数比较) 又013213113 2 000 nqqnqqnbqbnqbnnq （这里用到前面所得到的式子2 0qb，11 2 nqqqq） 012222121 2 000 nqqnqqqnqqbbnqbqn （这里也用到前面所得到

46、的式子2 0 qb，11 2 nqqqq） 又 0 3bnnq、 0 2bqnq、 0 1bnq、 0 1bnq均为正整数， 从而由、得， 00 11bnbnqq 00 32bnnqbqnq 由、矛盾，知原命题成立 又证： 画一个nn表格， 记题中n个点为 n AAA, 21 ，若 i A与 j A连了线， 则将表格中第i行 j列的方格中心涂红于是表中共有l 2个红点， 当mAd i 时，则表格中的i行及i列各有m个红 点且表格的主对角线上的方格中心都没有涂红 由已知，表格中必有一行有2q个红点不妨设最后一行前2q格为红点其余格则不为红 点( 若有红点则更易证) ，于是： 问题转化为：证明存在

47、四个红点是一个边平行于格线的矩形顶点 若否，则表格中任何四个红点其中心都不是一个边平行于格线的矩形顶点于是，前1n行的 前2q个方格中，每行至多有1个红点去掉表格的第n行及前2q列，则至多去掉 1)1(2)1(2 22 qqqqnq个红点 于是在余下)2)(1(qnn方格表中， 至少有 qqqqqqql 23222 1)1(2)1(1)1(2个红点 设此表格中第i行有 i m(1,2, 1ni) 个红点，于是，同行的红点点对数的总和为 1 1 2 n i mi C 其 中1 2 nqq( 由于当kn时， 2 1 2 1 22 knkn CCCC，故当红点总数为qqq 23 个时，可 取 2 q

48、行每行取q个红点，q行每行取1q个红点时 1 1 2 n i mi C取最小值，由下证可知红点数多于此数 时更有利于证明)，但 1 1 22 1 22 n i mqq i CqCCq 由假设，不存在处在不同行的2 个红点对，使此四点两两同列，所以，有( 由于去掉了2q列， 故还余1 2 q列，不同的列对数为 2 1 2 q C) n m D A C B A1 D1 即 2 1 1 1 2 2 q n i m CC i ，所以21)2)(1()1( 222 qqqqqqqq 即211)2)(1( 22 qqqqqqq 即222 2323 qqqqqq显然矛盾故证 2001* 三、 （本题满分50 分） ) 将边长为正整数m， n 的矩形划分成若干边长均为正整数的正方形每 个正方形的边均平行于矩形的相应边试求这些正方形边长之和的最小值 解析： 记所求最小值为),(nmf， 我们可以证明),(),(nmnmnmf (*) 其中),(nm表示m和n的最大公约数事实