组合数学习题解答

1.证任一正整数n可唯一地表成如下形式:证：对n用归纳法。

先证可表示性：当n=0,1时，命题成立。 假设对小于n的非负整数，命题成立。 对于n,设k!≤n＜(k+1)!,即0≤n-k!＜k·k!

,0≤ai≤i,i＝1,2,?。

由假设对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!,矛盾.

2.证 nC(n-1,r)=(r+1)C(n,r+1).并给出组合意义。

证：组合意义：

等式左边：n个不同的球，先任取出1个，再从余下的n-1个中取r个； 等式右边：n个不同球中任意取出r+1个，并指定其中任意一个为第一个。 显然两种方案数相同。

3.证法放球：

。

证：设有n个不同的小球，A、B两个盒子,A盒中恰好放1个球,B盒中可放任意个球。有两种方

①先从n个球中取k个球(k≥1),再从中挑一个放入A盒,方案数共为盒。

,其余球放入B

②先从n个球中任取一球放入A盒，剩下n-1个球每个有两种可能，要么放入B盒，要么不放，故方案数为n2n-1 .

显然两种方法方案数应该一样。

4.有n个不同的整数，从中取出两组来，要求第一组数里的最小数大于第二组的最大数。问有多少种方案？

解：设取的第一组数有a个,第二组有b个,而要求第一组数中最小数大于第二组中最大的，即只要取出一组m个数(设m=a+b),从大到小取a个作为第一组,剩余的为第二组。此时方案数为C(n,m)。从m个数中取第一组数共有m-1中取法。

总的方案数为.

5.六个引擎分列两排，要求引擎的点火的次序两排交错开来，试求从一特定引擎开始点火有多少种方案。

解：第1步从特定引擎对面的3个中取1个有C(3,1)种取法，第2步从特定引擎一边的2个中取1个有C(2,1)种取法，第3步从特定引擎对面的2个中取1个有C(2,1)中取法，剩下的每边1个取法固定。所以共有C(3,1)·C(2,1)·C(2,1)=12种方案。 6.试求从1到1000000的整数中，0出现了多少次？

解：首先所有数都用6位表示，从000000到999999中在每位上0出现了105次,所以0共出现了6·105次,0出现在最前面的次数应该从中去掉， 000000到999999中最左1位的0出现了105次， 000000到099999中左数第2位的0出现了104次， 000000到009999左数第3位的0出现了103次, 000000到000999左数第4位的0出现了102次, 000000到000099左数第5位的0出现了101次, 000000到000009左数第6位的0出现了100次。 另外1000000的6个0应该被加上。

所以0共出现了 6·105-105-104-103-102-101-100+6=488895次。

7.n个男n个女排成一男女相间的队伍，试问有多少种不同的方案？若围成一圆桌坐下，又有多少种不同的方案？

解：把n个男、n个女分别进行全排列，然后按乘法法则放到一起，而男女分别在前面,应该再乘2,即方案数为2·(n!)2个.

围成一个圆桌坐下，根据圆排列法则，方案数为2·(n!)2/(2n)个.

8.n个完全一样的球，放到r个有标志的盒子,n≥r,要求无一空盒，试证其方案数为入r个不同的盒子，每个盒子可以放任意个球，可以有空盒，根据可重组合定理可得共有

.

证：每个盒子不空，即每个盒子里至少放一个球，因为球完全一样，问题转化为将n-r个小球放C(n-r+r-1,n-r)=C(n-1,n-r)中方案。 根据C(n,r)=C(n,n-r),可得C(n-1,n-r)=C(n-1,n-1-(n-r))=C(n-1,r-1)个方案。证毕。

9.设,p1、p2、?、pl是l个不同的素数，试求能整除尽数n的正整数数目.

解：每个能整除尽数n的正整数都可以选取每个素数pi从0到ai次，即每个素数有ai+1种选择，所以能整除n的正整数数目为(a1+1)·(a2+1)·?·(al+1)个。 10.试求n个完全一样的骰子掷出多少种不同的方案？

解：相当于把n个小球放入6个不同的盒子里，为可重组合，即共有C(n+6-1,n)中方案，即C(n+5,n)中方案。

11.凸10边形的任意三个对角线不共点，试求这凸10边形的对角线交于多少个点？又把所有对角线分割成多少段？

解：根据题意,每4个点可得到两条对角线,1个对角线交点,从10个顶点任取4个的方案有C(10,4)中,即交于210个点。

根据图论知识，每个对角线交点有4个度，每个顶点去掉与相邻两个顶点的连线还有7个度，可以得到

条边

12.试证一整数是另一个整数的平方的必要条件是除尽它的数目为奇数。 证：根据第9题的结论，而

l)，所以乘积为奇数。 证毕。

13.统计力学需要计算r个质点放到n个盒子里去,并服从下列假定之一，问有多少种不同的图象。假设盒子始终是不同的。

(a)Maxwell-Boltzmann假定：r个质点是不同的，任何盒子可以放任意数个. (b)Bose-Einstein假定：r个质点完全相同，每一个盒子可以放任意数个. (c)Fermi-Dirac假定：r个质点都完全相同，每盒不超过一个.

解：(a) 每个质点放入盒子都有n种选择，r个质点共有rn种不同的图案。 (b) 可重组合，共有C(n+r-1,r)种图案。 (c) 一般组合问题，共有C(n,r)种图案。

14.从26个英文字母中取出6个字母组成一字，若其中有2或3个母音，问分别可构成多少个字(不允许重复)？

解：其中有2个母音可构成C(21,4)C(5,2)6!个字。 其中有3个母音可构成C(21,3)C(5,3)6!个字。

, 能被(a1+1)·(a2+1)·?·(al+1)个数整除，

,能被(2a1+1)·(2a2+1)·?·(2al+1)个数整除，2ai+1为奇数(0≤i≤

15.给出组合意义. 解：如图：

的

可看作是格路问题：左边第i项为从点C到点(-1,i)直接经过(0,i)的路径,再到点B的所有路径数。左边所有项的和就是从点C到B的所有路径数即为右边的意义。

16.给出的组合意义。

解：C(n+1,r+1)是指从n+1个元素a1, a2,?,an+1中任取r+1个进行组合的方案数。

左边：若一定要选an+1,则方案数为C(n,r).若不选an+1,一定要选an,则方案数为C(n-1,r).若不选an+1,an,?ar+2,则方案数为C(r,r). 所有这些可能性相加就得到了总方案数。

17.证明:

证：组合意义,右边：m个球,从中取n个,放入两个盒子,n个球中每个球都有两种放法,得到可能的方案数。左边：第i项的意义是一个盒子中放i个,另一个盒子放n-i个,所有的方案数相加应该等于右边。

证毕。

18.从n个人中选r个围成一圆圈，问有多少种不同的方案？ 解：圆排列:共有P(n,r)/r种不同的方案。

19.分别写出按照字典序由给定排列计算其对应序号的算法及由给定序号计算其对应排列的算法。(解略)

20.(a)按照第19题的要求，写出邻位对换法(排列的生成算法之二)的相应算法。 (b)写出按照邻位对换法由给定排列生成其下一个排列的算法。(解略)

21.对于给定的正整数n,证明当

当k>n/2时,(n-k+1)/k<1,即C(n,k)

时，C(n,k)是最大值。

证：取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)>C(n,k-1)得到当k为最接近n/2的数时，C(n,k)取到最大值。

22.(a)用组合方法证明和都是整数. (b)证明是整数.

证：(a)设有2n个不同球放入n个不同的盒子里，每盒两个，这个方案数应该是整数。对2n个球进行排列得到方案数为(2n)!。而把2个球放入同一个盒子里不计顺序，应该把全排列数除掉这些重复计算的次数，n个盒子内部的排列共重复计算了2 次。得到2n个不同球放入n个不同的盒子里，每盒两个的方案数(2n)!/2 若有3n个不同的球,放入n个不同盒子,故同理得(3n)!/(3!)是整数。

(b)有n个不同的球，放入n个相同的盒子里，每盒n个，求方案数，方案数应该是一个整数。按前面(a)的方法，应该得到(n2)!/(n!)n是整数。另外由于n个盒子相同，放入不同的盒子是没有区别的，应该把n个盒子的排列数n!除去。 因此得到(n2)!/(n!)n+1是整数。

23.(a)在2n个球中,有n个相同,求从这2n个球中选取n个的方案数。 (b)在3n+1个球中，有n个相同，求从这3n+1个球中选取n个的方案数.

解：(a) 相当于从n个不同的小球中分别取出m个小球(0≤m≤n)，再从n个相同的小球中取出n-m个小球。

共有方案： C(n,0)+C(n,1)+?+C(n,n)=2n种。

(b)相当于从2n+1个不同的小球中分别取出m个小球(0≤m≤n)，再从n个相同的小球中取出n-m个小球。

共有方案： C(2n+1,0)+C(2n+1,1)+?+C(2n+1,n)种。 24.证明在由字母表{0,1,2}生成的长度为n的字符串中.

(a)0出现偶数次的字符串有个；

(b)，其中.

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

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

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

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

(3k-1)/2种。

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

(b) 等式左边第m项是0出现m次的字符串数，总和就是0出现偶数次的字符串数，右边由(a)得是0出现偶数次的字符串数，两边显然相等。

25. 5台教学机器m个学生使用，使用第1台和第2台的人数相等，有多少种分配方案？ 解：当使用第1台机器的学生为n个时，使用第2台机器的学生也为n,从m个学生中选出2n个使用这两台机器，剩余的学生可以任意使用剩下的机器的组合数为C(m,2n)C(2n,n)(m-2n)3。

所以总的方案数为

26.在由n个0及n个1构成的字符串中，任意前k个字符中，0的个数不少于1的个数的字符串有多少？

解：转化为格路问题(弱领先条件),即从(0,0)到(n,n),只能从对角线上方走,可以碰到对角线,故方案数为C(2n,n)-C(2n,n-1).

27.在1到n的自然数中选取不同且互不相邻的k个数，有多少种选取方案？

解：设从1~n中选取互不相邻的k个数的方案数为g(n,k),若选n，则方案数为g(n-2,k-1),若不选n则方案数为g(n-1,k)。

显然，g(n,k)=g(n-2,k-1)+g(n-1,k).且只有当n≥2k-1时，g(n,k)>0,否则g(n,k)=0. 可给定初始值g(2k-1,k)=1,g(2k-2,k)=0。

28.(a)在5个0，4个1组成的字符串中，出现01或10的总次数为4的，有多少个? (b)在m个0，n个1组成的字符串中,出现01或10的总次数为k的，有多少个？

解：(a)先将5个0排成一列：00000，1若插在两个0中间，“010”，则出现2个“01”或“10”;若插在两端，则出现1个“01”或“10”;要使出现“01”,“10”总次数为4，有两种办法： (1)把两个1插入0得空当内，剩下的1插入1的前面。

(2)把1个1插入0得空当内，再取两个1分别插入两端，剩下的1插入1的前面。 故总方案数为C(4,2)·2+C(4,1)·3=36. (b)m个0产生m-1个空当，

若k为奇数,则必有且只有1个“1”插入头或尾,总方案数为

若k为偶数,总方案数为

1.证明等式

解：...

比较n次方系数即可证。

2.求(1+x4+x8)中x20项的系数. 解：...

分析(x4+x8)k的结构可知仅当k=3,4,5时有x20项

三个系数相加即为所求

3.有红、黄、蓝、白球各两个，绿、紫、 黑的球各3个，问从中取出试问 有多少种不同的取法？ 解：...

用指数型母函数，可得母函数

10个球，

x10系数即为所求。

4.求由A,B,C,D组成的允许重复的排列中 AB至少出现一次的排列数目。 解1：...

A、B、C、D组成的全排列数为 p=n4

不出现AB的字符串的排列数为

特征方程为：

解为：

可设为：

代入初值：

AB至少出现一次的排列为

解二： 至少出现一次AB的字符串的排列数为

特征方程为：

解为：

5.求n位四进制数中2和3必须出现偶次的 数目。 解：...

对符合题设要求的排列如果0可以出现在最高位，则可得母函数：

但是对n位四进制数来说最高位不能为0。

6.试求由a,b,c三个文字组成的n位符号串 中不出现aa图像的符号串的数目。 解：...

设不出现aa的字符串的排列数为an

特征方程为： 解为：

可设为：

代入初值：

代入可得结果

7.证明序列

C(n,n),C(n+1,n),C(n+2,n),...

的母函数为

证明：...

题设中序列的母函数为：

由$4性质3得，上式

8.证明

证明：...

等式的右端相当于从n+m+1个球中取n+1个球的组合。 把这n+m+1个球编号，如果取出的n+1个球中最小编号是一，则得到

C(n+m,n)

如果最小编号是二则得到C(n+m-1,n) 如果最小编号是m则得到C(n,n)。 可证

9.利用

改善 §4(2) 的pn估计式。 解：...

由推导过程知

，

令

求导得

令 即

解得

将x1代入y得

10. 8台计算机分给3个单位，第1单位的分配量不超过3台，第2单位的分配量不超过4台，第3个单位不超过5台，问共有几种分配方案？ 解：...

把单位看成元素，共12个元素 其中 第1单位有3个 第2单位有4个 第3单位有5个

则命题可看成从12个元素中取8个的组合。母函数为：

其中x8项系数为所求

11. 证明正整数n都可以唯一地表示成不同的且不相邻的Fibonacci数之和。即

注意F1=F2=1是相同的Fibonacci数。 证明：...

先证明可表示性

对n用归纳法. 1）当n=1时命题成立

2）设对小于n的正整数命题成立 对于n，存在k，满足设

则

可表示为不相同且不相邻的F数列的和。即

若

则Fk与Fk-1可合并为Fk+1 命题得证。

，

12. 设空间的n个平面两两相交，每3个平面有且仅有一个公共点，任意4个平面都不共点。这样的n个平面把空间分割成多少个不重叠的域？ 解：...

设n个满足条件的平面把空间分成an个域n-1个满足条件的平面把空间分成an-1个域 则第n个平面与这n-1个平面有n-1条交线，且这些两两相交，任三线不共点。

第n个平面被这n-1条线分成个域。可得 设

个域 增加了

解得

13. 相邻位不同为0的n位2进制数中一共出现了多少个0？ 解：...

设符合条件的n位二进制数的个数为hn 这些数中一共有an个0

当n位二进制数最高位为1时,符合条件的n位二进制数的个数为hn-1 最高位为0时，次高位必为1符合条件的n位二进制数的个数为hn-2 即hn是F数列

特征方程为：

解得a、b为2重根。 设

分析上式结构可得：

把n=2代入可解得： 代入an 可得方程组

解得

14. 在Hanoi塔问题中，在柱A上从上到下套着n个圆盘，其编号依次从1到n。现要将奇数编号与偶数编号的圆盘分别转移到柱B和柱C上。转移规则仍然是每次移动一个，始终保持上面的比下面的小。一共要移动多少次？ 解：...

设n为偶数

1）先把n-1个盘通过C移到B 2）把第n个盘移到C 3）把n-3个盘通过C移到A 4）把第n-2个盘移到B

对n为奇数时上述四步仍然成立，但是B、C对调。

其中k(1)=1,k(2)=2,k(3)=5 h(k)为Hanota数列。

可得特征方程： 解得 代入初值可解得

15. 一书框中有m格，每格各放n册同类的书，不同格放的书类型不同。现取出整理后重新放回，但不打乱相同类。试问无一本放在原来位置的方案数应多少？ 解：...

设m层中有k层不在原来的层上，m-k层在原有层上，但是每册都不在原来的位置。

16. 设一矩形ABCD,其中

作C1B1使得AB1C1D是一正方形。试证矩形B1C1CD和ABCD相似。试证继续这过程可得一和原矩形相似的矩形序列。 解：...

把AD看成1

则AB为

同理可得其他矩形相似

17. 平面上有两两相交，无三线共点的n条直线，试求这n条直线把平面分成多少个域？ 解：...

满足条件的n条直线把平面分成an个域，其中n-1条直线分割成的域数为an-1，第n条直线与这n条直线均相交。 被分成n-1+1=n段。

增加的域数为n。 设

解得

18. 在一圆周上取n个点，过一对顶点可作一弦，不存在三弦共点的现象，求弦把圆分割成几部分？ 解：...

n-1个点把圆分为an-1部分，加上第n个点则对于前n-1个点来说，每选取3个点都有3条弦构成一个三角形，而中间的一点和第n点的连线把中间点与第n点间的弦分为两个部分，增加了一个域。而对第n点与其他n-1点的连线有把第1、n-1、n点构成的三角形分为n个域。

所以地推关系为：

可设

代入初值可解得

19. 求n位二进制数相邻两位不出现11的数的个数。 解：...

设n-1位不出现11的个数为an-1

n-2位不出现11的个数为an-2 n位不出现11的个数为an 则

特征方程为

设 代入得

20. 在n个文字，长度为k的允许重复的排列中，不允许一个文字连续出现三次，求这样的排列的数目。 解：...

设所求为ak则

特征方程为 解得

可设

代入初值可解出A、B

21. 求14+24+34+...+n4的和。 解：...

是n的4次方

满足第推关系

设

代入可解得

22. 求矩阵

解：...

由矩阵的结构知

只要求出K(n)即可

可解得

23. 求

解：...

只求

其他两式 同理可解。

，

可设

把初值代入可的方程组：

解得：

24. 在一个平面上画一个圆，然后一条一条地画n条与圆相交的直线。当r是大于1的奇数时，第r条直线只与前r-1条直线之一在圆内相交。当r是偶数时，第r条直线与前r-1条直线在圆内部相交。如果无3条直线在圆内共点，这n条直线把圆分割成多少个不重叠的部分？ 解：...

当r是奇数（>1）时

当r是偶数时

25. 用an记具有整数边长周长为n的三角形的个数。 （a）证明

（b）求序列{an}的普通形母函数。 解：...

I 当n是偶数时

对所有符合条件的ar-3来说，每边增加1各单位，则可构成符合条件的ar。

设短边为a、b，长边为c，则(a+b)-c>=2即a+b-2>c-1，对所有符合条件的ar来说，每边减少1各单位，则可构成符合条件的ar-3

II 当n为奇数时

由I的讨论知，ar比ar-3多了a+b-c=1的三角形。

而这种三角形可知 当 当

个 个

能被2整除时，这种三角形有 不能被2整除时，这种三角形有

(2)

26.

（a）证明边长为整数、最大边长为l的三角形的个数是

（b）设fn记边长不超过2n的三角形的个数，而gn记边长不超过2n+1的三角形的个数，求fn和gn 的表达式。 解：...

（a）l=1时，只有一种可能（即3边都是 长度为1）。

l=2时，有两种可能（即“1，2，2”、 “2，2，2”）。

。

设三角形的3边边长为x、y、z， 且 l=2k+1时

x+y=2k+2时，有k+1种方案，即“1，2k+1”、“2，2k”、...?、“k+1，k+1”。

x+y=2k+3时，有k种方案，即“2，2k+1”、“3，2k”、...?、“k+1，k+2”。

x+y=2k+4时，有k种方案，即“3，2k+1”、“4，2k”、...?、“k+2，k+2”。 ? ? ? ?

x+y=4k+1时，有1种方案，即“2k，2k+1”。 x+y=4k+2时，有1种方案，即“2k+1，2k+1”。

l=2k时

x+y=2k+1时，有k种方案，即“1，2k”、“2，2k-1”、...?、“k，k+1”。 x+y=2k+2时，有k种方案，即“2，2k”、“3，2k-1”、...?、“k+1，k+1”。

x+y=2k+3时，有k种方案，即“3，2k”、“4，2k”、...?、“k+2，k+2”。 ? ? ? ?

x+y=4k-1时，有1种方案，即“2k-1，2k”。 x+y=4k时，有1种方案，即“2k，2k”。

（b）

27. 设

（a）证明 an+1=an+bn+1, bn+1=an+bn （b）求序列{an}与{bn}的母函数。 （c）用Fibonacci数来表示an与bn。 解：...

1）证明

同理可证 3）解

28. 设 F1=F2=1, Fn=Fn-1+Fn-2 （a）证明

（b）证明Fm|Fn的充要条件是m|n。 （c）证明

（d）证明(Fm,Fn)=F(m,n), (m,n)为m,n的最大公约数。 解：...

1）证明

用数学归纳法 I k=2时 成立，即 II 设k=m时成立 则k=m+1时，

用归纳假设 由I、II知题设成立。 2）证明

Fm与Fm-1互素（自己证明）

作了k次后 若n-km

3）证明

当n是偶数时，最后一次会出现F0=0项

当n是奇数时，最后一次会出现F1=1项

4）证明 用2）的结论

下面证明是最大公约数

设F(n,m)不是最大公约数， FN是,

则 m|N, n|N 则 N=<(n,m)与 N>(n,m)矛盾 是最大公约数

29. 从1到n的自然数中选取k个不同且不相邻的数，设此选取的方案为f(n,k)。

（a）求f(n,k)的递推关系。 （b）用归纳法求f(n,k)。

（c）若设1与n算是相邻的数，并设在此假定下从1到n的自然数中选取k个不同且不相邻的k个数的方案数为g(n,k)，利用f(n,k)求g(n,k)。 解：...

（a）

（b）

（c）

30. 设S2(n,k)是第二类Stirling数。 证明

证明：...

设与第n+1号球同盒的球有n-k个，这样，其他k个球就放入另外m-1个盒子， k=m-1,m,…,n。 即从n个不同的球中取k个放入m-1个相同的盒子的方案有

31. 求下图中从A点出发到n点的路径数。

解：...

把上方的点序列设为an

把下方的点序列设为bn 可得第推关系

特征方程为 解得

代入初值可解

32. n位0,1符号串，求从左向右只在最后两位才出现0，0的符号串的数目。 解：...

设所求的串的个数为an，相邻不同为0的串的个数为bn

特征方程为 解得

代入初值可解

33. 试证

证明：...

用数学归纳法

I n=2时

成立

II 设n=k时成立即

当n=k+1时

由I、II知题设成立

1.某甲参加一种会议，会上有6位朋友，某甲和其中每人在会上各相遇12次，每二人各相遇6次，每三人各相遇3次，每五人各相遇2次，每六人各相遇一次，1人也没有遇见的有5次，问某甲共参加了几次会议

解: 设Ai为甲与第i个朋友相遇的会议 集，i＝1，?，6．则

故甲参加的会议数为:28+5=33.

2.求从1到500的整数中被3和5整除但不被7整除的数的个数. 解: 设A3：被3整除的数的集合 A5：被5整除的数的集合 A7：被7整除的数的集合

所以

3. n个代表参加会议，试证其中至少有2人各自的朋友数相等。

解:每个人的朋友数只能取0，1，?，n－1．但若有人的朋友数为0，即此人和其 他人都不认识，则其他人的最大取数不超过n－2．故这n个人的朋友数的实际取数只 有n－1种可

能．，所以至少有２人的朋友数相等．

4. 试给出下列等式的组合意义.

解:

5.设有三个7位的二进制数：a1a2a3a4a5a6a7，b1b2b3b4b5b6b7， c1c2c3c4c5c6c7．试证存在 整数i和j，1≤i≤j≤7，使得下列之一必定成立：ai=aj=bi=bj， ai=aj=ci=cj，ai=aj=ci=cj．

证： 显然，每列中必有两数字相同，共有种模式， 有０或１两种选择．故共有·2

种选择．·2=6．现有7列， ．即必有２列在相同的两行选择相同的数字，即有

一矩形，四角的数字相等．

6. 在边长为1的正方形内任取5个点试证其中至少有两点，其间距离小于

证： 把１×１正方形分成四个(1/2)×(1/2)的正方形． 如上图.则这５点中必有两点落在同一个

小正方形内．而小正方 形内的任两点的距离都小于．

7．在边长为1的等边三角形内任取5个点试证其中至少有两点，期间距离小于1/2．

证：

把边长为１的三角形分成四个边长为1/2的三角形，如上图：则这５点中必有两点落在 同一个小三角形中．小三角形中任意两点间的距离都小于1/2．

8. 任取11个整数，求证其中至少有两个数它们的差是10的倍数。

证：整数的个位数的可能取值为０，１，?，９．共１０种可能．11个整数中必有 ２个数的个位数相同，即这两个数之差能被１０整除．

9. 把从1到326的326个整数任意分为5个部分，试证其中有一部分至少有一个数是某两个数之和， 或是另一个数的两倍。

证： 用反证法。设存在划分 P1∪P2∪P3∪P4∪P5＝[1，326]， Pi中没有数是两数之

差．

，则有一Pi中至少有66个数， A＝{ a1 ,?,a66} ，a1＜a2＜···＜a66 ， 以

下按书上174页的例题证明可得．

10. A、B、C三种材料用作产品I、II、III的原料，但要求I禁止用B、C作原料，II不能用B作原料， III不允许用A作原料，问有多少种安排方案？（假定每种材料只做一种产品的原料） 解：按题意可得如下的带禁区的棋盘,其中有阴影的表示禁区．

棋盘多项式为： R(

)=R(

)R(

)

=(1+x)(1+3x+x2 ) =1+4x+4x + x 3

故方案数＝3!－4·2!+4 ·1!－1 ·0!＝1

11. n个球放到m个盒子中去，n＜(m/2)(m－1)，试证其中必有两个盒子有相同的球数。 解：设m个盒子的球的个数是a1,?,am， 各不相等，且有0≤a1＜a2＜···＜am．则有 a2≥1、am≥m－1，故

≥1+2+?+m－1＝(m/2)(m－1) ， 与n＜(m/2)(m－1)相矛盾！ 所以必有两个盒子的球数相等．

12. n各单位各派两名代表去出席一会议。2n位代表围一圆桌坐下。试问： （1）各单位代表并排坐着的方案是多少？ （2）各单位的两人互不相邻的方案数又是多少？

解：

13. 一书架有m层，分别放置m类不同种类的书，每层n册。先将书架上的图书全部取出清理。清理过程要求不打乱所有的类别。试问:

（1）m类书全不在各自原来层次上的方案数有多少？ （2）每层的n本书都不在原来位置上的方案数等于多少？

（3）m层书都不在原来层次，每层n本书也不在原来位置上的方案数又有多少？

解：

14．m+1行同色的矩形。

列的格子同m种颜色着色，每格着一种颜色，其中必有一个4角

证 每列有(m+1)行，只有m种颜色，故一列中必有两格同色．同色的２个格子的行 号有

种取法．有m种色，故有m 种同色模式，现有m +1列，必有两列的同色模

式相同．即由这两列的对应行上有 ４个格子同色，正好是一个矩形的４个角上的格子．得证． 15. 两名教师分别对6名学生同时进行两门课程的面试（每名教师各管一门课程）每名学生每门面试的时间都是半个小时，共有多少不同的面试顺序？ 解 第一门课的顺序有6!种；

第二门课的顺序有： D6＝6! ( (1/2!)－(1/3!)＋(1/4!)－(1/5!)＋(1/6!) )＝265; 故总顺序有6!×265种．

16.在平面直角坐标系中至少任去多少个整点（两个坐标系都是整数）才能保证其中存在3个构成三角形（包含3点在一条直线上）的面积是整数（可以为0）．

解 任一点的坐标（a , b）只有如下４种可能：(奇数，偶数)、(奇数，奇数)、 (偶数，奇数)、(偶数，偶数)。因而5个点中必有两个点模2的格式一样．设 2｜(x1－x2)，2｜(y1－y2)即x1－x2＝2k ， y1－y2＝２l，则三角形面积

是整数．

17. 在平面直角坐标系中至少任去多少个整点才能保证存在3个点构成的三角形的重心是整点？

解 设(x，y)是整点，每个分量模3后有 如下表的结果：

若有３个点模３后的结果落在上表中的同 一格中，则这３个点的重心是整点． 若有３点占满一行，则３点重心是整点； 有３点占满一列，则３点重心是整点； 若存在一组均匀分布，则有3点重心是整点．

由上表可知，若只有8个点，也不能保证有３点的重心是整点．（因为若每个格子都有 ２点，则只占有４个格子，无法保证上面的要求）

下面假设存在９个点，其中任３点的 重心都不是整点．则这9个点，至少占有＝5个

格子（因 为每格中最多有2个点，否则有3个点的重 心为整点），每行最多有２格，又=3，

所以每行都有点． 同理，每列都有点． 不妨设第一行2点，第二行2点，第三行1点 前2 行有两种模式：

或

这样第三行的点无论在哪一列都构成占满一列或构成一组均匀分布．满足前面说的 三点重心是整点的情况．

故 9个点能保证其中存在３个点的重心是 整点．

本文来源：https://www.bwwdw.com/article/xq96.html