《高中数学竞赛》组合计数“续1”

1、第二十讲组合计数“续1”精讲例1数1447, 1005和1231有某些共同点，即每个数都是首位为1的四位数，且每个 四位数中恰有两个数字相同，这样的四位数共有多少个？（第1届aime试题，1983年） 【解】符合条件的四位数必含有一个1或者两个1.（1）含有两个1的情形从除1之外的其余9个数字中任取两个，有c）种取法，再与其中的一个1组成任意排 列的三位数，有p,种，这样构成的首位为1的四位数共有ni= c29 p?（个）.（2）只含有一个1的情形从其余的9个数字中任取两个，有c?9种取法，其中一个数字被重复选出，有c,种， 这样的三个数字组成的三位数共有吃，这样构成的首位为1的四位数共有 2

2、c；c；f因此 符合题意的四位数共有n=ni+n2=432 （个）.例2在xy平面上，顶点的坐标（x,y）满足1wxw4, lwyw4,且x ,y是整数的三角 形有多少个？（第44届ahsme试题，1993年）【解】由题设知，在xy平面上有16个整点，共有c316=560个三点组，要从中减去那些 三点共线的.平面上有4条垂直线和4条水平线，每条上有4个点，这8条线上含有8c?=32个三点 共线的三点组（如图i331）.图i 3 31图1-3-3-2类似的，在斜率为±1的线上三点共线的三点组有2c43+4c33=8+4=12 （个）（如图13 32）.此外，没有其他的三点共线的三点组，

3、所以，组成的三角形的个数是 560-32-12=516 （个）.例3方程2xi+x2+x3+xl0=3有多少个非负整数解.【解】设（xi,x2,xio）是原方程组的一个非负整数解，由于x&o （i=l,2, 10）, 因此，2x 1w 2x |+x2+x3+x4+x5+x6+x7+x8+x9+x |（）=3即2xiw3,所以xi=o, 1.下面分两种情形：（1）x=0,则 x2+x3+x|（）=3,所以 xi 二 0,1,2,3 （i=2, 3,10）.如果有某个xj=3,贝康他xi=0,这样解有0*9=9 （个）.如果某个焉工3,若某个xi=2,则必有一个 沪1, ihj, 2wi,

4、jw9,这样解有c0c*8=72 （个）.如果对每个&h2, 3,则xz，,xio中必有三个xi（2wiw10）为1,这样解有c93=84 （个）（2）x=l,则 x2+x3+x1o=1,因此 x1，x2, x3x10 中仅有一个是 1，这样解有 c*9=9 （个）.于是原方程组有c； + c c； += 174个非负整数解.例4设s=1, 2,，】, a为至少含有两项的、公并非为正的等差数列，其项部都 在s中，且添加s的其他元素等于a后均不能构成与a有相同公差的等差数列，求这种a 的个数（这里只有两项的数列也看做等差数列）.（全国高中数学联赛，1991年）【解】构造具有如下要求的集合

5、a：把a中的元素按从小到大的次序排好后，在其最大 元素后面添上s的任何元素均不能构成具有原公差的等差数列。这时，当a的首项与公差一 旦确定，其整个集合a也即确定，不妨设a的首项为a,公差为d,则a=l, d=l, 2, , n 1 时的集 a 有 n1 个；a=2,d=l,2, -,n-2 时的集 a 有 n-2 个;a= n 1, d=l时的集a有1个.因此 所求a的总个数为1 +2+ （n-1）二巴匸12.2例5在扔硬币时，如果用z表示正面朝上，f表示反面朝上，那么扔硬币的序列就表 示为用z和f组成的串，我们可以统计在这种序列中正面紧跟着反面（zf）的出现次数，正 面紧跟着正面（zz）的出

6、现次数，例如序列zzffzzzzfzzffff是15次扔币的结果，其中有5个zz, 3个zf, 2个fz, 4个ff.问：有多少个15次扔硬币的序列，恰好有2个z乙3个zf, 4个fz, 5个ff?（第4届aime试题，1986年）【解】符合题意的序列具有如下两种可能形式：（1）f带头的：ffzzf；（2）z带头的：zzffzzff.由于题设要求的序列恰有3个zf,则序列属于第（ii）类的，应具有如下形式zzffzzffzzff.其中只有2个fz,达不到4个fz,故不可能，所以符合题设的序列只能是第（i）种形 式.市于序列恰有4个fz,则在考虑序列中恰有两个zz的情况下可分为如下两类： zzz

7、 z z z, zz zz z z.以及z的不同位置，其中的空格之处应填f.设每个空格处填f的个数依次为x,x2,x3,x4,则x + x。+ x3 + x4=9这相当于求其正整数解的个数，显然有c38=56.另一方面，对于，zzz的位置有4种，对，zz, z乙乙z的排列方法有6种，所以z的排列方法有10种.所以，符合题意的序列有10x56=560 (个).例6 aabc的顶点为a= (0, 0), b二(0, 420), c= (560, 0), 一个骰子的六个面 分别标上两个“a”，两个“b”，两个“c” .从aabc内部选出一点pl (k , m),重复扔骰 子，依下列法则选出点匕，p3

8、,：如骰子露出标记l的那面lea, b, c,且刚刚选为 pn，那么pn+i选为丑 的中点,已知p7=(14, 92),问k+m=?(第11届aime试题，1993年)【解】首先应注意到因pi在aabc内，则以后的所有在aabc内.下面，我们将证 明一旦任何后继的pk给出，则可惟一地确定p】.假定pk=(xk,yk)，因pk在aabc内,则有0<xk<560,0<yk<420,0<420xk+560 yk<420 560.若掷出a,贝i(兀如九+1)= e+i寸,(图i333中的一部分)，显于是pk+i所在的可能范围被限制在原三角形的丄之内4然pk+i在i内

9、，从而有1420xk+1+560yk+1< - x 420 x 560.2同样掷出b,则pk+i在ii内，yk+i>210.若掷出 c,则 pk+i 在iii内，xk+1>280.所以，对k$2, pk必在i, ii, iii之一内，且由它的前一点惟一确定.例如，若pk(xk,yq，位于ii内，则pk必为bpk-i的中点,这时 pk-j=2pk-b=(2 xk,2yk-420).图i一3-3-3所以,若 km2, pk二(xk,yq，有(2耳,2儿 一 420),若儿 > 210,2xk 一560,2儿),若耳 >280,(2林,2儿),若420林 +560儿 v

10、 1x420x560.、 2下面，我们可以由p7推出p|：p7=(14, 92) =>p6= (28, 184) =>p5= (56, 368) =>p4= (112, 316)=p3= (224, 212) np尸(448, 4)(336, 8). k+m 二336+8=344.例7 已知定义在非负整数集上的函数f(n)由下列条件确定：f(0)=0, f(l)=0, f(2n)=2f(n)+1 (n>0)及 f(2n+l)=f(2n) 1,求最小正整数 m,使 f(m)=21990+l.【说明】本题的函数由递推关系给出，由递推关系求出函数表达式往往不是一件容易的 事，

11、通常情况下，求自变量为某一值时的函数值，只要按递推关系式计算而不必求出函数关 系，可现在的问题是已知函数值，要求自变量的最小正整数值，问题就显得难了，复杂了， 在此我们可直接借助于递推关系而避开求函数表达式的麻烦.【解】因为f(2n)=2f(n)+l,f(2n+1 )=f(2n) 一 1 =(2f(n)+1)-1 =2f(n)所以偶数的函数值为奇数，奇数的函数值为偶数.因为 2|990+1 是奇数，而 f(m)=2l990+l,所以m为偶数，可设m=2np贝uf(m)=f(2n j )=2f(n 0+1=21990+1,得 f(ni)=2i989,k而可知 rij 是奇数，可设 ni=2n2+

12、l,w'j f(ni)=2f(n2)=21989, f(n2)= 21989,而可知ri2是奇数,可设n2=2n3+l,可得关系式 m=2nhf(ni)=2,989, i)i=2n2+l, f(n2)= 21989,nk=2nk+hf(nk+1)= 21989 4,ni988=2n】998+1 ,f(ni989)=2因为 f(0)=l,f(l)=0,f(2n)=2f(n)+l, f(2n+l)=f(2n)-l, n>0. 所以当时，f(2xl)=2f(l)+l=l,f(2x 1+1 )=f(2x 1) -1=1 -1 =0. 当n=2时,f(2x2)=2f(2)+1 =2x 1+1 =3, f(2x2+1 )=f(5)=f(4) -1=3-1=2.因为满足f(ni989)=2的最小正整数是n989=2x2+1=5仝 3 2 1,递推而上可知 =111988=2 111989+1=2x5