2019年全国数学竞赛命题研讨会材料

1 代代 数数 A 1（赵斌）（赵斌） 设数列 n x满足 2* 1 6, nn xxnN + =-，且对于 1 2x-，都存在n使得 n xa， 求a的最大值 解解：a的最大值为 211 2 - 一方面， 当数列为 1 211 2 x - =时， 有 211 2 k x - =，k为奇数； 211 2 k x - =， k为奇数故 211 2 a - 另一方面，若对于任意正整数n都有 211 2 n x - ，则 (1)我们首先证明，对任意，都要： 211 3 2 n x - - - 若3 n x，与 1 211 3 2 n x + - -， 则 211211 (,) 22 n x - -，从而 2 2 1 211211 66 22 nn xx + - =- - = ， 与 2 211 2 n x + - = 记X有所有1,2,100到自身的一一映射构成的集合对于任意实数 12100 ,a aa，求 12100 min (, (1)(, (2)(, (100) X f af af a s sss + 的最大值 解解：所求的最大值为50512550=，一方面当 12100 50aaa=时， 12100 (, (1)(, (2)(, (100)50512550,f af af asss+= 另一方面，我们只需证明，对于任意 12100 ,a aa，都存在一个Xs ，使得 12100 (, (1)(, (2)(, (100)2550f af af asss+ 由 对 称 性 ， 不 妨 设 12100 aaa， 且 取s就 为 恒 等 映 射 ， 则 1210012100 (, (1)(, (2)(, (100)(,1)(,2)(,100)f af af af af af asss+=+ 我们可设 100 100a，否则上述表达式显然为0，并记得k为最小的正整数使得 0 k ak-，从而 121001100 (,1)(,2)(,100)(, )(,1)(,100) kk f af af af a kf akf a + +=+ 1100 (101)(101)50512550, kkk aaak akk + =+- = 最后一步用到了k是整数，故我们完成了证明 A 3（张端阳）（张端阳） 给定整数2n求最小的实数l，使得对任意满足 1 1 n i i a = = 的非负实数 12 , n a aa，都有 2 12 1 1 min ,. 1 n in i aa aa n l = + - 解解：对 1 0, n e ，取 12 1 , 1 n aaa n e e - = - 则 2 2 11 (1) 11 n nn e ele - +-+ - ， 即 (1)2nnel+- 对任意 1 0, n e 成立令0e得， 2 1n l - 下证： 2 12 1 21 min , 11 n in i aa aa nn = + - 不妨设 112 min , n aa aa=由柯西不等式， 2 22 1 22 11 (1) 11 nn ii ii aaa nn = =- - 所以 3 222 12111 1 212 min ,(1) 111 n in i aa aaaaa nnn = +-+ - 2 1 11 111 n a nnn =+ - 成立 综上，所求最小值为 2 1n- A 4（张端阳）（张端阳） 设整数2n 不全为零的实数 12 , n x xx满足 1 0 n i i x = = ，且对任意正实数 t，至多有 1 t 对( , )i j，使得| ij xxt- 证明： () 2 11 1 1 maxmin. n iii i ni n i xxx n = - 证明证明：由拉格朗日恒等式， 2 22 111 () nn iiij iiijn nxxxx = =+- ， 所以只需证明 2 11 1 ()maxmin ijii i ni n ijn xxxx - 设|(1) ij xxijn- 能 取 到 的 所 有 非 零 值 为 12 , m y yy， 其 中 12 0 m yyy 再对1km，设有 k a 对( , )i j，使得| ijk xxy-= 对1km，在条件中取 k ty=得，至多有 1 k y 对( , )i j，使得| ij xxt-，所 以 1 1 kkm k aaa y + + 记 1kkkm Saaa + =+，则 1 k k S y 由阿贝尔变换， 22 2222 1 1 1111 111 ()() 222 mmm kk ijkkkkk ijnkkk k yy xxa ySyy y - - = - -=- ， 其中 0 0y= 因为 1kk yy - ，所以 22 111 1 ()() 2() kkkkkk kk kk yyyyyy yy yy - - -+- =- 故 2 1 11 11 ()()maxmin m ijkkmii i ni n ijnk xxyyyxx - = -=- 注注：本题改编自Problems from the book第十九章习题 19，原题是： 4 设 1212 , nn x xxy yy是正实数， 满足对任意正实数t， 至多有 1 t 对( , )i j， 使得 ij xyt+ 证明： 1, 11 max() nn iiij i jn ii xyxy = + 本题采用了不同于原解答（积分）的方法，且得到了更强的结果 A 5（王永喜）（王永喜） 设m是正整数，且(1,2, ) i y in=是任意实数，满足 21 1 ()0 n m i i y + = = 求证： 21 4 1 1 (21) max| 2 m m n i i i i n y m y nm + = + 证明证明：设 1 n N Ni i Iy = =，对任意的实数r，利用柯西不等式我们有 2 22221 111 ()() nnn mm iiii iii yryyry + = + 结合条件我们有 22 4221 (2) mm IrInrIr I+整理得 22 212224 ()20 mm nIIrIIrI I-+ +，rR 而由柯西不等式有 2 21 nII那么上式必有 222 222421 044()0 rmm III InIID - 那么 2 22 4 2 21 m m II I nII - 由Holder不等式有 2 122 2 22 22 1 () () m mn m mim m i I InyI n - - = 故 21 2 4 222 21 () () m m m I I nnII + - - 另外一方面，利用均值不等式得： 221 4221 1212 21 (2 ) ( )()() (21) mm mm m mn InIII m + + + - + ， 所以 21 4 41 412 (21) ( ) (2 ) m m m mm m II nm + - + 也就是 4 21 4 412 11 (21) () (2 ) m mnn m ii mm ii m yy nm + - = + 由均值原理得 5 21 4 1 1 (21) max| 2 m m n i i i i n y m y nm + = + A 6（王永喜）（王永喜） 设0 (1, 2, ) i ain=，且3n，满足任何两个数不相等，求证： 22 2 11 1(1) ()9 ij ij nij n ij n n a a aa - - 证明证明：引理引理（2008年越南数学奥林匹克） ： 设,x y z非负，且无任何两个数相等，则有 222 1114 ()()()xyyzzxxyyzxz + -+ 引理证明引理证明：不妨设min( , , )zx y z=，注意到 222 ()()()2()()xzyzxyxzyz-+-=-+-， 利用均值不等式得 2 2222 11()2 ()()() ()()() xy xyxyyzzxxzyz cyc - =+ - 22 ()()()()xzyzxzyz + - 或者设 2 1 ( , , ) () cyc f x y z xy = - ，由(,)f xd yd zd+与d的值无关，故不妨设 0z =，此时 222 222222 1114(3) 0 ()() xyxy xyxyxyxyx y +- +-= - 回到原问题由 , , ()6(2) ijjkikij i j kij a aa aa ana a 互不相等是给定的偶数 在nn的方格表中选取m个 单位方格，已知可以在选取的每个方格中画一条对角线，满足任意两条对角线不 共点求m的最大值 解解：m的最大值为 (1) 2 n n 先给出构造如图所示，此时 (1) (1)1 2 n n mnn + =+-+ = 下证 (1) 2 n n m + 注意到nn方格，共有1n+行格点，将第1, 3,1n+行格点染为红色，将 第2, 4, n行格点染为蓝色注意到每条对角线连接一个红点和一个蓝色，且 蓝点个数共 (1) 2 n n+ ，于是所求 (1) 2 n n m + C 2（吴尉迟）（吴尉迟） （不相交的对角线问题不相交的对角线问题 2） ：在77的方格表中选取m个方格，已知可以在 选取的每个方格中画一条对角线，满足任意两条对角线不共点求m的最大值 解解：m的最大值为29 先给出构造，构造如上图所示 我们用( , )f a b表示ab方格表中， 能选出满足条件的方格个数的最大值， 则 (7,7)f即为所求m的最大值 引理引理： (2, )( ,2)1fnf nn= + 引理的证明引理的证明：由对称性知(2, )( ,2)fnf n=考虑2n方格表中的格点，共有 3行格点将第1, 3行格点染为红色，第2行格点染为蓝色注意到每条对角线连 接一个红点和一个蓝色，且蓝点个数共1n+，于是至多能选出1n+个满足要求 23 的方格引理得证 下证(7,7)29f 反证法，假设(7,7)30f由引理知，(6,7)3 (2,7)24ff从而77方 格表第1行和第7行至少有30246-=条对角线又(2,7)8f，所以第2, 6行各 至多2条对角线 于是前5行至少302622- - =条对角线， 又(4,7)2 816f =， 故第5行至少22166-=条对角线，类似地，对后5行进行分析可得第3行至少6 条对角线从而第4行至多2条对角线 现在，第2, 4, 6行至多2条对角线类似地，第2, 4, 6列至多2条对角线从 而这些行列共至多有232312 + =条对角线 除这些行列外，77方格表中共 有16个方格（图中白色方格） ，故至多有161228+=个方格中有对角线，这与 (7,7)30f矛盾故(7,7)29f C 3（赵斌）（赵斌） 有n个人参加一次聚会， 已知这n个人中至少有18n个朋友对(每对中的两人 相识)，证明：可以从这些人中选出一些人组成无公共成员的两个(非空的)小组 ,A B，A 中的每个人在B中认识的人数大于等于10，B中的每个人在A中认识 的人数大于等于10(不是每个人都要属于组A或组B) （图论题，改编自 Reinhard Diestel 的Graph Theory中的习题） 解解：首先我们可以将问题转化为这样一个图论题：一个图G，有n个点，且 边数大于等于18n，证明：可以选出两个互不相交的非空顶点集,A B，使得A中 的每个顶点与B中的顶点的连线数大于等于10，B中的每个顶点与A中的顶点 的连线数大于等于10 我们分两步来完成这个题的证明：存在一个G的子图H使得H的每个顶点 的度数大于等于19这是因为首先对边数估计有 2 18 n C，则我们有37n然 后对n采用数学归纳法， 若37n =时， 此时图G为37阶完全图， 显然符合要求 假 设命题对于137n- 成立，对于n的情况，若G中存在一点v，使得( )18d v ， 则考虑图 Gv 我们有，该图的边数大于等于18(1)n-，使用数学归纳法易得结 论成立 由上取G的子图H使得H的每个顶点的度数大于等于19，然后将H的顶点 分成两组,A B，使得,A B间的边数最大，那么易知对于每个A中的顶点至少有 10 个B中的顶点与其相连(因为否则将其调入B中， 由于此时与它相连的,A B中 的总点数19， 则其与A中相连的点数10， 即能使新,A B的边数严格增大， 这 与我们的选取矛盾)类似可得对于每个B中的顶点至少有10个A中的顶点与其 相连 注释注释： 本题具有一定难度， 主要考察组合数学中的数学归纳法和极端原理两 个非常重要的思想另外有兴趣的同学也可以思考下“18”这个数字可否改进 24 C 4（缠祥瑞）（缠祥瑞） 平面上有100个不同的点和n条不同的直线 12 , , n l ll，记直线 k l经过的点数 为 k a若 12 250 n aaa，求n的最小可能值 分析分析：由于两条不同的直线不能过两个相同的点，想到用算两次的方法 线上的点数不好入手，可以考虑点在多少条线上 考虑100个点 12100 ,A AA，记点 k A在 k x条直线上，则 100 1 250 k k x ，且 100 22 1 k xn k CC 由柯西不等式知 2 100 100 2 100100 12 1 11 375 220022 k k k k kkk x kk xx xx C ， 所以 100 2 1 188 k x k C 因此 2 3760nn，解得20n 用这种常见的方法可以得到20n 反过来，若20n ，可以解得 100 1 251 k k x ，且放缩很大，再进行细节上的讨论 可以得到 100 1 245 k k x ，因此21n 本题中21n 时的构造也非常困难 解解：首先证明21n 设恰好在0,1,2,k kn条直线上的点有 k x个，则 0 100 n k k x ，且 01 250 nn kk kk kxa 所以 2 100 n k k x ， 0 2 1150150 n k k kxx 考虑直线的交点个数，有 22 2 n kkn k C xC 对任意整数k有230kk， 即 1 23 2 k k k ， 故2k 时 2 23 k Ck， 因此 22 222 212 150 100200 nnn nkkkk kkk CC xkxx ， 解得21n 下面证明：21n 时，存在这样的点和直线 当100个点中有3个点不在直线上，1个点只在一条直线上，39个点是两条直 线的交点，57个点是三条直线的交点时，1 221 1 39 257 3250aaa ， 满足条件 下面只要构造21条线，它们两两相交，且有57组三线共点即可 25 考虑单位圆 22 1xy，记 cos ,sinP，直线 2lPP （当 5 , , 33 时， l为圆的切线） 取20条直线 10 i i ll ，1,2,20i 可知这20条直线两两相交 若2 | ， 则 ? ? 22mod2PPPP， lPP 同 理 lPP， lPP， 故 ,lll三线共点于 PPP的垂心 若，则2 2，故l不经过 ,lll的交点 同理 因此， 若 ,lll三线共点， 则2 | ； 且不存在四线共点 , 有20 19种不同的选择， 满足20 mod2或20 mod2 的各有19种，不计, 顺序，有 20 192 19 57 3! 个三线共点 此时， 必存在直线 21 l与 1220 , ,l ll都相交， 且没有三线共点 满足交点个数要 求 注注：本题的模型是两年前想到的，经过一些尝试得到这道题先做了100个 点20条线的情况， 然后编了这道题， 最开始是想把重点放在考察前半部分证明， 在做题过程中发现这么问构造部分才是难点，想要三线共点尽可能多，考虑直线 的角度给出了上面的构造，才完成了本题的证明 C 5（吴尉迟）（吴尉迟） 给定正整数n，证明存在正整数m满足以下条件：对1,2, m的任意子集 G， 若| 2 m G， 则存在1n+个正整数 012 , n x x xx， 使得 12 , n x xx中任意若 干元素与 0 x的和都属于G 证法一证法一（解法属于浙江省瑞安中学 沈焕超） ： 1n=时，取4m=，设 1212 ,()a aG aa，取 01121 ,xaxaa=-即可 nk=时，假设存在偶数 k m满足条件下证1nk=+的情形 取 1 (21) k m kk mm N + =+，其中N为待定正整数从而 1k m + 为偶数对于满足 1 | 2 k m G + 的子集G构造(21) k M N+个序列： ,1,2, (,),0,1,(21) k k m iiii m AaaaiN=+， 其中 , i j a满足 , 0(,), 1(,). i j im kjG a im kjG + = + 令() i S A为 i A中所有元素之和，我们证明：对于足够大的N，存在21 k m +个整数 12 21 mk iii + - 考虑(1) ,(1,2, ) i GGiq iq ir=-=中| 2 i Gq d 的集合的个数， 记个数为R 则 有 1 |()11 222 r i i r rquGqGqRqrRRqq ddd dd = +-=-+ 解得 2 1 22 r Rr dd d - - - ，结合知， 1 (1)nRq - - 对R个满足| 2 i Gq d 的集合使用归纳假设 对每个 i G， 存在n个满足条件的 正整数 011 , iii n x xx - ， 注意到这些元素均是1,1q-中的整数， 故 121 , iii n x xx - 至多 有 1 (1)nq - -有选取方式 又 1 (1)nRq - -，故由抽屉原理知存在两个集合 01 , ii GG，满足 00 11 , ii n xx - 与 11 11 , ii n xx - 相同注意到 0 0 i x与 1 0 i x属于不同的 i G，故不相等不妨设 01 00 ii xx取 0 00 i xx=， 00 1111 , ii nn xxxx - =， 01 00 ii n xxx=-， 则 01 , n x xx满足要求 事实上， 若 1, , n xx中取的k个元素中包含, n x则由对 1 i G的归纳假设知， 这k 元素与 0 x的和属于 1 i G，则自然属于G 若 1, , n xx中取的k个元素中不包含 n x，则由对 0 i G的归纳假设知，这k元素 与 0 x的和属于 0 i G，故也属于G 注注：本题来源于范德瓦尔登定理（对于任意给定的正整数k和l，存在正整 数( , )n k l，使得1,2, n每个元素染成k种颜色之一时，必存在长为l的同色的 等差数列）反命题的研究 Szemerdi 在On sets of integers containing no four elements in arithmetic progression一文中研究了下面的问题：1,2, n中的子集，考 虑其中不含长度为4的等差数列的子集，这样的子集中元素个数的最大值为 4( ) ntSzemerdi 证明了 4( ) n n t 会趋于0本题改编自该论文中的一个引理本 题也刊于数学新星网第32期征解问题 C 6（刘伟才）（刘伟才） 设 12341234 ,;,a a a a b b b b是 均 不 超 过2019的 两 组 正 整 数 ， 且 ii ab (1,2,3,4)i ， 12341 2 3 4 a a a abb b b，求 3124 1234 bbbb aaaa 的最小值. 28 解解：记 3124 1234 bbbb S aaaa ，当 12343412 2019,2018aabbaabb 时， 3124 1234 1 4, 1009 2019 bbbb St aaaa 我们证明t为所求最小值. 不妨设 3124 1234 bbbb aaaa ，则 1 1 1 b a 情形一： 324 234 1 bbb aaa ，则 11223344 ,ba ab ab ab均不小于1，若 1122 ,ba ab 3344 ,ab ab中有一个数不小于2，设 11 2ba或2 ii ab，则由 3124 1234 bbbb S aaaa 111 11 ()() 1 j iiik iijk b baabbbb a aa aaa 1 11 2 1 j ik iijk b bbb a aa aaa 1 3 1 2 13 2018 2019 j ik ijk b bbb t a aaa ， 其中 , , 2,3,4i j k ， 故只需考虑 11223344 ,ba ab ab ab 均为1的情形.此时， 将问题表述为 1111 1 axyz axyz ，由伯努利不等式 1111 1(1)(1)(1) 111axyz 111 1, 111xyz 故 1111axyz S axyz 1111 4 axyz 111111 4 111xyzxyz 111 4 (1)(1)(1)x xy yz z 3 4 2018 2019 t 情形二： 3124 1234 1 bbbb aaaa ，此时易得 1234 ,2018,2019a aa a，故 1 31133242244 13132424 ()()()() 11 bbbaabb bbaab S a aa aa aa a 1 324 13132424 11 11 bbb b a aa aa aa a 1 324 13241324 11 22 bb b b a a a aa aa a 11 22 2018 20192018 2019 t ， 当且仅当 12343412 2018,2019aabbaabb时取得等号. 29 情形三： 3124 1234 1 bbbb aaaa ，类似情形一可以得出St. 综上， 3124 1234 bbbb aaaa 的最小值为 1 4 1009 2019 . C 7（邓晓）（邓晓） 给定一个19 19的方格棋盘， 其中有n个格子上各放置一枚棋子.对每个棋子， 以其所在格为中心作一个5 5的边平行于相应棋盘边界的正方形， 这个正方形称 为该棋子的范围.已知每个棋子范围中恰有一个其它棋子，求n的最大值. 证明：证明：n的最大值为 72. 对每个棋子，以其所在格为最左上角的格作一个3 3的边平行于棋盘边界的 正 方形， 这个正方形称为该棋子的小范围.若棋子A在棋子B的范围中， 易知B也在 A范围中.由题设知这些棋子可两两配对使每一对棋子互相在其范围中， 所以n为 偶数，并将配对的棋子分成一组，共 2 n 组.若棋子在从上至下第x行，从左至右第 y列，则记此棋子坐标为( , )x y.对棋子,A B，设其坐标分别为 1122 ( ,),(,)x yxy，所 以,A B互相在另外一个棋子的范围中等价于 12 12 | 2 , , ,0,1,2 | 2 xx a b c d yy ， 使得 12 12 xaxb ycyd A的小范围与B的小范围有公共方格. 将原19 19的棋盘的最下边与最右边分别加上两行，两列构成一个21 21的 大 棋盘， 则所有棋子的小范围都包含于大棋盘中， 且同组棋子的小范围有公共方格， 异组的棋子的小范围中没有公共方格.考虑一组棋子， 若它们不再同一行， 则其小 范围占至少4行，每一行占至少3格，所以它们的小范围占至少12格.若它们在 同一行，则它们不在同一列，同理可得它们的小范围占至少12格.而不同组的棋 子的小范围没有公共方格，所以所有棋子的小范围占了至少12 2 n? .故 21 21 36 212 n ，72n. 构造：将21 21的大棋盘分为 9 个7 7的棋盘，对每个7 7，内部如下图所 示 放置8个棋子，故总共放了72个棋子均在原棋盘内，且每个棋子范围内恰有一 个其它棋子. （此题原始形式为m n的棋盘放棋子，每个棋子的范围为以其中心的3 3的正 30 方形， 其余条件不变， 则最多能放 (1)(1) 2 6 mn 个棋子.实际上当12n 时，n n 的棋盘在此题条件下的答案为 2 (2) 2 12 n ，即为在(2)(2)nn的大棋盘上放置 2 (2) 12 n 个不交的3 4矩形.对于范围概念的转化通过坐标的角度去推比较自然， 然后把范围变成小范围） C 8（张宁）（张宁） 方格表中只有两种方格： “雷”格与数字格. “雷”格中没有数字. 数字格中 填有数字m，当且仅当其周围的8个格中共有m个“雷”格（当数字格位于方格 表的边界或角落时，改为其周围的5个格或3个格）. (1) ) 12() 12(nn的方格表中有1 2 n个“雷”格，求所有数字格中数字之和 的最大值. (2) 求k的最大值，使得在任意一张含有k个“雷”格的nn方格表中，均 存在至少一个填有数字“0”的数字格.（结果用含n的式子表示） 解：解：先约定：当且仅当两个格有不少于一个公共顶点时，称它们相邻；方格 表第i列第j行的方格记为(i,j). (1) 用mi表示与数字格Mi相邻的雷格个数(i=1,2,.,3n2+4n)，用li表示与雷 格Li相邻的数字格个数(i=1,2,.,n2+1). 由于“相邻”是相互的，有mi=li. 只 需求li的最大值. 对于n=1，尝试可得li11. n2时，设共有B个雷位于边界（除四角） ，J个雷位于四角，S对雷彼此 相邻. 不位于方格表边角的雷至多与8个数字格相邻，位于边界的雷至多与5个 数字格相邻，位于角落的雷至多与3个数字格相邻. 除位置因素外，每有一对相 邻雷格(Lk,Lj)也将导致lk与lj分别减少1，从而使li减少2. 于是有 li=8(n2+1)-(8-5)B-(8-3)J-2S=8(n2+1)-3B-5J-2S. 明显li8(n2+1)-1. 先证明li8(n2+1)或8(n2+1)-2，即(B,J,S)(0,0,0)或(0,0,1). 用反证法，假设(B,J,S)=(0,0,0)或(0,0,1). 给出两种划分方格表的方式： 划分1：对于r,S0,1,.,n，将(2r,2s)、(2r+1,2s)、(2r,2s+1)、(2r+1,2s+1) 划为一个区域. 划分2：对于r,S0,1,.,n，将(2r+1,2s+1)、(2r+1,2s+2)、(2r+2,2s+1)、 (2r+2,2s+2)划为一个区域. （当一个区域中有至少一个方格有意义或未被去掉时，才认为这个区域存在） 由于B=J=0，不妨将所有边角格去掉，剩余n2个区域. 因为n2，存在至少 包含2个格的区域. 由于雷格总数为n2+1，根据抽屉原理，存在一个区域，其中 含有至少两个雷，即一对相邻雷格，所以S0. 同理，划分2中也有一对相邻雷格. 注意到划分1中，位于同一区域的两个 格在划分2中位于不同区域. 因此这两对相邻雷格不同. 从而S1. 到此已与两 种假设均矛盾，因此假设不成立，即(B,J,S)(0,0,0)或(0,0,1). 再证明li8(n2+1)-3， 即(B,J,S)(1,0,0). 用反证法， 假设(B,J,S)=(1,0,0). 不 妨设位于边界的雷在(k,1). 将所有边角格去掉后使用划分1，形成n2个区域. 由 31 于S=0，每个区域中必恰含一个雷；并且为了没有雷与(k,1)相邻，(k-1,2)、(k,2)、 (k+1,2)应均不是雷. 但这三个格中已包含一个区域，这自相矛盾. 因此假设不成 立，即(B,J,S)(1,0,0). 所以li8(n2+1)-4， 在(B,J,S)=(0,0,2)时取到. 事实上， 当所有位于偶数行、 偶数列的方格是雷，并且格(3,2)是雷时，可以取到该最大值（此时相邻雷格对只 有(2,2)与(3,2)、(3,2)与(4,2)）. 综上，n=1时，最大值为11；n2时，最大值为8n2+4. (2) 若使得存在一张含有q个雷格且没有填有0的数字格的nn方格表的 正整数q的最小值为qmin，则kmax=qmin-1. 注意到，一张方格表中没有0，当且仅当其中的每个格子都满足：其本身是 雷或其与至少一个雷相邻. 记S=(i,j)|ij1(mod3)， 则 2 3 2 n S. 对于(i,j)S， 记(i,j)及与其相邻 的所有格组成的集合为S(i,j). 易知任两个S(i,j)的交集为空. 由于S中任意两格 都不相邻，也不能与同一个雷相邻，而(i,j)应满足：其本身是雷或其与至少一个 雷相邻，所以每个S(i,j)中必至少存在一个雷. 即q|S|. 为使q可以取到该最小值， 只需在n1(mod3)时， 令每个满足ij1(mod3) 的(i,j)是雷；而在n0(mod3)或n2(mod3)时，令每个满足ij2(mod3)的(i,j) 是雷. 容易验证此时q=|S|，且方格表中没有数字0.从而qmin= 2 3 2 n . 所以kmax=qmin-1=1 3 2 2 n . C 9（陈楷）（陈楷） 设有7种颜色 1 a， 2 a， 7 a和一个nn的方格表开始时按照国际象棋 的规则将每个方格染为 1 a或 7 a每一次操作允许将其中任意一个22的小方格 表中的方格按如下法则改变颜色： 将 1 a改为 2 a， 2 a改为 3 a， ， 7 a改为 1 a 问： 对怎样的n，能经过若干次操作，使得方格表中原来的 1 a色的格全变为 7 a色， 7 a 色的格全部变为 1 a色 解：解：设颜色为i的方格记为i型方格，i1，2，3，7由题意可知，一 个方格改变7次颜色就变回原来的颜色所以将1型方格变为7型方格，需要 76k 次操作，将7型方格变为1型方格需要71m次操作所以，设1型方格 有a个，7型方格有b个，则一共需要对1型方格变色76sa次，对7型方格变 色7tb次 而在初始的每个22的小方格中，1型方格和7型方格数是相等的， 所以颜色改变的总次数相等，所以有 767satb， 从而 7()absat， 这表明ab是7的倍数，所以 2 7|7|nn，即n是7的倍数 当n是7的倍数时， 给出构造 先将nn的方格表分为若干个7 7的小方格 表，只需考虑7 7的结果即可 32 1 -2 3 3 -2 1 -2 4 1 1 4 -2 3 1 2 2 1 3 3 1 2 2 1 3 -2 4 1 1 4 -2 1 -2 3 3 -2 1 上表是一个6 6的表满足边界小方格相邻两个的和为1、1相邻， 内部每个 22的和为1或1， 且1和1相邻 每个小方格中的数对应了7 7方格表的对 应位置的22的变色次数模7的余数于是可得到下表： 1 5 3 3 5 1 5 4 1 1 4 5 3 1 2 2 1 3 3 1 2 2 1 3 5 4 1 1 4 5 1 5 3 3 5 1 这个是每个对应位置的22变色次数，于是可以得到每个7 7小方格变色次 数： 1 6 8 6 8 6 1 6 15 13 8 13 15 6 8 13 8 6 8 13 8 6 8 6 8 6 8 6 8 13 8 6 8 13 8 6 15 13 8 13 15 6 1 6 8 6 8 6 1 这个是四个角上均为 7 a色的情形 四角均为 1 a时， 只需将第一个表中的数均 乘以1，按同样的方法即可得到 33 C 10（胡郁郁）（胡郁郁） 国王有一天闲的无聊， 抓了10个囚犯过来玩游戏， 他将把10个囚犯分开关在 10间小黑屋里，小黑屋里看不到也听不到外界，也不知道时间国王过一阵时间 会放一个囚犯进院子里，院子里有一盏灯，囚犯可以把它点亮或者点灭，然后国 王再把他关回去如果有一天某个囚犯能证明：所有的囚犯都出来过，那么国王 就把他们放了，证明错误就会集体被杀掉国王可能会选重复的人出来，比如先 连点5次一号，而且国王可能会隔很久再点一个人囚犯游戏前有10分钟讨论的 机会，游戏前不知道灯最初是亮的还是灭的 问：囚犯们应该讨论怎样的对策才能保证自己能自由？ 解解：指定1号囚犯出来以后负责点灯，如果灯是灭的就点上，如果灯是亮的 就不管；210号囚犯负责灭灯，如果灯是灭的就不管，如果灯是亮的就灭掉并 且210号囚犯每人最多熄灭两次 当1号囚犯点亮了18次灯后， 他可以证明所有 人都到过院子 证明如下： 如果刚开始的时候灯是亮的，当1号囚犯点亮了18次灯后，必然是210号每 人出门2次，所有人都到过院子 如果刚开始的时候灯是灭的，当1号囚犯点亮了18次灯后，必然是210号中 的8个人出门2次，1个人出门1次，所有人都到过院子 :Ps这道题关键在于每个人要拉两次灯， 如果只是拉一次，1号囚犯是无法证明都 出来过的，比如如果他点亮了9次就去找国王，有可能当初始的灯是灭的，210 号只有8个囚犯出来过；如果他准备点亮10次再去找国王，那么当初始的灯是亮 的，210号全出来过，此时1号点亮了9次，他这辈子也不会等到点第10次灯的 时候了 C 11（胡郁郁）（胡郁郁） 甲乙两人作游戏， 甲先在纸上任意写下一个由LR、构成的长为n的序列， 然 后乙将n个质量互不相同的砝码逐一放在天平上，每放一个砝码（已放的砝码不 再拿下） ， 乙都在纸上按顺序写一个字母： 如果天平倾向左边则写L， 否则写R 当 所有砝码都放在天平上时，乙也写下一个由LR、构成的长为n的序列规定：当 乙写的序列与甲写的序列相同时乙胜，否则甲胜试问：谁有必胜策略？ 解解：乙有必胜策略 记n个砝码的质量依次为 12n aaa 记甲写的序列为A下面证明：乙有办法写下序列A 不妨设A的最后一顶为L，且n为偶数 乙的策略满足如下要求： （1）任何时刻天平上砝码的下标都是连续的自然数； （2）偶下标砝码放在天平的左边，奇下标砝码放在天平的右边 由以上两点知，任何时刻天平总是倾斜向含有最重砝码的那一边 此外，还满足： （3）序列从某项到下一项改变字母 天平从某个砝码到加下一个砝码改变倾斜方向 新放的是一个比已放的都重的砝码；序列从某项到下一项不改变字母 天平从某个砝码到加下一个砝码不改变倾斜方向 34 新放的是一个比已放的都轻的砝码 这样一来，乙可按下述规则将砝码排列顺序：从最后一项开始逆向往前排， 当排列右起第i（1in ）个砝码时，如果序列A的右起第i项与它左边一项不 同 ， 则 排 剩 下 的 最 重 的 砝 码 ， 否 则 ， 排 剩 下 的 最 轻 的 砝 码 （ 如 ALRRLLL， ， ， ， ，则砝码排列的顺序是 453621 aaaaaa， ， ，） 现在，按从左向右的顺序依次将砝码放在天平上，且下标为偶数的砝码都放 在天平的左边，下标为奇数的砝码都放在天平的右边，则此放法对应写下的序列 恰好为A C 12（李卓伦）（李卓伦） 设 * , n kN，简单图G有n个顶点，并且最长路径（圈不算，路径的顶点数 比边数多1）长度为k(指边数)证明：G中至多有 2 k n 条边 证明证明：对顶点数应用数学归纳法，奠基显然设顶点数小于n时命题成立， 则顶点数为n时： （1）若有某个定点度数小于等于 2 k ，那么去除掉最小度数的点，至多去除 了 2 k 条边，则由归纳假设： 1 222 kkk E Gnn （2）假设所有顶点的度数均大于 2 k ，首先找一个长度为k的路径 012 , k v v vv，则 0 v仅与 1 v至 k v中的点相邻， k v仅与 0 v至 1k v 中的点相邻不妨 设这条路径是从左至右的（ 0 v至 k v） 考虑与 0 v相邻的点，如果这些点中每个点 的左邻点均不与 k v相邻，则至少有 0 d v个点在 011 , k v vv 中与 k v不相邻，也即 0k d vd vk，与假设矛盾故存在 i v使得 0 v与 i v相邻， 1i v 与 k v相邻，则这 1k 个点构成圈:C 012110ikki vvvvvvvv ， 因此，/G C中任意一点均不与C中的任一点相邻，则 1 1 222 k kkn k E Gnk C 13（来章润，肖佳劼）（来章润，肖佳劼） 某个国家有k个省份，每个省份分别有 12 , k a aa座城市，现计划在这些城 市间建立一些（双向）航线，使得从任一城市出发都可以都可经一条或多条航线 抵达其它任何城市若同一省份的城市之间不设航线，又要求总共的航线数尽可 能少，问有几种不同的航线设计方法？ 解：解：令 12k naaa，用1,2,Sn来表示所有城市，其中 11 1,2,Aa， 21112 1,2,Aaaaa， 12112 ,1, kkk Aaaaaaa 35 分别代表第1,2,k个省份的所有城市 易知，最少航线数必为1n，对任一组符合要求的航线，每个城市必至少有 一条航线，且至少有两个城市恰有一条航线经过，记这些城市中对应数字最小的 为b，设 i b