我们就证明了:任取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组合与构造
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)