我们就证明了：任取11个点，一定存在两个点，它们之间的距离严格小于1。（这样的抽屉构造也是不唯一的）
2013B四、（本题满分50分）用若干单位小正方形和由三个单位小方格组成的 形“砖”铺满一个2?n的方格棋盘的所有不同可能铺法的数目是Tn．下面的图是n?3时的两种不同的铺法：
⑴求T10；
⑵求T2013的个位数．
★证明：由题意显然T1?1，T2?5，
当n?3时，我们从左向右地铺2?n的方格棋盘，无论哪一种铺法，至多铺到2?3，我们一定会完成一个2?k（k?1,2,3,）的矩形。这样我们计算Tn时，就可以去寻找与Tn?1,Tn?2,Tn?3的关系，又由下图
我们得到Tn?Tn?1?4Tn?2?2Tn?3
⑴由T1?1，T2?5，得T3?11，T4?33,T5?87,依次下去可得T10?13377
⑵由Tn?Tn?1?4Tn?2?2Tn?3，T1?1，T2?5，T3?11，可知，Tn一定是奇数。我们由mod5计算T2013，对每一个Tn，我们有：
(T1?1,T2?0,T3?1,T4?3,T5?2,T6?1,T7?0,T8?3,T9?0,T10?2,T11?3,T12?1,
T13?2,T14?2,T15?2,T16?4,T17?1,T18?1,T19?3,T20?4,T21?3,T22?0,T23?0,
T24?1,)T25?1,T26?0,T27?1,T28?3,T29?2,T30?1,…
可知，Tn的个位数的周期是24。而2013?21?mod24?，又mod5等于3的奇数mod10也一定等于3，所以T2013的个位数为3。
2012A三、（本题满分50分）设P0,P1,P2,,Pn是平面上n?1个点，它们两两间的距离的最小值为
d(d?0)，求证：P0P1?P0P2?dP0Pn?()n(n?1)!
3★证明：证法一:不妨设P0P1?P0P2?显然, P0Pk?d??P0Pk?0Pn.先证明:对任意正整数k,都有Pdk?1 3dk?1对k?1,2,,8均成立,只有k?8时右边取等号……10分 3d所以,只要证明当k?9时,有PP?k?1即可. 0k3dd(i?0,1,2,,k)P以P为圆心,为半径画个圆,它们两两相离或外切;以圆心，为PP?k?1i00k22半径画圆，这个圆覆盖上述k?1个圆‥‥‥‥‥‥‥20分
d2d2d所以?(PP?)?(k?1)?()?PP?(k?1?1)‥‥‥‥‥‥‥30分 0k0k222由k?9易知所以P0Pk?k?1?1?2k?1‥‥‥‥‥‥‥‥‥‥‥‥‥‥40分 3dk?1对k?9时也成立. 3dP?k?1. 综上,对任意正整数k都有P0k3dnP?PP?PP?()(n?1)!‥‥‥‥‥‥‥‥‥‥‥‥50分 因而P01020n3证法二: 不妨设P0P1?P0P2?以Pi(i?0,1,2,?P0Pn.
,k)为圆心,
d为半径画k?1个圆,它们两两相离或外切; ‥‥‥10分 2设Q是是圆Pi上任意一点,由于
P0Q?P0Pi?PQ?P0Pi?id13?P0Pk?P0Pk?P0Pk‥‥‥‥‥‥‥‥‥‥20分 2223P0Pk为半径的圆覆盖上述个圆‥‥‥‥‥‥‥‥‥30分 23d2d2故?(PP)?(k?1)?()?PP?k?1(k?1,2,,n)‥‥‥‥‥‥‥‥‥40分 0k0k223dn所以PP?PP?PP?()(n?1)!‥‥‥‥‥‥‥‥‥‥‥50分 01020n3因而,以P0为圆心,
2011A四、（本题满分50分）设A是一个3?9的方格表，在每一个小方格内各填一个正整数．称A中的一个m?n(1?m?3,1?n?9)方格表为“好矩形”，若它的所有数的和为10的倍数．称A中的一个1?1的小方格为“坏格”，若它不包含于任何一个“好矩形”．求A中“坏格”个数的最大值． ★解析：首先证明A中“坏格”不多于25个．
用反证法．假设结论不成立，则方格表A中至多有1个小方格不是“坏格”．由表格的对称性，不妨假设此时第1行都是“坏格”．
设方格表A第i列从上到下填的数依次为ai,bi,ci,i?1,2,?,9． 记Sk??a,Tii?1kk??(bi?ci),k?0,1,2,?,9，这里S0?T0?0．
i?1k我们证明：三组数S0,S1,?,S9；T0,T1,?,T9及S0?T0,S1?T1,?,S9?T9都是模10的完全剩余系．
事实上，假如存在m,n,0?m?n?9，使Sm?Sn(mod10)，则
i?m?1?ani?Sn?Sm?0(mod10)，
即第1行的第m?1至第n列组成一个“好矩形”，与第1行都是“坏格”矛盾．
又假如存在m,n,0?m?n?9，使Tm?Tn(mod10)，则
i?m?1?(bni?ci)?Tn?Tm?0(mod10)，
即第2行至第3行、第m?1列至第n列组成一个“好矩形”，从而至少有2个小方格不是“坏格”，矛盾．
类似地，也不存在m,n,0?m?n?9，使Sm?Tm?Sn?Tn(mod10)． 因此上述断言得证．故
?Sk?09k??Tk??(Sk?Tk)?0?1?2???9?5(mod10)，
k?0k?099所以
?(Sk?09k?Tk)??Sk??Tk?5?5?0(mod10)，
k?0k?099矛盾！故假设不成立，即“坏格”不可能多于25个．
另一方面，构造如下一个3?9的方格表，可验证每个不填10的小方格都是“坏格”，此时有25个“坏格”．
综上所述，“坏格”个数的最大值是25．
2011B四、（本题满分50分）给定n个不同实数，其所有全排列组成的集合为An.对于
1 1 1 10 1 1 1 1 2 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 10 1 (a1,a2,,an)?An，若恰有两个不同的整数i,j?{1,2,,n?1}使得ai?ai?1,aj?aj?1成立，则称
该排列为“好排列”.求An中“好排列”的个数. ★解析：首先定义：
对于A中的一个排列?a1,a2,?,an?，如果满足a1?a2???an，则称该排列为自然排列；
1,2,?,n?1?，使得ai?ai?1则称ai和对于A中的一个排列?a1,a2,?,an?，如果有整数i??ai?1构成一个“相邻逆序”；
对于?a1,a2,?,an??A，如果它恰有一个“相邻逆序”，则称该排列为“一阶好排列”，A中所有“一阶好排列”的个数记为f1(n)；如果它恰有两个“相邻逆序”，则称该排列为“二阶好排列”，
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），其次求f1(n)。
我们先来考察f1(k?1)与f1(k)之间的递推关系。
对Ak?1中的每一个“一阶好排列”（记为a），我们考虑从中取出最大的数ak?1后剩下的k个数
a1,a2,?,ak按原来的顺序构成的排列（记为b）。
如果排列b是Ak中的“一阶好排列”，且“相邻逆序”为ai?ai?1，那么，在排列a中，ak?1的位置只能在ai,ai?1之间或最后；
如果排列b不是Ak中的“一阶好排列”，则排列b中的“相邻逆序”的个数不为1，显然排列b中“相邻逆序”的个数不能大于1（否则，排列a不是“一阶好排列”，理由是：因为ak?1是最大的数，所以排列a中“相邻逆序”的个数一定不少于排列b中“相邻逆序”的个数），从而排列b中“相邻逆序”的个数为0，此时排列b是一个自然排列，而排列a是“一阶好排列”，所以ak?1的位置不能在最后（有k种可能的位置）。
综合上面的分析可知：f1(k?1)?2f1(k)?k，即f1(k?1)?(k?1)?1?2?f1(k)?k?1?， 所以f1(n)?n?1?4?2最后求f2(n)。
我们先来考察f2(k?1)与f2(k)之间的递推关系。
对Ak?1中的每一个“二阶好排列”（记为c），我们考虑从中取出最大的数ak?1后剩下的k个数
n?2，即f1(n)?2?n?1。
na1,a2,?,ak按原来的顺序构成的排列（记为d）。
如果排列d是Ak中的“二阶好排列”，且“相邻逆序”为ai?ai?1，aj?aj?1，那么在排列c中，ak?1的位置只能在ai,ai?1之间或aj,aj?1之间，或者排在最后；
如果排列d不是Ak中的“二阶好排列”，则它一定是Ak中的“一阶好排列”，设“相邻逆序”为ai?ai?1，因为排列c是“二阶好排列”，所以ak?1的位置不能在ai,ai?1之间，也不能排在最后，其余位置都行，有k?1种可能。
1981-2018年全国高中数学联赛真题分类汇编含解析答案16组合与构造
