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

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

nkknnk?0 当x=r时亦成立：?1?r??????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整除，于是 n?i?pi?k?ri，（i=1，2，?k）

其中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}

, 两边被(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

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

????种选择，??2???2?6。现有7列，?6??2。即必有2列在相同的两行选择相同的数字，

????即有一巨形，四角的数字相等。

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

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

?????222成n?1?a，则新幻方的每行每列的数字之和为nn?1?nn?1/2?nn?1/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?x????1?c?n?k?1,k?xk，所以命题得证

kk?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个点落在同一个小等边三角形内，它们的距离不大于小等边三角形

的边长1/3

更多课程资料请到大学课程网www.0206.cc学习