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

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

2、6.将方格纸的行从上至下依次记为A1, A2, , A33，列从左至右依次记为BB2,，B33,行Ai中方格出现的颜色数记为n（A ）,11列Bi中方格出现的颜色数记为n（Bi ）,三种颜色分别记为C1 , C2,C3,对于一种颜色 q ,设nC 诞表示含有Cj色方格的函数与列数之和3333 33 333则工(n(A )+n(BiZ (-(Ai, cj- (Bi, cj )=E Z (-(Ai,cj)+-(Bi,cj )=Z n(cj)Di 1iWjWj=1iWj=1,一 1由于染Cj色的方格有-父332 =363个，设含有Cj色方格的行有a个，列有b个，则Cj色方格一定 3在这a行和b列的交

3、叉方格中，因此 ab之363.从而n（ci a + b > 2V ab > 2v 363 > 38即 n(G )至39. j =1,2,31.由于在行A中有n（A颜色的方格，因此至少有n（A ）-1条分割边，同理在行 Bi中有n（Bi ）种颜色的方格，因此至少有 n（Bi ）-1条分割边，于是，3333333L（n（A）1 ）+£（n（Bi卜1 上£（n（A）+n（Bi）卜66=£n（c）66i 1i 1i 1j 1下面分两种情形讨论.当有一行或有一列全部方格同色时，不妨设有一行全为 G色，从而方格纸的33列中均含有G的方格，由于Ci的方格有36

4、3个，故至少有11行中含有Ci色方格。于是n(ci巨11+ 33 = 44。由得 L_nc1 n c2 n c3 -66 _44 39 39 一66 = 56没有一行或没有一列全部方格同色时，则对任意1 < i < 33 ,均有n(A )>2, nBi )>2 ,从而由33知，Ln Ain Bi -66-33 4 -66 56i 1综上可知，分割边条数的最小值为56。2017A四、(本题满分50分)。设m,n均是大于1的整数，m >n , a1,a2,，an是n个不超过m的互不相同的正整数，且a1，a2,，an互素。证明：对任意实数x ,均存在一个i( 1 w i

5、 E n),使得y到它最近的整数的距离。2aix < x ,这里y表不实数m(m 1)证明：首先证明两个引理:引理1:存在整数eq,，a ,满足Ga1 +c2a2 +aan =1 ,并且ci Mm, 1 w i w n .由于a1，a2,，an互素，即冏e2,，an )=1 ,有裴蜀定理，存在整数。，品，满足c1a1 +c2a2 + +cnan =1 。卜面证明，通过调整，存在一组C1,c2,，Cn满足，且ci Wm,记S1(q,C2,，cn)=£ q >0,Ci mS(G,C2,，Cn )= £ Cj >0oCj :二划如果s1>0,那么存在Ci

6、Am A1 ,于是aiCi A1 ,又a1，a2,，an是大于1的整数，故由可知,存在 q <0 ,令Ci/ =Ci aj, C/ =5 +ai, c：=Ck(1w k w n ,k ¥ i, j),则C/a1 +c2a2 +c；an =1, 并且 0 m-ajWei/<ci, cj <c/j<ak m ,所以S1G , C2 , Cn :二 S1C1, C2 ,S2 c1 ,C2 , Cn :二 S2 C1 ,C2,Cn如果 S2 >0，则存在Cj<-m ,因此有一个 g >0 .令 ci/=ciaj ,c/=5 +ai,ek=Ck (1

7、< kn ,k#i,j）,那么成立，并且m<c/<Ci,Cj<c/<0,与上面类似可以证明至ij：S1 = S2 = 0结论获证。S1 (c17 c2,，cn k S1 (c17 c2,，cnS2 (c1 7 c2,，cn)< S2 (c1 7c2,，cn 卜即说明S1与 S2均是非引理2：对任意的实数a,b，均有负整数，故通过有限次上述的调整，可以得到一组使得成立，并且|a +b| <|a| +|b ；对任意整数u和实数v , 有网.|u| |v| ;由于对任意整数u和实数x,均有u十E|x|,于是不妨设a,bw上!，此时同=a，|b = b，若ab

8、 W0,不妨设a <0 <b,则a+bw1 12，2，从而 la +1右ab >0 ,不妨设a,b同方，则当a+bE时，有a+bw 2;_1HIL. 2'2 'a +b| =|a + b =|a| +|b| ;当1 ,、一、.a + b a 一时，汪息到总有 2,1a+bM2<a+lbTa|+g|；故得证;又| y| =|y|，由知，是成立的。接下来回到原题，由结论存在整数C1,C2,，Cn,满足Ga1+c2a2+cnan=1,并且ci <m,n1 Wi Wn .于是，Z ciaix = x,由引理 2 得| xi 1后aiXc Eci HI ai

9、 X 4 ms| ai XI，id因此,i i 1maxiiaix'mni冈maxlaixl 至llxl 之2x综上，总存在存在一个i （1w i工n）,使得aix* 1)Xx 2x占O2 m m 1m m , 1右n >,则在a17a2, ,an中存在两个相邻的正整数。不妨设a17 a2相邻，则2x| =|a2X -a1X| «|a2X| +|a1x| ，故 |a2x| 与 |a1X| 中有一个不小于2016A三、(本题满分50分)给定空间10个点，其中任意四点不在一个平面上。将某些点之间用线段相连，若得到的图形中没有三角形也没有空间四边形，试确定所连线段数目的最大值

10、。解析：以这10个点为顶点，所连线段为边，得到一个10阶简单图G,我们证明G的变数不超过15.设G的顶点为my,，V。一共有k条边，用D(m底示顶点Vi的度。若D(m )M3对i= 1,2,3，101 101 " C "都成立，则k= £ D vi E父10父3=15。2 T2假设存在Vj满足D(vi心4,不妨设D(v1)=n之4,且必与v2，vn41均相邻.于是v2，vn书之间没有边，否则就成三角形，所以V1与V2,，Vn4之间恰有n条边.对每个j (n+2MjM10), Vj至多与V2,，Vn 4中的一个顶点相邻(否则设Vj与Vs, Vt(2 <s &l

11、t;t En+1)相邻，则V1，V2, Vj, Vt就对应了一个空间四边形的四个顶点，这与题意矛(9 一 n，19 n条边，因此G的盾)，从而V2,，Vn由与Vn>2,，V10之间的边数至多10 (n+1) =9 n条。在Vn也，Vn这9-n个顶点之间，由于没有三角形，由托兰定理，至多边数 k <n +(9n) + |(9-nJ=9+，(9-n，k9 + .|251 = 15I 4 - I 4 一 ！4例如如图所示的就有15条边，且满足要求。综上所述，所连线段数目的最大值为15。2014B四、(本题满分50分)设AABC是一个边长为2J3的等边三角形，在&ABC的内部和边界

12、上任取11个点.(1)证明：一定存在两个点，它们之间的距离小于或等于1; (20分)(2)证明：一定存在两个点，它们之间的距离严格小于1; (30分)3证明：(1)如左下图1,我们将AABC分成16个边长为 一的小等边三角形；对于中间的图 2中六2个灰色的小三角形，我们将它们剖分成三个全等的三角形；这样，我们就可以看出AABC就可以被右图3的10个正六边形所覆盖。图1图2图3不难看出，这里的10个正六边形的直径为1,它们可以被看做10只“抽屉”，对于三角形 AABC内 部和边界上任取11个点，根据抽屉原理，至少有一个正六边形包含两个点。而在这个正六边形中，任意两点间的距离不超过 1,这样便证明

13、了我们所要的结论。(要注意，我们的抽屉的构造并不是唯一的，我们还可以用下图4所示的10个直径为1的圆覆盖ABC,也可以得到同样的结论)图4图5(2)这部分要求证明的是严格不等号。我们要证明在11个点中存在两个点， 他们间的距离严格小于 1,注意到直径为1的正六边形中，间距恰好为 1的两个点一定是距离最远的一对点，另一方面，上面所 构造的正六边形抽屉在边和顶点处是由重复的，我们通过指定一条边或者顶点属于那一个特定的正六边形来改造我们的“抽屉”，使得每一个抽屉不包含正六边形中距离为1的顶点对，当然，在目前的情况我们只需关心怎么改造顶点即可。我们在每一个正六边形抽屉上去掉一些顶点，使得每一个抽屉不在

14、包含正六边形中距离为1的顶点对，如图5就是一个办法，图中空心的点表示正六边形中去掉该点，不难看出，这样的改造还是覆盖了原来得三角形 AABC,且每一个抽屉不在包含正六边形中距离为1的顶点对，根据抽屉原理，我们就证明了：任取11个点，一定存在两个点，它们之间的距离严格小于1。（这样的抽屉构造也是不唯一的）2013B四、（本题满分50分）用若干单位小正方形和由三个单位小方格组成的形“砖”铺满-个2 xn的方格棋盘的所有不同可能铺法的数目是Tn.下面的图是n = 3时的两种不同的铺法：EH3求Tio；求T2013的个位数.当n至3时，我们从左向右地铺 2n的方格棋盘，无论哪一种铺法，至多铺到 2M3

15、,我们一定会完成一个2Mk （k =1,2,3,）的矩形。这样我们计算 Tn时，就可以去寻找与Tn,Tn,Tn二的关系，又由下图我们得到=42Tn由 丁1=1,丁2=5,得丁3=11,丁4=33,丁5=87,依次下去可得T10=13377由Tn=Tnj+4Tni+ 2=1,丁2=5,T3=11 ,可知，Tn一定是奇数。我们由mod5计算丁2013,对每一个Tn,我们有：(T1 =1 ,T2 =0,丁3 =1,丁4 =3,丁5 =2 ,T6 =1 ,T7 =0,丁8 =3,T9 =0,T10 =2,T11 =3 ,T12 =1 ,T13= 2 ,Ti4= 2 ,T15= 2 ,T16= 4 ,T

16、17= 1 ,Ti8= 1 ,Ti9= 3 , T20 = 4 ,T21= 3 ,T22= 0 , T23 = 0 ,可知，Tn的个位数的周期是 24。而2013三21 (mod 24 ),又mod5等于3的奇数mod10也一定等于3,所以T2013的个位数为3。2012A三、(本题满分50分)设P0, P, P2|,Pn是平面上n+1个点，它们两两间的距离的最小值为d d(d >0),求证：|BP 由因41比0 A(d)nJ(n+1)! 3 _ d 1证明：证法一：不妨设P0PlMP0P2E MP0Pn.先证明：对任意正整数k,都有F0P；>-Vk+1 3d 显然，P0P, &g

17、t;d >-7k+?又k =1,2,111,8均成立，只有k =8时右边取等号10分所以，只要证明当k之9时，有P0R AdJk即可.3 dd以P(i =0,1,2,|,k)为圆心，d为半径回k十1个圆，它们两两相离或外切；以P0圆心，P0Pk+9为22半径画圆，这个圆覆盖上述k +1个圆 20分30分所以 n( P0R +d)2 >(k +1)n(d)2= P0Pk >d(Vk7M -1)222k 1 -1. k 140分由k之9易知>23一、， d .一 . 所以P°Pk >Jk +1对k之9时也成立.3综上，对任意正整数k都有P0Pk >dJ

18、E.3因而用0用HI P°Pn A(d)nJ(n+1)! 50分3证法二：不妨设RP Wp°用制闫BPn|.d .以P(i =0,1,2,|,k)为圆心，£为半径回k + 1个圆，它们两两相离或外切； 10分2设Q是是圆P上任意一点，由于P0Q Wbp +PQ| = P0P13#pk =#pk20分一，、，3因而，以P0为圆心，- P()Pk为半径的圆覆盖上述个圆 30分2,3,2d 2d . 故冗(2|BR) >(k+1)n(5)= |PoPk >-Vk7M(k=1,2,m,n) 40 分所以 PoPi BP2 -Ill.PoPn. >(d)/

19、(1)! 50分32011A四、(本题满分50分)设A是一个3x9的方格表，在每一个小方格内各填一个正整数. 称 A中的一个mxn (1 Mm M3, 1 Mn M9)方格表为“好矩形”，若它的所有数的和为 10的倍数.称A中的 一个1父1的小方格为“坏格”，若它不包含于任何一个“好矩形” .求A中“坏格”个数的最大值.解析：首先证明A中“坏格”不多于 25个.用反证法.假设结论不成立，则方格表A中至多有1个小方格不是“坏格” .由表格的对称性，不妨假设此时第1行都是“坏格”.设方格表A第i列从上到下填的数依次为 aibi'Ci, i =1,2，9. kk记 Sk =Z ai,Tk =

20、E (bi +g ), k = 0,1,2，9 ,这里 S0 =T0 = 0 . i 1i W我们证明：三组数 S0,S1,，S9； T0,T1,，T9及S0 +T0,S +T1,，S9 十丁9都是模10的完 全剩余系.事实上，假如存在 m, n, 0<m<n<9,使Sm三Sn (mod 10),则nZ ai =Sn -Sm 三0(mod10), i =m 1即第1行的第m+1至第n列组成一个“好矩形”，与第1行都是“坏格”矛盾. n又假如存在 m,n, 0 Wm <n W9 ,使 Tm 三 Tn (mod 10),则 Z (bi +g ) =Tn Tm 三 0(mod

21、 10), i -m 1即第2行至第3行、第m +1列至第n列组成一个“好矩形”，从而至少有2个小方格不是“坏格”， 矛盾.类似地，也不存在 m, n, 0<m<n<9,使 Sm +Tm 三 Sn +Tn(mod 10).因此上述断言得证.故 999£ Sk 三2 Tk 三工(Sk +Tk)三 0+1+ 2+9 三 5(mod10), k =0k =0k =0999所以(S (Sk +Tk)三工 Sk +z Tk 三 5+5 三 0(mod10), k £k =0k R矛盾！故假设不成立，即“坏格”不可能多于25个.另一方面，构造如下一个 3 M 9的方格

22、表，可验证每个不填10的小方格都是“坏格”，此时有25个“坏格”.11121111101111111111111011112综上所述，“坏格”个数的最大值是 25.2011B四、(本题满分50分)给定n个不同实数，其所有全排列组成的集合为An.对于 (ai,a2,|,an)乏An,若恰有两个不同的整数i, j w1,2| ,n 1使彳导ai aai书,aj a aj书成立，则称 该排列为“好排列”.求An中“好排列”的个数.解析：首先定义：对于A中的一个排列(a1,a2，an ),如果满足a1 < a2<<an，则称该排列为自然排列；对于A中的一个排列(a1，a2,，an )

23、,如果有整数i w1,21，n1,使得ai >ai书则称ai和 ai十构成一个“相邻逆序”；对于(“田2,，a。声A ,如果它恰有一个“相邻逆序”，则称该排列为“一阶好排列”，A中所有“一阶好排列”的个数记为力伯)；如果它恰有两个“相邻逆序”，则称该排列为“二阶好排列”，A中所有“二阶好排列”的个数记为f2(n);依题意知，f2(n)恰好是要求的 A中“好排列”的个数。由题意知：f1(1)=0, f1(2)=1, f2(1) = f2(2) = 0 , f2(3)=1。以下为了叙述简便，我们把由给定的k个不同实数的所有全排列构成的集合记为Ak(k =1,2,，n),其次求 fi(n)o我

24、们先来考察f1(k +1)与f1(k)之间的递推关系。对Ak4中的每一个“一阶好排列”(记为a),我们考虑从中取出最大的数 ak中后剩下的k个数ai,a2,，ak按原来的顺序构成的排列(记为 b)。如果排列b是Ak中的“一阶好排列”，且“相邻逆序”为ai >科书，那么，在排列a中，ak卡的位置只能在ai, ai4之间或最后；如果排列b不是Ak中的“一阶好排列”，则排列b中的“相邻逆序”的个数不为 1,显然排列b中“相邻逆序”的个数不能大于 1 (否则，排列a不是“一阶好排列”，理由是：因为ak书是最大的 数，所以排列a中“相邻逆序”的个数一定不少于排列 b中“相邻逆序”的个数)，从而排列

25、b中“相 邻逆序”的个数为0,此时排列b是一个自然排列，而排列 a是“一阶好排列"，所以ak书的位置不 能在最后(有k种可能的位置)。综合上面的分析可知："k+1) =2fl(k)+k ,即 f1(k+1)+(k+1)+1 = 21f1(k)+k + 1，所以 f(n)十n +1 =4 M2n,，即 f1(n) =2n -n -1 °最后求f2(n)。我们先来考察f2(k +1)与f2(k)之间的递推关系。对Ak4中的每一个“二阶好排列”(记为c),我们考虑从中取出最大的数ak由后剩下的k个数a1,a2,，ak按原来的顺序构成的排列(记为 d)。如果排列d是Ak中

26、的“二阶好排列”，且“相邻逆序”为 ai >aH1, aj >aj+，那么在排列c中，ak«的位置只能在ai,ai书之间或aj,aj书之间，或者排在最后；如果排列d不是Ak中的“二阶好排列”，则它一定是 Ak中的“一阶好排列”，设“相邻逆序”为ai >ai+，因为排列c是“二阶好排列"，所以ak +的位置不能在ai,ai书之间，也不能排在最后，其余位置都行，有 k -1种可能。综合上面分析可知：f2(k +1) =3f2(k) + (k -1 )f1(k),又 f1 (n) = 2n -n -1,所以f2(k + 1) =3f2(k) +(k -1 J2k

27、 -k -1),变形为.一一k1 1一 .一k 1f2(k1) (k 2) 2-(k1)(k 2)=3 f2(k)k 1 2 -k(k 1)n 1n 3.nn 1所以 f2(n)+(n+1>2 n(n+1)=27 3,即 fz(n)=3 (n+1) 2 + n(n+1),221.因此An中“好排列”的个数为 3n (n+1) 2n +3门6+1)个。2010A四、（本题满分50分）一种密码锁的密码设置是在正n边形A1A2- L An的每个顶点处赋值 0和1两个数中的一个，同时在每个顶点处染红、蓝两种颜色之一，使得任意相邻的两个顶点的数字或颜 色中至少有一个相同.问：这种密码锁共有多少种不

28、同的密码设置。解析：对于该种密码锁的一种密码设置，如果相邻两个顶点上所赋值的数字不同，在它们所在的边上标上a,如果颜色不同，则标上 b,如果数字和颜色都相同，则标上c.于是对于2定的点 A1上的设置（共有4种），按照边上的字母可以依次确定点A2, A3/H, An上的设置.为了使得最终回到 A1时的设置与初始时相同，标有 a和b的边都是偶数条.所以这种密码锁的所有不同的密码设置方法数等于在边上标记 a, b, c,使得标有a和b的边都是偶数条的方法数的 4倍.设标有a的边有2i条，0勺E 8,标有b的边有2 j条，0 E j E ,口自L选取2i条边标,2一 2记a的有C；中方法，在余下的边中

29、取出2 j条边标记b的有C；匕种方法，其余的边标记c.由乘法原理，此时共有 C2i C：匕种标记方法.对i, j求和，密码锁的所有不同的密码设置方法数为这里我们约定C0）=1.当n为奇数时,n -2i >0 ,此时j =02n 2 1n3代入式中，得4Vi -0=2C：i2nNi-0n=、：C：2n”k On八 Cnk2n*(-1)k =(2 1)n (2 -1)nk =0=3n +1 .当n为偶数时，若i <n,则式仍然成立；若i =口，则正n边形的所有边都标记 a,此时 22只有一种标记方法.于是，当 n为偶数时，所有不同的密码设置的方法数为f2门 、J 2j21Cni1CCn

30、_2i= 4 M1+U (C212n= 2+4£ (C；*-)=3n+3j=0i=0Li =0综上所述，这种密码锁的所有不同的密码设置方法数是：当n为奇数时有3n十1种；当n为偶数时有3n +3种.xnX12X13X14X15X16X17X18X19p =X21X22X23X24X25X26X27X28X29kX31X32X33X34X35X36X37X38X39 ,2009*四、（本题满分50分）在非负数构成的 3M 9数表中每行的数互不相同,前6列中每列的三数之和为1,X11X12X13均大于1。如果P的前二列构成的数表S =X21X22X23满足如下性质（O）：对于数表P中任1

31、X31X32X33 )X17 = X28 = X39 = 0 ,X27 , X37 , X18 , X38 , X19 , X29X1k意一列X2k( k =1,2，9)均存在某个i w 4,2,3使得 X1k E Ui = mn <Xi1,Xi2, X13L 求证:,<X3k )最小值Ui =min xi1,Xi2,X131, i =1,2,3一定来自数表S的不同歹U；z 、X1k*（ 、X11X12xk 冲存在数表P中唯一的一列X2k*,k* #1,2,3，使得 3x3数表 S* =x21x22x2k”仍然具有F3k*jX31x32X3k冲,性质（O）。则存在一列不含证明：（i

32、）假设最小值ui =min xi1,xi2，xi3, i =1,2,3不是取自数表S的不同歹U。 3313"任何ui .不妨设j =xi2,i =1,2,3.由于数表P中同一行中的任何两个元素都不等，于是 ui <xi2,i =1,2,3.另一方面，由于数表 S具有性质（0）,在（3）中取k=2,则存在某个i0 1,2,3 使得xi02 < Ui0 .矛盾。（ii）由抽屉原理知 min x11, x12, min x21, x22, min x31,x32中至少有两个值取在同一列。不妨设 min x21,x22 = x22 ,min x31,x32 =x32.由前面的结论

33、知数表S的第一列一定含有某个ui ,所以只能是x11 =u1.同样，第二列中也必含某个x11 x12 xl3ui ,i=1,2.不妨设x22=u2 .于是u3=x33,即ui是数表S中的对角线上数字：S=x21x22加3*31 x32 x33 , 记“=1, 2,，9,令集合 I =kM |xik >min xi1,xi2, i =1,3显然 I =k W M |x1k >xn,x3k >x32且 1,2,3 更 I .因为 x18,x38 >1 >x11,x32 ,所以 8三 I .故 I #9 .于是存在 k* W I 使得 x2k* =maX x2k | k

34、 w I.显然，k* #1,2,3.fIXii Xi2 x1k，下面证明3M3数表S'= X21 X22 x» 具有性质（0）. 2k931 X32 X3k- J. , . , . . , -，一 , 从上面的选法可知 ui := minxi1,xi2,xik* =minxi1,xi2, （i =1,3）.这说明x1k*min Xii,Xi2 w,x3k min X31, X32用又由 S 满足性质（。），在（3）中取 k = k ,推得 x2k* < u2，于是 u2 = minx21,x22,x2k* = x2k.下证对任意的k w M ,存在某个i =1,2,3使

35、得ui'之xik .假若不然，则xik > min xi1,xi2, i = 1,3且x2k A x2k这与x2k*的最大性矛盾。因此，数表 S'满足性质（。）。下证唯一性。设有k£ M使得数表S, S?= x21x22x2k<x31x33x3k J具有性质（O ）.不失一般性，我们假定u1 = min x11, x12, x13 = x11（ 4 ）u2 =min X21, X22, X23 =X22,用=min X3i,X32,X33 =X33。X32 < X31由于 x32 Hx31 ,x22 Mx21 ,及（i ）,有 u? =min x11

36、,x12,x1k =x11.又由（i）知：或者（a）区=min X31, X32, X3k =X3k ,或者（b）u?2 =min X21，X22,X2k =x?k.如果(a)成立，由数表§具有性质(0),则U1 = min x11,x12,x1k = x11,(5)U2 =min x2i,x22,x2k =x22,乌=min x31，x32,x3k = x3k由数表§满足性质(0),则对于3w M至少存在一个i w 1,2,3使彳导u?i之xi3 ,又由(4), 式 知，UE,= x11<x13,U2=x22cx23.所以只能有U?3=x3k之x33.同样由数表S满

37、足性质(。)，可推得x33之x3k.于是k = 3 ,即数表S = § 如果(b) 成立， 则 U1 = min x11,x12,x1k = x11 , U1 = min x11,x12,x1k = x11 , ( 6 ) u2 = minx21 , x22 , x2k =x2k，u3=minx31 ,x32 , x3k =x32由数表§满足性质(0),对于k* w M ,存在某个i =1,2,3使得U? >xik* ,ik由 k U I 及(4)和(6)式知，x,*>x11= I?,x,.*>x32=l?3.1 k3k于是只能有x2k* <Ui2

38、=x2k.类似地，由S'满足性质(。)及kw M可推得x2k < u2 = x2k* ,从而.*.k =k。2007*二、(本题满分40分)。如图所示，在7 M 8的长方形棋盘的每个小方格的中心点各放一个棋子。如果两个棋子所在的小方格共边或者共顶点，那么称这两个棋子相连。现从这56个棋子中取出一些，使得棋盘上剩下的棋子，没有五个在一条直线(横竖斜方向)上依次相连。问最少取出多少个棋子 才能满足要求？并说明理由。解析：1 23456 171gl解：最少要取出11个棋子，才可能满足要求。其原因如下：1如果一个方格在第i行第j歹U,则记这个方格为(i, j)o2二第一步证明若任取 10

39、个棋子，则余下的棋子必有一个五子连3珠，即五个棋子在一条直线(横、竖、斜方向)上依次相连。用反证法。假设可取出10个棋子，使余下的棋子没有一个五子连珠。如图1,在每一行的前五格中必须各取出一个棋子，5后三列的前五格中也必须各取出一个棋子。这样，10个被取8出的棋子不会分布在右下角的阴影部分。同理，由对称性，也7不会分布在其他角上的阴影部分。第1、2行必在每行取出一个，且只能分布在(1, 4)、(1 , 5)、(2, 4)、(2, 5)这些方格。同理I E 一 一 了扑(6, 4)、(6, 5)、(7, 4)、(7, 5)这些方格上至少要取出 2个棋子。 1 口 | | | | | |在第1、2

40、、3歹U,每列至少要取出一个棋子，分布在(3, 1)、？二(3, 2)、(3,3)、(4,1)、(4, 2)、(4, 3)、(5, 1)、(5,2)、(5,3)3二所在区域，同理(3, 6)、(3, 7)、(3, 8)、(4, 6)、(4, 7)、(4, 8)、 -I(5, 6)、(5,7)、(5,8)所在区域内至少取出3个棋子。这样，在这些$二区域内至少已取出了10个棋子。6二因此，在中心阴影区域内不能取出棋子。由于、这4个| | | | | | | 一棋子至多被取出2个，从而，从斜的方向看必有五子连珠了。矛盾。第二步构造一种取法，共取走11个棋子，余下的棋子没有五子连珠。如图2,只要取出有

41、标号位置的棋子，则余下的棋子不可能五子连珠。综上所述，最少要取走 11个棋子，才可能使得余下的棋子没有五子连珠。2005*12、如果自然数a的各位数字之和等于 7,那么称a为“吉祥数”.将所有吉祥数从小到大排成一歹U a1,a2,a3，若 an =2005,则 a5n =答案:5200解析：因为方程 为+x2 +xk = m的非负整数解的个数为 Cm4k，而使x1 > 1, xi > 0 (i父2 ) 的整数解个数为cm；,。现取m = 7,可知，k位吉祥数的个数为p(k)=C；45因为2005是形如2abc的数中最小的一个吉祥数，且 p(1) = 1 , p(2) = 7 , p

42、(3) = 28 ,对四位吉祥数崩，其个数为满足 a+ b + c =6的非负整数解的个数，即 C：书=28个。 6 3又 2005是第 1 +7 +28+28 +1=65个吉祥数，即 a66 = 2005 ,从而 n = 65, 5n = 325。又 p(4) =84 , p(5) =210 ,而 p(1) + p(2) + p(3) + p(4) + p(5) =330所以从大到小最后六个五位吉祥数依次是70000,61000,60100,60010,60001,52000 ,所以第325个吉祥数是52000,即a5n = 520002003*三、(本题满分 50分)。由n个点和这些点之间

43、的l条连线段组成一个空间图形，其中212n =q +q+1 , l之一q(q+1) +1, q之2, q N。已知此图中任四点不共面，每点至少有一条2连线段，存在一点至少有q+2条连线段.证明：图中必存在一个空间四边形 (即由四点A,B,C,D和 四条连线段 AB,BC,CD,DA组成的图形).证明：证明：设点集为V =与，儿,，A1,与A连线的点集为Bi,且Bi.于是1 Wb Wn 1 .又n 4显然有 Z bi =2| >q(q+1 2 +2 i f若存在一点与其余点都连线，不妨设b0 =n -1.122则 B0 中 n-1 个点的连线数 l-b0q(q+1)+1-(n-lW q(q

44、+>q " = 1)1 1n -1.=一(q +1 jfn -1 )+1 -(n -1 )=- (q -1 fn -1 )+1 至+1 .(由 q ' 2)2 22但若在这n-1个点内，没有任一点同时与其余两点连线，则这n-1个点内至多连线|上11条,一 2故在Bo中存在一点A,它与两点Aj、Ak（i, j,k互不相等，且i,j,k至1）连了线，于是庆。人，入，入 连成四边形.现设任一点连的线数 En-2 .且设bo=q+2wn-2.且设图中没有四边形.于是当 i¥ j时,Bi与 Bj 没有公共的点对，即BinBjM1( 0 <i, j <n-1)

45、.记 B0=VB0,则由BiPlB。M1,得 Bi riBo >bi -1( i =1,2,，n1),且当 1 W, j Wn1 且i / j 时，Bi B0 与 Bj B0 无公共点n-1对.从而 丽中点对个数z （Bi nBo中点对个数）.即i 1n 1n 11”二110/20VIC2耳 迂 C|Bi耳I 迂 C；二1£ to2 -3bi +2)>- I Z (bi ) -3Z C )+2(n-1i mi m2i 工21n1i三yyj(由平均不等式) 2l - bo - 3 2l _ bo2 n _ 1 J2 Ln -1= 1.1(2l -bo 2 -3(n -1 2

46、1 -bo )+2(n-1 f12 Un -1=1(21 bo n +1121 bo 2n+2)(注意 21 2 q(q +1 2 +2 = (n 1 Kq+1 计2),2 n -121即得到 C：4 之n1L+2bo ( n1(q1 十2 bo (两边同乘以 2(n-1)°2 n -1即(n -boJn -1 -bo户«n-1 q +2 -boj(n-1Jq- 1 )+2bo)(注意到 n -1 2q(q +1得 q(q+1In 一仇In-1 -bo上(nq-q +2 -bo Inq -n +3-bo).(各取部分因数比较)又 nq n3 boq n T-bo= q 7b

47、o_n 3 _ q_1q 2 V-n 3 =q2q 1 n = o2(这里用到刖面所得到的式子bo2q+2, q(q+1)=q +q = n1)In -1 q 2 -b0 I - q 1 n - b0 =qb0 -q-n 2.qq 2 -q-n 2=q2 q-n 2=1 0(这里也用到前面所得到的式子b0之q+2, q(q+1 )= q2 + q = n 一1)又(nqn+3bo (nqq+2 bo 卜 q(n-1 bo )、(q+1'。b0 )均为正整数,从而由、得， q(q +1 jn -b0 (n -1 -b0 )<(nq -q +2 -b0 jnq -n +3 b0 )

48、由、矛盾，知原命题成立.又证：画一个nxn表格，记题中n个点为A1, A2； An ,若A与Aj连了线，则将表格中第i行j列的方格中心涂红. 于是表中共有21个红点，当d(A )=m时，则表格中的i行及i列各有m个红 点.且表格的主对角线上的方格中心都没有涂红.由已知，表格中必有一行有 q+2个红点.不妨设最后一行前 q+2格为红点.其余格则不为红点(若有红点则更易证)，于是：问题转化为：证明存在四个红点是一个边平行于格线的矩形顶点.若否，则表格中任何四个红点其中心都不是一个边平行于格线的矩形顶点.于是，前n-1行的前q +2个方格中，每行至多有1个红点.去掉表格的第 n行及前q + 2歹U,

49、则至多去掉22q+2+(n-1) =q+2+q +q=(q+1) +1个红点.于是在余下(n1)(nq-2)万格表中，至少有21 一(q +1)2 -1 =q(q +1)2 +2 -(q +1)2 -1 = q3 +q2 q 个红点.n-1设此表格中第i行有mi(i =1,2,，n-1)个红点，于是，同行的红点点对数的总和为 £ Cli .其 id中q2+q=n1.(由于当nk时，C2+C2<C2书+CiL1 ,故当红点总数为q3+q2q个时，可n 1取q2行每彳T取q个红点，q行每彳T取q-1个红点时C Cli取最小值，由下证可知红点数多于此数 i 1n -1时更有利于证明.

50、)，但q2C2 +qC' <Z Cmi . i 1由假设，不存在处在不同行的 2个红点对，使此四点两两同列，所以，有(由于去掉了 q + 2列，故还余q2 -1列，不同的列对数为 C22 .)q 1'n 二即 Z cm <C22 1 ，所以 q2 q(q -1) +q(q -1)(q-2) <(q2 -1 '(q2 一2 ). iq - Ii 1即 q(q -1)(q2 q -2) < q -1 q 1 q2 -2即q3 +q2 2q <q3 +q2 -2q 一2显然矛盾.故证.2001*三、(本题满分50分)将边长为正整数 m, n的矩形

51、划分成若干边长均为正整数的正方形.每个正方形的边均平行于矩形的相应边.试求这些正方形边长之和的最小值.解析：记所求最小值为f(m,n),我们可以证明 f (m, n) = m+n (m,n). (*)D1A mA1 B其中(m,n)表示m和n的最大公约数.事实上，不妨设 m之n,(1)关于m归纳，可以证明存在一合乎题意的分法，使所得正 方形边长之和恰为 m + n -(m,n).当m =1时，命题显然成立.假设当m Mk时，结论成立(k之1).当m = k+1时，若 n=k+1,则命题显然成立.若 n<k+1,从矩形ABCD中切去正方形 AA1D1D (如图)，由归纳m A1 Ba1 ,

52、a2,，ap ,不妨设假设矢I形A1BCD1有一种分法使得所得正方形边长之和恰为m -n + n -(m, n) = m -(m,n).于是原矩形ABCD有一种分法使得所得正方形边长之和为m + n-(m,n)oD(2)关于m归纳可以证明(*)成立.当 m =1 时，由于 n =1,显然 f (m, n) =1 = m +n -(m, n) .A假设当 mW k 时，对任意 1WnWm有f(m, n)= m+n-(m, n).若m = k+1,当门=卜+1 时显然 f (m,n) = k+1 = m + n(m, n).当1 E n E k时，设矩形ABCD按要求分成了 p个正方形，其边长分别

53、为a1之a2主2ap 显然a1 = n或a1 < n .若21 <n ,则在AD与BC之间的与AD平行的任一直线至少穿过二个分成的正方形(或其边界),于是a1 +a2 +ap不小于AB与CD之和.所以a1 + a2 + ap之2M > m + n - (m,n),a2,，ap的正方若a1 = n ,则一个边长分别为 m - n和n的矩形可按题目要求分成边长分别为形，由归纳假设 a2 +ao 之 m n+n(m，n) = m(m，n)。pp从而 a1 +a2 +ap 之 m + n (m,n).于是当 m = k+1 时，f (m, n)之 m + n _(m, n).再由 可

54、知 f (m,n) = m + n (m, n)。1997*三、(本题满分50分)在100x25的长方形表格中每一格填入一个非负实数，第 i行第j列中填入的数为xij ( i =1,2，100, j =1,2,25)如表1,然后将表1每列中的数按从小到大的次序从上到下重新排列为x1/,j >x2,j之至x/00,j ( j =1,2，25)。如表2。求最小的自然数k,使得只2525要表1中填入的数满足工x,j <1 (i =1,2,100),则当i之k时，在表2中就能保证Z x/,j <1 oj 1'再再,2福珞 -V 近3&餐惇<A « 而曲】 -V 解析：在表1 中，取x4iJ3,i=x4i_2,i=x4i,i0.Vl,2444或1V&E« A wX2,36 a a寺 y UMr!« A w/1帆381= x4i,i =0( i =1,2，25),其余各数均取 一，25是，每列各数之和均等于 1 .但重新填入后，前96行之和均等于-5 >1 .第97,98,99,100行之和24反之，如果表2中第9