解：根据鸽巢原理加强形式：如果q1,q2,,,,,qn为正整数，将q1+q2+.....qn-n+1个物体放入n个盒子里。那么，至少存在一个盒子含有qn个物体。对于此题：我们需要取12个水果。设已经取出了11个水果，还剩下一个。那么需要11×4+1分钟。

题5：证明对于任意n+1个整数a1,a2,.....a(n+1)存在两个整数ai和aj，i≠j，使得ai-aj能够被n整除。

解：由于任一整数被n整除的余数有0,1,2,......n-1。 共n种，对于n+1个数，由鸽巢原理可得证。即存在ai,aj。ai=bn+r,aj=cn+r (b>c)。ai-aj=(b-c)n。所以n|ai-aj。至少两个整数被n整除的余数相等。

题6：证明，边长为2的正方形中取5个点，当中存在2个点，这2点的距离至多为√2

解：将正方形分成四等分即可

第二章:

5、证明：如果从{1,2,3，… ，3n}中选择n+1个整数，那么总存在两个整数，他们之间最多差2。

答：取鸽巢为{1,2,3},{4,5,6},….,{3n-2,3n-1,3n}共n个，当从中选取n+1个数时，必然有至少两个属于同一鸽巢，即他们的差最多为2

14、一只袋子装了100个苹果、100个香蕉、100个橘子和100个梨子。如果我每分钟从袋子里取出1个水果，那么需要多长时间我就能肯定至少已拿出了一打相同种类的水果？

答：根据鸽巢原理的加强形式可得：

,故需45分

钟。

16、证明在一群n>1个人中，存在两个人，他们在这群人中有相同数目的熟人。

答：已知，每个人认识的人数为0,1,…n-1。而这一群人中不可能同时存在认识0人和n-1人的情况，因此，所有人所认识人数范围为1,2,3,…,n-1或0,1,2…,n-2，

均为n-1个，现在有n个人，由鸽巢原理可知，必然存在至少两个人认识的人数相等。

18、证明，从边长为2的正方形中任选5个点，他们当中存在2个点，这两个点的距离最多为

。

答：如图所示，将图分割成四个小正方形，可知小正方形内的两点之间的最大距离为

，而由鸽巢原理可知，从图中任选5个点

则必有至少两个点在同一小正方形内，即他们的距离最多为

第三章：

4、问620有多少个互异正因子。

答：将620因式分解可得：620=

，所以互异正因子的个数为3*2*2=12

8、有15个人围坐一个圆桌。其中，如果B拒绝挨着A坐，有多少种围坐方式？如果B只拒绝坐在A的右边，又有多少种围坐方式？

答：这15个人围坐的方法一共有14!种，(1)A和B在一起的情况，则围坐方法有13!*2种，因此，B拒绝挨着A坐的情况一共有14!-13!*2=12*13!。(2)考虑B只在A一侧的情况，则，相当于AB相对位置固定，则围坐的方法一共有13!种，所以，B只拒绝坐在A的右侧的方法数为14!-13!=13*13!。 17、将2个红车4个蓝车放在8*8的棋盘上，使没有两个车可以互相攻击的摆放方式有多少种？ 答：

27、确定多重集S={3a,3b,3c,3d}的11排列的个数。

答：由11排列我们可知：S={2a,3b,3c,3d} U{3a,2b,3c,3d} U{3a,3b,2c,3d} U{3a,3b,3c,2d}，即对这些11元素集合进行排列计数，即得S的11排列个数为：

第四章：

15、对于{后继组合。

答：用2进制表示为：（1011111），+1后为1100000，所以，后继组合为{

31、生成{1,2,3,4,5}的3排列。

答：首先写出它的3-组合：

123,124,125,134,135,145,234,235,245,345 然后分别进行排列：

123 132 231 213 312 321 124 142 241 214 412 421 125 152 251 215 512 521 134 143 341 314 413 431 135 153 351 315 513 531 145 154 451 415 514 541 234 243 342 324 423 432 235 253 352 325 523 532 245 254 452 425 524 542 345 354 453 435 534 543

}

}通过使用基为2的生成算法确定其直接

第六章：

3、求出从1到10000既不是完全平方数又不是完全立方数的整数个数。

答：设S={1,2,…,10000}，为S中的完全平方数的集合，集合，则问题是求|

|，由于

=10000,，所以|

又是完全立方数的集合，亦即：

为S中完全立方数的

|=100，由于

>10000,所以|

|=21。为既是完全平方数，，由于

=4096，

=15625>10000，故， |

。所以：

|=10000-（100+21）+4=9883

13、确定{1,2,3,4,5,6,7,8,9,}的至少一个奇数在他的自然位置上的排列数

答：设S为{1,2,3,…,9}的排列

的全体，

，

，，则问题变成求||。

，，

，

所以：|

|=5*8！-10*7！+10*6！-5*5！+4！

15、在一次聚会上，7位绅士检查他们的帽子。有多少种方法是的这些帽子返还时满足： 1）没有绅士收到他自己的帽子 2）至少一位绅士收到他自己的帽子 3）至少两位绅士收到他们自己的帽子

答：1）这是一个错位排列问题，有

种方法。

2）设S为7位男士收到帽子结果的全体，A为S中至少一位男士收到自己帽

子的集合，则就是S中没有人收到自己帽子的集合，所以：

|A|=|S|-||=