综合上面分析可知：f2(k?1)?3f2(k)??k?1?f1(k)，又f1(n)?2?n?1，所以
nf2(k?1)?3f2(k)??k?1?(2k?k?1)，变形为
11??f2(k?1)?(k?2)?2k?1?(k?1)(k?2)?3?f2(k)??k?1??2k?k(k?1)?
22??11n(n?1)?27?3n?3，即f2(n)?3n?(n?1)?2n?n?n?1?， 221nn因此An中“好排列”的个数为3?(n?1)?2?n?n?1?个。
2所以f2(n)??n?1??2?n
2010A四、（本题满分50分）一种密码锁的密码设置是在正n边形A1A2?An的每个顶点处赋值0和
1两个数中的一个，同时在每个顶点处染红、蓝两种颜色之一，使得任意相邻的两个顶点的数字或颜
色中至少有一个相同.问：这种密码锁共有多少种不同的密码设置。
★解析：对于该种密码锁的一种密码设置，如果相邻两个顶点上所赋值的数字不同，在它们所在的边上标上a，如果颜色不同，则标上b，如果数字和颜色都相同，则标上c．于是对于给定的点A1上的设置（共有4种），按照边上的字母可以依次确定点A2,A3,,An上的设置．为了使得最终回到A1时的设置与初始时相同，标有a和b的边都是偶数条．所以这种密码锁的所有不同的密码设置方法
数等于在边上标记a，b，c，使得标有a和b的边都是偶数条的方法数的4倍．
设标有a的边有2i条，0?i???，标有b的边有2j条，0?j??22i
2j?n????n?2i?．选取2i条边标??2?记a的有Cn种方法，在余下的边中取出2j条边标记b的有Cn?2i种方法，其余的边标记c．由乘法
2i2j原理，此时共有CnCn?2i种标记方法．对i，j求和，密码锁的所有不同的密码设置方法数为
4?i?0?n??2????n?2i????2????2i2j?CC?n?n?2i?． ①
j?0????0这里我们约定C0?1．
当n为奇数时，n?2i?0，此时
?n?2i??2???j?0?C2jn?2i?2n?2i?1． ②
代入①式中，得4?i?0?n??2????n?2i??n??n????2??2??2??????2i??2j?2in?2i?1??2??Cn2i2n?2i? ?Cn?Cn?2i??4??Cn2j?0i?0i?0????n??C2knk?0nn?kkn?k??Cn2(?1)k?(2?1)n?(2?1)n k?0?3n?1．
当n为偶数时，若i?nn，则②式仍然成立；若i?，则正n边形的所有边都标记a，此时22只有一种标记方法．于是，当n为偶数时，所有不同的密码设置的方法数为
4?i?0?n??2???n?2i?n??n????????2??2??1?2????2i??2j?????2in?2i?1???2?4??Cn2i2n?2i?1??3n?3． ?Cn?Cn?2i??4??1???Cn2j?0i?0i?0????????n 综上所述，这种密码锁的所有不同的密码设置方法数是：当n为奇数时有3?1种；当n为偶数时有3?3种．
2009*四、（本题满分50分）在非负数构成的3?9数表
n?x11?P??x21?x?31x12x22x32x13x23x33x14x24x34x15x25x35x16x26x36x17x27x37x18x28x38x19??x29? x39??中每行的数互不相同，前6列中每列的三数之和为1，x17?x28?x39?0，x27,x37,x18,x38,x19,x29?x11?均大于1。如果P的前三列构成的数表S??x21?x?31x12x22x32x13??x23?满足如下性质（O）：对于数表P中任x33???x1k???1,2,3?使得⑶x1k?ui?min?xi1,xi2,x13?。求证： 意一列?x2k?（k?1,2,?,9）均存在某个i???x??3k?⑴最小值ui?min?xi1,xi2,x13?，i?1,2,3一定来自数表S的不同列；
?x1k???x11?????⑵存在数表P中唯一的一列?x2k??，k?1,2,3，使得3?3数表S??x21?x??x??3k??31性质（O）。
x12x22x32x1k???x2k??仍然具有x3k???★证明：（i）假设最小值ui?min{xi1,xi2,xi3},i?1,2,3不是取自数表S的不同列。则存在一列不含任何ui.不妨设ui?xi2,i?1,2,3.由于数表P中同一行中的任何两个元素都不等，于是
ui?xi2,i?1,2,3.另一方面，由于数表S具有性质（?），在（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.
由前面的结论知数表S的第一列一定含有某个ui，所以只能是x11?u1.同样，第二列中也必含某个?x11x12x13??xxxui,i?1,2.不妨设x22?u2.于是u3?x33，即ui是数表S中的对角线上数字：S??212223?? ?xxx??313233?记M=｛1，2，...，9｝，令集合I?{k?M|xik?min{xi1,xi2},i?1,3}
显然I?{k?M|x1k?x11,x3k?x32}且1,2,3?I.因为x18,x38?1?x11,x32，所以8?I.
**故I??.于是存在k?I使得x2k*?max{x2k|k?I}.显然，k?1,2,3.
?x11x12x1k*???? 下面证明3?3数表S??x21x22x2k*?具有性质（?）. ??x31x32x??3k*??从上面的选法可知ui:?min{xi1,xi2,xik*}?min{xi1,xi2},(i?1,3).这说明
'x1k*?min{x11,x12}?u1,x3k*?min{x31,x32}?u3
*'又由S满足性质（?），在（3）中取k?k，推得x2k*?u2,于是u2?min{x21,x22,x2k*}?x2k* '下证对任意的k?M,存在某个i?1,2,3使得ui?xik.假若不然，则xik?min{xi1,xi2},i?1,3且
x2k?x2k*.这与x2k*的最大性矛盾。因此，数表S'满足性质（?）。
?x11????x下证唯一性。设有k?M使得数表S，S21?x?31x12x22x33x1k??x2k? x3k??具有性质（?）.不失一般性，我们假定u1?min{x11,x12,x13}?x11（4）
u2?min{x21,x22,x23}?x22，u3?min{x31,x32,x33}?x33。x32?x31
?1?min{x11,x12,x1k}?x11.又由（i)知：或者由于x32?x31，x22?x21，及（i），有u?3?min{x31,x32,x3k}?x3k，或者(b)u?2?min{x21,x22,x2k}?x2k. (a)u?具有性质（?）?1?min{x11,x12,x1k}?x11， 如果(a)成立，由数表S，则u?2?min{x21,x22,x2k}?x22，u?3?min{x31,x32,x3k}?x3k （5） u?满足性质（?）?i?xi3，又由（4）由数表S，则对于3?M至少存在一个i?{1,2,3}使得u，（5）式?1?x11?x13,u?2?x22?x23.所以只能有u?3?x3k?x33.同样由数表S满足性质（?）知，u，可推得
?· x33?x3k.于是k?3，即数表S?S?1?min{x11,x12,x1k}?x11，u?1?min{x11,x12,x1k}?x11，（6） 如果(b)成立，则u?2?min{x21,x22,x2k}?x2k，u?3?min{x31,x32,x3k}?x32 u*?满足性质（?）??x*， 由数表S，对于k?M，存在某个i?1,2,3使得uiik*?1,x3k*?x32?u?3. 由k?I及（4）和（6）式知，x1k*?x11?u'?2?x2k.类似地，由S'满足性质（?）及k?M可推得x2k?u2于是只能有x2k*?u?x2k*，从而
k*?k。
2007*二、（本题满分40分）。如图所示，在7?8的长方形棋盘的每个小方格的中心点各放一个棋子。如果两个棋子所在的小方格共边或者共顶点，那么称这两个棋子相连。现从这56个棋子中取出一些，使得棋盘上剩下的棋子，没有五个在一条直线（横竖斜方向）上依次相连。问最少取出多少个棋子才能满足要求？并说明理由。 ★解析：
解：最少要取出11个棋子，才可能满足要求。其原因如下： 如果一个方格在第i行第j列，则记这个方格为(i，j)。
第一步证明若任取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个，从而，从斜的方向看必有五子连珠了。矛盾。
图1 图2
第二步构造一种取法，共取走11个棋子，余下的棋子没有五子连珠。如图2，只要取出有标号位置的棋子，则余下的棋子不可能五子连珠。
综上所述，最少要取走11个棋子，才可能使得余下的棋子没有五子连珠。
2005*12、如果自然数a的各位数字之和等于7，那么称a为“吉祥数”.将所有吉祥数从小到大排成一列a1,a2,a3,?，若an?2005，则a5n? ◆答案：5200
xi?0★解析：因为方程x1?x2???xk?m的非负整数解的个数为Cm?k?1，而使x1?1，（i?2）
m?16的整数解个数为Cm?k?2。现取m?7，可知，k位吉祥数的个数为p(k)?Ck?5
m因为2005是形如2abc的数中最小的一个吉祥数，且p(1)?1，p(2)?7，p(3)?28，对四位吉
6祥数1abc，其个数为满足a?b?c?6的非负整数解的个数，即C6?3?1?28个。
又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
,52000， 所以从大到小最后六个五位吉祥数依次是70000,61000,60100,60010,60001所以第325个吉祥数是52000，即a5n?52000
2003*三、（本题满分50分）。由n个点和这些点之间的l条连线段组成一个空间图形，其中
n?q2?q?1，l?1q(q?1)2?1，q?2，q?N。已知此图中任四点不共面，每点至少有一条2连线段，存在一点至少有q?2条连线段．证明：图中必存在一个空间四边形(即由四点A,B,C,D和四条连线段AB,BC,CD,DA组成的图形)． ★证明：
证明：设点集为V??A0,A1,?,An?1?，与Ai连线的点集为Bi，且Bi?bi．于是1?bi?n?1．又显然有
． ?bi?2l?q?q?1??2，
2i?0n?1若存在一点与其余点都连线，不妨设b0?n?1．
1981-2018年全国高中数学联赛真题分类汇编含解析答案16组合与构造
