1981年~2019年全国高中数学联赛试题分类汇编（15）组合与构造（含答案）

1981年~2019年全国高中数学联赛试题分类汇编

组合与构造部分

2019A四、(本题满分50分)

设V是空间中2019个点构成的集合，其中任意四点不共面.某些点之间连

有线段，记E为这些线段构成的集合.试求最小的正整数〃，满足条件：若E至

少有拉个元素，则E一定含有908个二元子集，其中每个二元子集中的两条线

段有公共端点，且任意两个二元子集的交为空集.

★解析：为了叙述方便，称一个图中的两条相邻的边构成一个“角”.

先证明一个引理：设G=(V,E)是一个简单图，且G是连通的，则G含有个两两无公

共边的角(这里［可表示实数。的整数部分).

引理的证明：对的元素个数国归纳证明.当|同=0,1,2,3时，结论显然成|立.下面假设，并

且结论在较小时均成立.只需证明，在G中可以选取两条边。力构成一个角，在G中删去。力

这两条边后，剩下的图含有一个连通分支包含|目-2条边.对这个连通分支应用归纳假设即

得结论成立.

考虑G中的最长路尸：匕叫…为，其中匕彩…也是互不相同的顶点.因为G连通，故左23.

情形1：deg(%)»2,由于p是最长路，耳的邻点均在岭…匕中，设％斗€后，其中

3<i<k.则｛用为，匕匕｝是一个角，在E中删去这两条边.若匕处还有第三条边，则剩下的

图是连通的：若匕处仅有被删去的两条边，则匕成为孤立点，其余顶点仍互相连通.总之在

剩下的图中有一个连通分支含有|国-2条边.

情形2：deg(Vj)=l,degM)=2.则｛、3，%%｝是一个角，在G中删去这两条边后，匕,彩

都成为孤立点，其余的点互相连通，因此有一个连通分支含有|目-2条边.

情形3：deg(匕)=1,deg(v2)>3,且％与匕…4中某个点相邻.则｛匕%，为匕｝是一个角，

在G中删去这两条边后，匕成为孤立点，其余点互相连通，因此有一个连通分支含有|目-2

条边.

情形4：deg(yj=l,deg(v2)>3,且为与某个〃史｛用，匕,…以｝相邻.由于P是最长路，

故”的邻点均在打…以之中.因｛巧巧，岭〃｝是一个角，在G中删去这两条边，则匕是孤立

点.若“处仅有边〃彩，则删去所述边后〃也是孤立点，而其余点互相连通.若“处还有其他

边"斗，3<i<k,则删去所述边后，除匕外其余点互相连通.总之，剩下的图中有一个连通

分支含有|目一2.

引理获证............20分

回到原题，题中的V和£可看作一个图G(V,E).

首先证明2795.

设V=｛H，%，…/在匕，彩，…，为中，首先两两连边，再删去其中15条边(例如

｛用为，W匕…M%｝)，共连了T5=1815条边，则这61个点构成的图是连通图.再将剩

余的2019-61=1958个点配成979对，每对两点之间连一条边，则图G中一共连了

1815+979=2794条线段.由上述构造可见，G中的任何一个角必须使用岭，…，之相连

的边，因此至多有一厂=907个两两无公共边的角.故满足要求的〃不小于2795.……

30分

另一方面，若|目22795,可任意删去若干条边，只考虑忸|=2795的情形.

设G有攵个连通分支，分别有町,，々，…，町i个点，及4,«2,…,e*条边.下面证明q,02,…，线

中至多有979个奇数.

反证法，假设6,02,…,q中有至少980个奇数，由于4+62+…+q=2795是奇数，故

G，02,…,e*中至少有981个奇数，故攵2981.不妨设q,e2,…,0网都是奇数，显然

仍+ITL,d---F/My8|>2.

令机=町+m2+…+/22,则有2，（lWi<980）,第20981+0980+…+线，

k980

故2795=»>,.<C；+£C\,利用组合数的凸性，即对xNyN3,有C；+C；<C；+l+。

i=li=l

980

可知当犯，加2,…，砥80,机由980个2以及一个59构成时，+取得最大值.于是

/=1

980

27954C；+ZG；W（4+980。；=2691<2795,这与①矛盾.从而4勺,…9中至多有

/=1

979个奇数....40分

对每个连通分支应用引理，可知G中含有N个两两无公共边的角，其中

我「口1（A1

N=Z上>--979=-（2795-979）=908o

|=|L2J21,•=]J2

综上,所求最小的〃是2795.……50分

2019B四、（本题满分50分）

将一个凸2019边形的每条边任意染为红、黄、蓝三种颜色之一，每种颜色的边各

673条.证明：可作这个凸2019边形的2016条在内部互不相交的对角线将其剖分

成2017个三角形，并将所作的每条对角线也染为红、黄、蓝三种颜色之一，使得

每个三角形的三条边或者颜色全部相同，或者颜色互不相同.

★证明：我们对〃25归纳证明加强的命题：如果将凸〃边形的边染为三种颜色

a,b,c,并且三种颜色的边均至少有一条，那么可作满足要求的三角形剖

分.........10分

当“=5时，若三种颜色的边数为1,1,3,由对称性，只需考虑如下两种情形,

分别可作图中所示的三角形剖分.

若三种颜色的边数为1,2,2,由对称性，只需考虑如下三种情形，分别可

作图中所示的三角形剖分.

假设结论对〃（〃25）成立，考虑〃+1的情形，将凸〃+1边形记为44…Aw

情形1：有两种颜色的边各只有一条.不妨设4/色边各只有一条.由于〃+126,

故存在连续两条边均为C色，不妨设是4A川，4+同.作对角线44,并将44染

为c色，则三角形44MA的三边全部同色.此时凸〃边形KA?…4的三种颜色的

边均至少有一条，由归纳假设，可对其作符合要求的三角形剖分.............

30分

情形2：某种颜色的边只有一条，其余颜色的边均至少两条.不妨设。色边只有一

条，于是可以选择两条相邻边均不是〃色，不妨A/U”4川4设均不是。色，作对

角线AA,，则A4有唯一的染色方式，使得三角形A.A“+M的三边全部同色或互不

同色.此时凸〃边形A4…4的三种颜色的边均至少有一条，由归纳假设，可对

其作符合要求的三角形剖分.............40分

情形3：每种颜色的边均至少两条.作对角线44,则AA,有唯一的染色方式，

使得三角形A,A,+IA的三边全部同色或互不同色.此时凸〃边形44…A,的三种颜

色的边均至少有一条，由归纳假设，可对其作符合要求的三角形剖分.

综合以上3种情形，可知〃+1的情形下结论也成立.

由数学归纳法，结论获证.............50分

2017A三、（本题满分50分）将33x33方格纸中每个小方格染三种颜色之一，使得每种颜色

的小方格的个数相等。若相邻两个小方格的颜色不同，则称他们的公共边为“分割边”。试求

分割边条数的最小值。

★解析：记分割边的条数为L.首先，将方格纸按如图所示分成三

个区域，分别染成三种颜色，粗线上均为分割边，此时共有56条

分割边，即乙=56。

下面证明L256.

将方格纸的行从上至下依次记为A，A”…,A33,列从左至右依次记为

%，行A,中方格出现的颜色数记为〃（4），

列为中方格出现的颜色数记为〃(与)，三种颜色分别记为q,”,c3,

对于一种颜色的，设〃(cj是表示含有与色方格的函数与列数之和.

记以c)」1，4中含有0色方格

只"一10,A,中不含j色方格’

卷中含有色方格

问理定乂87,，Cj)X=[]o1,与中不含C6j色方格’

则E(〃(4)+〃(坊))=££*,j)+血,J))=££旗A，Cj)+细,，S))=E〃(cj)①

/=1/=1j=\j=\i=\j=\

1i

由于染%色的方格有±x33?=363个，设含有C/色方格的行有4个，列有匕个，则与色方格

1377

一定在这。行和h列的交叉方格中，因止匕2363.从而“(q)=a+/?22yfab>27363>38

即”(c,)239J=1,2,3,…②

由于在行4中有“(4)种颜色的方格，因此至少有“(4)-1条分割边，同理在行月中有“(g)

种颜色的方格，因此至少有〃(8)-1条分割边，于是，

3333333/、

(〃(4)-1)+X("⑻T)2£(〃(4)+〃(Bj)-66=Z〃(J)-66③

i=l/=1i=l；=1

下面分两种情形讨论.

⑴当有一行或有一列全部方格同色时，不妨设有一行全为q色，从而方格纸的33列中均含有

G的方格，由于。的方格有363个，故至少有11行中含有q色方格。于是〃(q)N11+33=44。

④

由®®④得L>n(c,)+n(c2)+n(c3)-66>44+39+39-66=56

⑵没有一行或没有一列全部方格同色时，则对任意14iW33,均有〃(4)22,»(/?,)>2,

33

从而由②知，L>£(«(A)+))-66>33X4-66>56

/=i

综上可知，分割边条数的最小值为56。

2017A四、(本题满分50分)。设〃均是大于1的整数，m>n,q,%，…，4是〃个不超

过加的互不相同的正整数，且q,外，…，4互素。证明：对任意实数工，均存在一个i

(l<z<n),使得||。对4嬴3石同，这里帆表示实数y到它最近的整数的距离。

★证明：首先证明两个引理：

引理1：存在整数。,。2,…,c.,满足jq+c2a2+…+c.a“=1,并且|q|w〃z,\<i<n.

由于互素，即(%,生，…，a”)=l，有裴蜀定理，存在整数,满足

G4+。24+…+ga“=1。①

下面证明，通过调整，存在一组q,Q，…,g满足①，且同W"，记与(C：,。2,c,J=Zq>0,

cf>m

S,(C,,C2,•••,€„)=X同2。。

Cj<-tn

如果S|>0,那么存在q>根>1,于是。©>1,又q,“2,4是大于1的整数，故由①

可知，存在Cj<0,令。=q-%,Cy=Cj+ai,c'k=ck(\<k<n,则

c[ax+c!,a2+•••+c'nan=1,②并且0Wm-%Wc；<q,cy<c^-<ak<m.

所以S](G，S](C],C2,S2((?1,,C2，---,cJ<S2(G，C2,…,C”)

!

如果S2>0,则存在Cj<一机，因此有一个c,>0.令c；=q,cj=Cj+a；,c'k=ck

(\<k<n,k手i,j),那么②成立，并且一加<c；VC"<c；<0,与上面类似可以证明

到：SI(c；,备，…,c；)<S](c、|,C2,…,c“)，S2"弓，…,c：)<S2(C],C2,…,g),即说明S1与

S2均是非负整数，故通过有限次上述的调整，可以得到一组使得①成立，并且$=邑=。结

论获证。

引理2：①对任意的实数a,/?,均有||。+4闫同+/|；②对任意整数〃和实数y,有

由于对任意整数“和实数x,均有仙+.引用于是不妨设a,"ei,此时|司=时，

|例第，若ab<0,不妨设a<0<b,则a+be,从而

|。+同=k+44时+W=I4+N

若a匕>0,不妨设a,b同号，则当a+匕4,时，有a+Ae,

222

此时|,+邳=,+母=时+曰=|同+例；当时+网>^时，注意到总有|a+训故

珊+/I；故①得证;

又卜M=IM，由①知，②是成立的。

接下来回到原题，由结论①存在整数q,C2,…,c,，满足…+c,G=l，并且

同Wo?,iWiW〃.于是,2cM/=x,由引理2得国=＜旧琲国〈磋MN,

i=lII/=1/=1||/=!

因此，野轲的仁国③

若〃《%±1,贝岫③知，max||a,.x||>—||x||A

2区区〃mnm[m+1)

in+1

若〃则在a”的，％中存在两个相邻的正整数。不妨设囚,。2相邻，则

同引“2可|+|何4故随闻与|喇|中有一个不小于¥2

/fI\ffLIxf

综上，总存在存在一个i(IWiW"),使得|。国归泓；+]阿

2016A三、(本题满分50分)给定空间10个点，其中任意四点不在一个平面上。将某些点之

间用线段相连，若得到的图形中没有三角形也没有空间四边形，试确定所连线段数目的最大

值。

★解析：以这10个点为顶点，所连线段为边，得到一个10阶简单图G,下证明G的变数不

超过15.

设G的顶点为匕，匕，…,％o,一共有2条边，用。（匕）表示顶点匕的度。若。（匕）43对

1101

i=l,2,3,…,10都成立，则％=—匕）4—*10x3=15。

假设存在匕满足。（匕）24,不妨设0（%）=〃24,且匕与功,v„+1均相邻.于是匕，…,vn+1

之间没有边，否则就成三角形，所以匕与匕，…加日之间恰有〃条边.

对每个/（n+2<j<10）,匕至多与岭，…，乙+i中的一个顶点相邻（否则设匕与匕，v,

（+l）相邻，则匕，v2,Vj,匕就对应了一个空间四边形的四个顶点，这与

题意矛盾），从而匕，…,V.与匕,+2,…,%之间的边数至多10—（〃+1）=9—〃条。

「（9-〃丫］

在乙+2,…，乙这9一〃个顶点之间，由于没有三角形，由托兰定理，至多,4条边，因

（9—〃）2（9）2

此G的边数女<〃+（9-〃）+=9+，二L

44

例如如图所示的就有15条边，且满足要求。

综上所述，所连线段数目的最大值为15。

2014B四、（本题满分50分）设AABC是一个边长为2百的等边三角形，在A46C的内部和

边界上任取11个点.

（1）证明：一定存在两个点，它们之间的距离小于或等于1；（20分）

（2）证明：一定存在两个点，它们之间的距离严格小于1；（30分）

n

★证明：（1）如左下图1,我们将A46C分成16个边长为巨的小等边三角形；对于中间的图

2

2中六个灰色的小三角形，我们将它们剖分成三个全等的三角形;这样，我们就可以看出MBC

就可以被右图3的10个正六边形所覆盖。

图1图2图3

不难看出，这里的10个正六边形的直径为1,它们可以被看做10只“抽屉”，对于三角形A48C

内部和边界上任取11个点，根据抽屉原理，至少有一个正六边形包含两个点。而在这个正六

边形中，任意两点间的距离不超过1,这样便证明了我们所要的结论。

（要注意，我们的抽屉的构造并不是唯一的，我们还可以用下图4所示的10个直径为1的圆覆

盖AABC,也可以得到同样的结论）

（2）这部分要求证明的是严格不等号。我们要证明在11个点中存在两个点，他们间的距离严格

小于1,注意到直径为1的正六边形中，间距恰好为1的两个点一定是距离最远的一对点，另一

方面，上面所构造的正六边形抽屉在边和顶点处是由重复的，我们通过指定一条边或者顶点

属于那一个特定的正六边形来改造我们的“抽屉”，使得每一个抽屉不包含正六边形中距离为

1的顶点对，当然，在目前的情况我们只需关心怎么改造顶点即可。

我们在每一个正六边形抽屉上去掉一些顶点，使得每一个抽屉不在包含正六边形中距离为1的

顶点对，如图5就是一个办法，图中空心的点表示正六边形中去掉该点，不难看出，这样的

改造还是覆盖了原来得三角形AA3C,且每一个抽屉不在包含正六边形中距离为1的顶点对，

根据抽屉原理，我们就证明了：任取11个点，一定存在两个点，它们之间的距离严格小于1。

（这样的抽屉构造也是不唯一的）

2013B四、（本题满分50分）用若干单位小正方形和由三个单位小方格组成的形“砖”

铺满一个2x〃的方格棋盘的所有不同可能铺法的数目是.下面的图是〃=3时的两种不同

的铺法：

⑴求10;

⑵求4)”的个位数.

★证明：由题意显然7；=1,n=5,

的关系，又由下图

⑴由(=1,4=5,得7；=11,看=33,7；=87,依次下去可得加=13377

⑵由7；=T“_i+4T„_2+2(L3,I=1，T2=5,7；=11,可知，7；一定是奇数。我们由mod5

计算/013,对每一个了“，我们有：

\,T2,T3=1,TA=3,T5=2,Tb=1,T7=0,TS=3,Tg=0,TW=2=3,

名三1,后三2,0三2,九三2,n6三4,弓三1,0三1，19三3,720三4,与三3,弓三0,

^23三。，54三1，)/5=1，726三。,47三1,728三3,T29三2,7^0=1,,,,

可知，7；的个位数的周期是24。而2013三21(irod24),又mod5等于3的奇数modlO也

一定等于3,所以T2013的个位数为3。

2012A三、(本题满分50分)设鸟，…,匕是平面上〃+1个点，它们两两间的距离的最

小值为d(">0),求证：出出卜/闾…花刃>日)”(〃+1)!

★证明：证法一：不妨设区用W山闾〈…〈山制•先证明：对任意正整数左，都有

显然，|《川2d之《4k+\对％=1,2,…,8均成立,只有4=8时右边取等号……10分

所以，只要证明当左》9时，有闱即可.

以月(i=0,l,2,…，幻为圆心，!为半径画《+1个圆，它们两两相离或外切；以《圆心，

归闾+g为半径画圆，这个圆覆盖上述k+1个圆.............20分

所以匐外刃+§2>(%+1)哈2口忱间>g(VTFT-1).............30分

,,k+\—1yjk+\.

由上29易知--------->....................................40分

23

所以由闾>g仄门对左29时也成立・

综上,对任意正整数%都有|外引〉[/匚口.

因而贴卜|此闾…M刃>(夕’(〃+1)!........................50分

证法二：不妨设|用用闾<…W同间.

以4。=0,1,2,…，幻为圆心，g■为半径画k+1个圆，它们两两相离或外切；……10分

设。是是圆？上任意一点，由于

|4。|〈山田|+山。|=|4用+因闱+g后闱=|图闱....................20分

因而，以尼为圆心，#间为半径的圆覆盖上述个圆.................30分

故乃右山间)2>(女+1)乃仁了=>|^|>-=1,2,…,〃)..................40分

所以|此用M用…M用>(])"而诃......................50分

2011A三、(本题满分50分)设a”的，%(〃24)是给定的正实数，q<a2<--<an.对

a：-a：

任意正实数「，满足一一L=r(1<z</<左4〃)的三元数组(i,J,%)的个数记为了,,").

〃2

证明：/„(r)<—,

4

a：-a-

★证明：对给定的/(I</<〃)，满足lWi<，<攵且」一^=八①的三元数组

ak-aj

的个数记为g/⑺.注意到，若i,j固定，则显然至多有一个k使得①成立.因i</,口叮有/-1

种选法，故gj(r)4/-l.

同样地，若，左固定，则至多有一个i使得①成立.因人>/,即左有〃一/种选法，故

g.{r)<n-j.从而均⑺•

‘一!少一!2w-i

因此，当”为偶数时，设〃=2/n,则有/“0)=〉28/(，)=28/(7)+£8)(「)

j=2j=2j=m

2

.V，.v'zo、rn(m-l)22n

<Z(J-1)+2/2加一/)=-------+--------=m-m<m=—.

j=2j=nt+\224

〃一1〃J

当〃为奇数时，设"=2加+1,则有力（r）=Zgj（r）=Zgj（r）+Eg,。）

j=2j=2j=m+\

f"2〃J〃2

«Z（/T）+Z（2，〃+l-/）=m2<--.

j=2j=in+\4

n2

综上所述，/„（r）<y.

2011A四、(本题满分50分)设A是一个3x9的方格表，在每一个小方格内各填一个正整数.称

A中的一个"?x〃(l±〃V3,1V/2V9)方格表为“好矩形”，若它的所有数的和为10的倍数.称A

中的一个1x1的小方格为“坏格”，若它不包含于任何一个“好矩形”.求A中“坏格”个数的

最大值.

★解析：首先证明A中“坏格”不多于25个.

用反证法.假设结论不成立，则方格表A中至多有1个小方格不是“坏格”.由表格的对称性,

不妨假设此时第1行都是“坏格”.

设方格表A第i列从上到下填的数依次为％,d,c,.,z=L2,…,9.

kk

记S*=£%』=ZS，+c,)4=0，l，2/19,这里So="=0.

i=\i=l

我们证明：三组数S|,•­•,；To，T\,…,Tg及S°+”,S[+S9+T都是模的完

So,S9Z,g10

全剩余系.事实上，假如存在〃2,〃，04〃2<〃<9,使S,〃三S〃(modl0),则

=S“-S»,三0(mod10),

/=m+l

即第1行的第加+1至第〃列组成一个“好矩形”，与第1行都是“坏格”矛盾.

又假如存在〃?,〃,04根<”W9,使7；三7；(mod10),则£(2+c：)=T„-Tm=0(mod10),

i=in+\

即第2行至第3行、第加+1列至第〃列组成一个“好矩形”，从而至少有2个小方格不是“坏

格”,矛盾.

类似地，也不存在加,“，0〈根<”49,使S,,+(“三S“+(,(mod10).

因此上述断言得证.故

999

ZSA三三Z(S*+4)三0+1+2+一・+9三5(nx)d10),

k=Qk=0k=0

999

所以Z(S*+，)三Zs«+Z,三5+5三0(mod10),

k=0k=Qk=0

矛盾！故假设不成立，即“坏格”不可能多于25个.

另一方面，构造如下一个3x9的方格表，可验证每个不填10的小方格都是“坏格”，此时有

25个“坏格”.

综上所述，“坏格”个数的最大值是25.

2011B四、（本题满分50分）给定〃个不同实数，其所有全排列组成的集合为A“.对于

（4,4,…,4）eA”，若恰有两个不同的整数i,Je{l,2,…，〃一1}使得《>4+1，勺成立，

则称该排列为“好排列”.求A”中“好排列”的个数.

★解析：首先定义：

对于A中的一个排列（％,々，如果满足《<…<4，则称该排列为自然排列；

对于A中的一个排列（巧，生，…,4），如果有整数ie{1,2,…，〃一1},使得a,.>aM则称a；和

aM构成一个“相邻逆序”；

对于（%,外,…,%）eA,如果它恰有一个“相邻逆序”，则称该排列为“一阶好排列”，A中

所有“一阶好排列”的个数记为工（〃）；如果它恰有两个“相邻逆序”，则称该排列为“二阶

好排列”，A中所有“二阶好排列”的个数记为力（〃）；依题意知，为（〃）恰好是要求的A中

“好排列”的个数。

由题意知：/,（1）=0,力（2）=1,力⑴=力（2）=0，力⑶=1。

以下为了叙述简便，我们把由给定的左个不同实数的所有全排列构成的集合记为4

（k=）,其次求工（〃）。

我们先来考察力++1）与_/；（%）之间的递推关系。

对Aw中的每一个“一阶好排列”（记为。），我们考虑从中取出最大的数4向后剩下的左个

数4,外,…,4按原来的顺序构成的排列（记为人）。

如果排列力是4中的“一阶好排列“，且“相邻逆序”为%>。源，那么，在排列。中，ak+l

的位置只能在%,aM之间或最后；

如果排列力不是Ak中的“一阶好排列”，则排列力中的“相邻逆序”的个数不为1,显然排列

人中“相邻逆序”的个数不能大于1（否则，排列a不是“一阶好排列”，理由是：因为勺+1是

最大的数，所以排列。中“相邻逆序”的个数一定不少于排列b中“相邻逆序”的个数），从

而排列b中“相邻逆序”的个数为0,此时排列b是一个自然排列，而排列a是“一阶好排列”,

所以如的位置不能在最后（有人种可能的位置）。

综合上面的分析可知：/（左+1）=21（k）+k,即/（左+1）+（左+1）+1=2[/>（左）+k+1],

所以工（〃）+〃+1=4X2"2,即工（〃）=2"-〃一1。

最后求人（〃）。

我们先来考察力伏+1）与%（左）之间的递推关系。

对A1中的每一个“二阶好排列”（记为c）,我们考虑从中取出最大的数4+1后剩下的k个数

卬,。2,…，4按原来的顺序构成的排列（记为d）。

如果排列d是4中的“二阶好排列”，且“相邻逆序”为%>aM,%>。川，那么在排列c

中，a*.的位置只能在a”《+]之间或勺,。*之间，或者排在最后；

如果排列d不是4中的“二阶好排列”，则它一定是为中的“一阶好排列”，设“相邻逆序”

为卬>4+1，因为排列c是“二阶好排列"，所以的位置不能在a源之间，也不能排在

最后，其余位置都行，有左—1种可能。

综合上面分析可知：/2（4+1）=3人（幻+卜一1）工（氏），又力（〃）=2"-〃一1,所以

k

f2（k+T）=3f2（k-）+（k-i\2-k-r）,变形为

力（％+1）+6+2>2*|-；（Z+l）（Z+2）=3力⑹+（左+1）"女伏+1）

所以72(〃)+(〃+1)-2"+1)=273-3,即人(〃)=3"-(〃+l).2"+g〃(〃+l),

因此A,,中“好排列”的个数为3"—(〃+1)•2"+；n[n+1)个。

2010A四、（本题满分50分）一种密码锁的密码设置是在正〃边形A4…4的每个顶点处赋

值0和1两个数中的一个，同时在每个顶点处染红、蓝两种颜色之一，使得任意相邻的两个顶

点的数字或颜色中至少有一个相同.问：这种密码锁共有多少种不同的密码设置。

★解析：对于该种密码锁的一种密码设置，如果相邻两个顶点上所赋值的数字不同，在它们

所在的边上标上“，如果颜色不同，则标上A如果数字和颜色都相同，则标上c.于是对于

给定的点4上的设置（共有4种）,按照边上的字母可以依次确定点4,A3,…,A”上的设置.为

了使得最终回到A时的设置与初始时相同，标有。和力的边都是偶数条.所以这种密码锁的

所有不同的密码设置方法数等于在边上标记a,h,c,使得标有a和方的边都是偶数条的方法

数的4倍.

n-2i

设标有a的边有2,.条，标有方的边有2/条，OV/K.选取2i条边标

2

记a的有C；，种方法，在余下的边中取出2j条边标记b的有*种方法，其余的边标记c.由

乘法原理，此时共有C,『种标记方法.对i,j求和，密码锁的所有不同的密码设置方法

数为

〃-2i、

4Ec,rs峭•①

/=0J=o

7

这里我们约定c；=l.

n-2i

L2J

当”为奇数时，n-2i>0,此时Z六。C%=2"~T.②

、25)=2%”力

代入①式中，得嗯

1=07=01=01=0

7

=ZC：2"Y+ZC：2"-*(―=(2+1)"+(2_])"

*=0k=0

=3"+l.

Y]Y]

当〃为偶数时，若心,则②式仍然成立；若i=d则正"边形的所有边都标记处此

22

时只有一种标记方法、.于是，当〃为偶数时，所有不同的密码设置的方法数为

[11

4E第E*4x(c>2"jT)=2+4£(C,”"-2，T)=3"+3.

i=0六0i=0

77

综上所述，这种密码锁的所有不同的密码设置方法数是：当〃为奇数时有3"+1种；当〃

为偶数时有3"+3种.

2009*四、（本题满分50分）在非负数构成的3x9数表

孙Xi2玉5116%17*18项9

PX2\X22X29

X3\》32X39J

中每行的数互不相同，前6列中每列的三数之和为1,否7=X28=X39—0,

X\\X\2再3

了27，%37，内8，*38，司9，》29均大于1。如果P的前三列构成的数表SX2\X22x23满足如

X3\X32心）

/、

下性质（0）：对于数表P中任意一列々A(k=1,2,…,9)均存在某个ie{1,2,3}使得⑶

xxk<%=inin{xn,x/2,x13}。求证：

⑴最小值%=min{x〃，项2，玉3}，，=1,2,3一定来自数表S的不同列;

/、、

X\\X\2%

⑵存在数表尸中唯一的一列“，右力1,2,3,使得3x3数表S*X2\X22%仍

X3\X32Jr>

然具有性质（。）。

★证明：（i）假设最小值%=min{/，玉2，玉3}，7=1，2,3不是取自数表5的不同列。则存在一

列不含任何%.不妨设/丰x/2,z=1,2,3.由于数表P中同一行中的任何两个元素都不等，于是

《<可2，》=1，2,3.另一方面，由于数表S具有性质（0）,在（3）中取女=2,则存在某个

i0e{1,2,3）使得xio2<w,o.矛盾。

（ii）由抽屉原理知min{xlpxI2）,min{x21,x22},min{x31,x32）

中至少有两个值取在同一列。不妨设min{x21,x22}=x22,min{x3l,x32}=x32.

由前面的结论知数表S的第一列一定含有某个小,所以只能是尤”=〃「同样，第二列中也必

含某个%,i=l,2.不妨设々2=〃2.于是“3=%33，即对是数表S中的对角线上数字：

/\

芭1X12X\3

S=孙423

\X3lX32工337

记M二{1,2,9）,令集合/=伙£A/|工欣>min{x〃,Xj2}，i=l，3}

显然/={k^M\xxk>玉],%3A>132}且1，2,3金/.因为芭8，元38>12玉1，工32，所以8£八

故/W①.于是存在XGI使得=max{马/2£/}.显然，《丰1,2,3.

下面证明3x3数表S'=具有性质（0）.

从上面的选法可知u；:=01山{与,玉2，/，}=min{xzl,x/2},（z=1,3）.这说明

否1>min{],x}2]>u],x3k.>min{x31,x32}>u3

又由S满足性质（0）,在（3）中取攵=%”,推得/.</，于是〃2=min{x21,A22,x2^}=^*

下证对任意的左£M,存在某个i=1,2,3使得〃；>4.假若不然，则>nin{马,xi2}J=1,3

且々£>/厂.这与乙厂的最大性矛盾。因此，数表S'满足性质（0）。

2k2k

X||

下证唯一性。设有攵eM使得数表S,S=x2,

l%31

具有性质(0).不失一般性，我们假定%=min{Xu，X]2，X|3}=Xii(4)

u2=min{x2l,x22,x23}=x22>M3=min{x3l,x32,x33}=x33<,xi2<x3l

由于工32<工31,x22<x2l,及(i),有4=。加{孙,否2，芭《}=孙.又由(i)知：或者

(a)ii3=min{x3l,x32,x3(t)=,或者(Z7)u2=min{x2l,x22,x2k}=•

如果(a)成立，由数表6具有性质(O),则w,=min{xll,x12,xu.}=xll,

(5)u2-min{x2l,x22,x2k}-x22,u3=min{x31,,x3k}=x3k

由数表6满足性质(O),则对于3e"至少存在一个ie{1,2,3}使得均2x,3,又由(4),(5)

X

式知，&=xn<X]3,U2=X22<工23•所以只能有a-3kNX33•同样由数表S满足性质(o)，

可推得七32尤3A于是左=3,即数表S=6・

如果3)成立，则4=min{%[],网2，演《}=X”，4=1向{%11,玉2，4}=n11，(6)

，认=

w2=nm{x2l,x22,x2k}X2*min{x3i,x32,x3k}=x32

由数表$满足性质(O),对于&*eM,存在某个i=1,2,3使得u,>xjk.,

由A*e/及(4)和(6)式知，x]k.>X”=w,,x3k，>x32=4.

于是只能有x2k.<u2=々z类似地，由S'满足性质(O)及％eM可推得x2k<u2-x2k.,

从而k*=k。

2007*二、(本题满分40分)。如图所示，在7x8的长方形棋盘的每个小方格的中心点各放一

个棋子。如果两个棋子所在的小方格共边或者共顶点，那么称这两个棋子相连。现从这56个

棋子中取出一些，使得棋盘上剩下的棋子，没有五个在一条直线(横竖斜方向)上依次相连。

间最少取出多少个棋子才能满足要求？并说明理由。

★解析：

解：最少要取出11个棋子，才可能满足要求。其原因如下：

如果一个方格在第i行第/列，则记这个方格为(i,力。

第一步证明若任取10个棋子，则余下的棋子必有一个五子连

珠，即五个棋子在一条直线(横、竖、斜方向)上依次相连。

用反证法。假设可取出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,7)、(3,8)、(4,6)、(4,7)、(4,8)、

(5,6)、(5,7)、(5,8)所在区域内至少取出3个棋子。这样，在这些

区域内至少已取出了10个棋子。

因此，在中心阴影区域内不能取出棋子。由于①、②、③、④这4个

棋子至多被取出2个，从而，从斜的方向看必有五子连珠了。矛盾。

第二步构造一种取法，共取走II个棋子，余下的棋子没有五子连珠。如图2,只要取出有标

号位置的棋子，则余下的棋子不可能五子连珠。

综上所述，最少要取走11个棋子，才可能使得余下的棋子没有五子连珠。

2005*12、如果自然数。的各位数字之和等于7,那么称。为“吉祥数”.将所有吉祥数从小到

大排成一列…，若=2005,则=

♦答案：5200

★解析：因为方程