《组合数学》测试题含答案

y２)，(x3, y3)}中必有２个格点的y坐标的奇偶性相同，不妨设y1, y2均为奇数。于是格点(x1, y1)和(x２, y２)的中点M的坐标为（Mx ，My)，其中Mx＝ (x２－x1)/2，My＝(y２－y1)/2，因为x１和x２均为偶数，y1和y2均为奇数，所以Mx和My均为整数，也就是说点M是格点。

17. 证明：假设符合条件的字符串集合为A，其中的字符串个数为an。设由0、1、2组

成的长度为n的字符串中０出现奇数次的字符串个数为bn，那么，根据字符串最后一位为０或１或２将A中字符串分类，若最后一位是１或２，则共有２an－1个，若最后一位是０，则前n－1位中必有奇数个０，故有bn－1个，于是

n－1n－1

an＝２an－1＋bn－1，但an－1＋bn－１＝３，所以，bn－１＝３－an－1，于是

n－1n－1n－２

an＝an－1＋３，即an－an－1＝３，由此知an－１－an－２＝３，也就是3an－１－3an－２

n－1２

＝３，于是有an－4an－1＋3an－２＝0，其特征方程为x－4x＋3＝０，解此方程得：

nn

α１＝１，α２＝３，所以an＝A11＋A23，而a１＝２，a２＝５，于是有 A1＋３A2＝２ A1＋９A2＝５ 解得 A1＝1/2 A2＝1/2

n

所以an＝（３＋１）／２

18. 证明：因为从n＋r个不同的物品中任取r个的方案数是

C（n＋r，r）＝（n＋r）（n＋r—1）．．．（n＋r－r＋1）／r! ＝（n＋１）（n＋２）．．．（n＋r）／r! 它是一个整数，所以（n＋１）（n＋２）．．．（n＋r）必能被r!整除。 19. 证明： 因为已知C（n，l）C（l，r）=C（n，r）C（n-r，l-r）即

C（m，n）C（n，r）=C（m，r）C（m-r，n-r）,所以 左端

=C（m，0）C（m，n）＋C（m，1）C（m-1，n-1）＋．．．＋C（m，n）C（m-n，0） ＝C（m，m）C（m，m-n）＋C（m，m-1）C（m-1，m-n）＋．．． ＋C（m，m-n）C（m-n，m-n） ＝C（m，m-n）C（m-（m-n），m-（m-n））＋C（m，m-n）C（m-（m-n），m-1-（m-n）） ＋．．．＋C（m，m-n）C（m-（m-n），m-n-（m-n）） ＝C（m，n）C（n，0）＋C（m，n）C（n，1）＋．．．＋C（m，n）C（n，n）

n

＝C（m，n）（C（n，0）＋C（n，1）＋．．．＋C（n，n））=C（m，n）2=右端 故命题得证。

20. 证明：将３n个人排成n行，每行３人，不分左中右，则排列方案数为

C（3n，3）·C（3n-3，3）·．．．·C（3，3），其中C（3n，3）为第１行的可能方案数，C（3n-3，3）为在剩余3n-3个人中任取３人站在第２行的方案数，．．．，C（3，3）为最后３个人站在第n行的方案数，因为必须为每一行确定人选，故用乘法法则，由于 C（3n，3）·C（3n-3，3）·．．．·C（3，3） ＝［（3n）（3n-1）（3n-2）／３！］［（3n-3）（3n-4）（3n-5）／３！］．．．［３·２·１/３!］

nnn

＝（3n）!／（3!）是方案数，它必为整数，所以（３n）!／（２３）必是整数。 21. 证明：设任给的５个数为a1，a２，a３，a４，a５，将它们除以３得到的余数分别是

r1，r２，r３，r４，r５，即ai＝３Mi＋ri（i＝１，２，３，４，５），因为除以３的余数只可能是０或１或２，所以如果r1，r２，r３，r４，r５是相同的，则任取其中３个，比如r1，r２，r３，则a1＋a２＋a３＝３（M１＋M２＋M３）＋３r1，必能被３整除。如果r1，r２，

31 / 35

《组合数学》测试题含答案

r３，r４，r５中有３种余数，比如r1＝０，r２＝１，r３＝２，则a1＋a２＋a３＝３（M１＋M

，必能被３整除。还有一种情况是２＋M３）＋（０＋１＋２）＝３（M１＋M２＋M３＋１）

r1，r２，r３，r４，r５，既不是全都相同（只有一种余数），也不是３种余数都出现，而是只有２种余数，那么，根据鸽巢原理，这５个余数中至少有３个是相同的，比如r1＝r２＝r３＝r，于是a1＋a２＋a３＝３（M１＋M２＋M３）＋３r，它也必能被３整除。综上所述，知任取５个整数中必有３个之和是３的倍数。

22. 证明：设H＝｛h1, h2, …, hk｝是群G的子群，x，y∈G，若xH∩yH=Ф，则命题已证。

-1-1

现设xH∩yH≠Ф，则必存在g∈G，使g∈xH且g∈yH。设g=xhi=yhj,由此知x=ghi,y=ghj，

-1-1

于是对任意的f∈xH，即f＝xhk＝ghihk，由于H是子群，hi，hk∈H，所以hihk∈H，可

-1

令hihk＝hp∈H。于是f＝g hp＝yhj hp＝yhq∈yH，因而知xH是yH的子集。反过来，对

-1-1-1

任意的u∈yH，即u＝yhl＝ghjhl，由于H是子群，hj，hl∈H，所以hjhl∈H，可令hjhl＝hs∈H。于是u＝g hs＝xhi hs＝xht∈xH，因而知yH是xH的子集。从而xH=yH。 23. 证明：T中元素（x，y，z）满足条件x，y，z∈{1，2，…，n+1}，x

所以z的取值只能是2，3，…，n+1。当z取值i+1时，x，y的取值范围均为1，2，…，

2222222

i。于是共有i个（x，y，i+1），所以|T|=1+2+…+n。令|T|=Sn，则Sn＝1+2+…+n，

2

Sn－Sn－１＝n，于是可设Sn＝A0C（n，0）＋A１C（n，1）＋A２C（n，2）＋A３C（n，3），已知S０＝０，S１＝１，S２＝５，S３＝１４，所以有 S０＝０＝A0 S1＝1＝A0＋A1

S2＝5＝A0＋2A1＋A2

S3＝14＝A0＋3A1＋3A2＋A3 解得

A0＝０，A1＝１，A2＝３，A3＝２，

所以 |T|=Sn= C（n，1）＋３C（n，2）＋２C（n，3）

2

＝n+3n（n-1）/2+2n（n-1）（n-2）/3＝n（2n+3n+1）/6＝n（n+1）（2n+1）/6 而C（n+1，2）＋2C（n+1，3）＝n（n＋1）/2+2（n+1）n（n-1）/3! ＝n（n+1）（3+2n-2）/6＝n（n+1）（2n+1）/6

222

所以|T|=1+2+…+n＝C（n+1，2）＋2C（n+1，3），命题得证。

24. 证：设K个相继的正整数为n＋1，n＋2,…,n＋K,从这n＋K个不同的正整数中选取r

?n?k?!??n?k??n?k?1???n?k??r?1??为正整?k个正整数的方法数是n,即N=rr!?n?k?r?!r!??数，即分子有r 个相继正整数之积为r！的倍数，当然亦为r的倍数，证毕。 25. 证：利用组合数二分性质得： ???2n?2???n?1???n?1???2n?1??2n?1???????????n?????n?1?? n?1n?1??????????n?1??n???n?1??n??????n?1?? n????2nn2nn?12nn =?? =

???????????????

2nn?1 =

???2?????。

2nn?12nn2nn?126. 证：由二项式定理知，?1?x???nnk?0??xnkk

32 / 35

《组合数学》测试题含答案

当x=2时：3??2nk?0???2nkk

n 当x=r时亦成立：?1?r?n??k?0???rnkk

（二项式定理中x与y均为实数）。

27. 证明：A?B?C??A?B??C?A?B?C??A?B??C =A?B?A?B?C??A?C???B?C?

=A?B?C?A?B??A?C?B?C?A?C?B?C? =A?B?C?A?B?A?C?B?C?A?B?C 证毕。

28. 证：设k个相继正整数为n+1,n+2,…,n+k.

若不然这k个相继正整数都不能被k整除，于是

（i=1，2，…k） n?i?pi?k?ri，

其中pi为正整数，ri为余数，且1?ri?k?1，（i=1，2，…k）显然k个余数ri只能取k－1个值，由抽屉原理知，必存在m,?,且n?1?m＜?＜n+k使rm?r?，从而?n?????n?m???p??pm??k，即正整数??m??p??pm??k，显然n+1≤??m?n?k,且p??pm亦为整数，于是证毕。

29. 证明：把1～2n分成以下n组，即｛1，2｝，｛3，4｝，…｛2n－1,2n｝。由题设这n 组

有n+1个数，由抽屉原理必有一组至少有两个数，显然是相邻的两个正整数，以下证明这两个相邻正整数互素，不妨设这两个正整数为n与n+1，若不然，不是互等的，那末必有公因子q(q≥2)使n=p1·q，n+1=p2·q。其中p1，p2为整数，于是n+1= p1·q+1= p2·q?（p2－p1）q=1,这与q≥2且p2－p1为整数矛盾，证毕。 30. 证：对n用归纳法。

先证可表示性：当n=0,1时，命题成立。 假设对小于n的非负整数，命题成立。

对于n,设k!≤n＜(k+1)!,即0≤n-k!＜k·k!

由假设对n-k!,命题成立，设再证表示的唯一性：

，其中ak≤k-1,，命题成立。

设, 不妨设aj＞bj,令j=max{i|ai≠bi}

aj·j!+aj-1·(j-1)!+…+a1·1! =bj·j!+bj-1·(j-1)!+…+b1·1!,

另一种证法：令j=max{i|ai≠bi}

33 / 35

《组合数学》测试题含答案

, 两边被(j+1)!除,得余数aj·j!=bj·j!,矛盾.

31. 证：取C(n,k)和C(n,k-1)进行比较。C(n,k)/C(n,k-1)=(n-k+1)/k。 当k>n/2时,(n-k+1)/k<1,即C(n,k)

当k>n/2时,(n-k+1)/k>1,即C(n,k)>C(n,k-1)得到当k为最接近n/2的数时，C(n,k)取到最大值。

32. 证：归纳法：当n=1时,0出现偶数次的字符串有(3+1)/2=2个(即1,2),成立。

k

假设当n=k时,0出现偶数次的字符串有(3+1)/2种。总的字符串有3种。0出现奇数次的字

k

符串有(3-1)/2种。

当n=k+1时，0出现偶数次的字符串包括两部分：

k

n=k时,0出现偶数次再增加一位不是0的，共有2(3+1)/2种，0出现奇数次再增加一位0,

k

共有(3-1)/2种。

kkk+1

所以共有2(3+1)/2+(3-1)/2=(3+1)/2种，证毕。

1

33. 证明：显然，每列中必有两数字相同，共有?有0或1种选择，故共有?????2???种模式，

?3??2??3??2??2。即必有2列在相同的两行选择相同的数字，种选择，??2???2?6。现有7列，??6????即有一巨形，四角的数字相等。

34.一个n阶幻方每行每列的数字之和为：

?3??7??1?2?3????n?/n?n?n222?1/2n?nn2?1/2。如果将幻方中的每个数a换

?????2成n?1?a，则新幻方的每行每列的数字之和为nn?1?nn?1/2?nn?1/2，

?2??2??2?所以仍为幻方。

35.假设将S划分为个有序集合S1,S2,??,Sk，所谓有序集合是指S1,S2,??,Sk，是有序的，于是S中的个n元素每个都有k种选择，所以共有k种划分方法。 36.证明：因为c??n,k????1?c?n?k?1,k?

kn所以1/?1?x???1?x?n?n??c??n,k?xk????1?c?n?k?1,k?xk，所以命题得证

k?0k?0??k 37. 证明：以A表示所取10个点所成之集，则A?10。把边长为1的等边三角形分成9个边长为1/3的小等边三角形，并将其编号，以Ai表示A中属于第i个三角形的点所成之集，则

?Ai?19i?A.由鸽笼原理的简单形式，必有正整数k?1?k?9?，使得Ak?2，这表

明所取10个点中必有2个点落在同一个小等边三角形内，它们的距离不大于小等边三角形

34 / 35

《组合数学》测试题含答案

的边长1/3

更多课程资料请到大学课程网学习

35 / 35