组合数学作业第一次作业及其答案

1. 设想一个监狱有64个囚室组成，这些囚室排列得象一张8X8的棋盘。所有相邻的囚室

之间都有门相通。一个被囚在某个角上囚室中的犯人被告知，如果他能够恰好通过每个囚室一次而到达对角位置上的囚室，他就将被释放。问：该犯人能否得到自由？

答:不能获得自由,将棋盘涂成黑白相间,每经过的房间都是黑白交替,因此从左下角白房间出发,是不可能达到右上角的白房间的,最后一个房间必是黑色.

2. 用1×2的骨牌对6×6的棋盘进行完美覆盖。证明：无论怎样覆盖，一定存在断层线。

另外，8×8的棋盘呢？

答:假设6X6棋盘存在这样一个完美覆盖,使得把棋盘切成两个非空部分的五条水平切割线和垂直切割线都不是断层线.设x1,x2,x3,x4,x5分别是被水平切割线切到的多米诺骨牌数.一个水平方向的多米诺骨牌覆盖一行上的两个方格,因此x1,x2,x3,x4,x5都是偶数,即:x1+x2+x3+x4+x5>=2+2+2+2+2=10,即水平方向上至少有10个多米诺骨牌,同理垂直方向也有10个,而覆盖整个6X6棋盘只要18个骨牌,由于10+10>18,因此与题设矛盾,所以无论怎样覆盖,一定存在断层线,同理8X8得证.

3. 证明3阶幻方必然在中心位置有一个5。试推导：恰好存在8个3阶幻方。

因为3阶幻方的幻和为15,因此有: A+X+H=15 D+X+E=15 F+X+C=15 B+X+G=15

将四个式子相加,得3X+(A+B+C)+(D+X+E)+F+G+H=60,即3 X+15+15+15=60,即3X=15,解得X=5;

(2)除去5外,剩下八个数可组成,并且只有4对相加为10的式子,由于中间必为5,所以这四对分布于每条经过X的4条线,当A的位置确定,则H确定,剩下3条线也就确定,因为A位置有八种可能,因此恰好存在8个3阶幻方.

4. 各堆大小分别为22，19，14和11的4-堆Nim取子游戏是平衡的还是非平衡的？游戏

人I的第一次取子方式是从大小为19的堆中取走6枚硬币，游戏人II的第一次取子方式是什么？ 答:

因此,游戏初始是平衡的.

当I从19的堆中取走6枚硬币后,各堆情况如下:

5. 一局游戏在两个游戏人之间如下交替进行：游戏从一空堆开始。当轮到一个游戏人时，

他可以往该堆中加进1，2，3或4枚硬币。往堆中加进第100枚硬币的游戏人为得胜者。确定在这局游戏中是游戏人I还是游戏人II能够确保获胜。获胜的策略是什么？

答:因为100整除5,所以当玩家I投入n个硬币时,玩家II每次投入5-n个硬币,按照这种策略,玩家II最后就能获胜.

6. 证明：有理数m/n展开的十进制小数最终是要循环的。

答:用n作除数去除m，在除法的演算过程中，余数必是0，1，2，…,n-1中的一个，而余数无穷多，因此由鸽巢原理在作除法时一定会出现相同的余数，后面的计算将会重复，于上所得的商也必然重复。

7. 一个学生有37天用来准备考试。根据过去经验，她知道她需要不超过60小时的学习时

间。她还希望每天至少学习1小时。证明，无论她如何安排学习时间（假设每天的学习时间都是整数个小时），都存在连续的若干天，在此期间她恰好学习了13个小时。 答:令ai表示在第i天的学习时间，又ai>=1，1<=i<=37 且 1<=a1<a2<a3<.......<a37<=60 又14<=a1+13<a2+13<a3+13<......<a37+13<=73;在a1,a2,a3,......a37,a1+13,a2+13,.....a37+13这74个数中一定存在两个数ai,aj+13，使得i不等于j使得ai=aj+13。

故存在从j到i连续的若干天，期间她恰好学习了13小时。

8. 证明，从边长为2的正方形中任选5个点，它们当中存在2个点，这2点的距离至多为

根号2。

答: 将正方形切割成四个大小相同的小正方形,如右图,五个点分配到四 个正方形, 根据有鸽巢定理,必定有两个点存在一个正方形中,即这两

点的距离最多为小正方形的对角线长度:根号2.

9. 有一个100人的聚会。每个人都有偶数个（可能是0个）熟人。证明，在这次聚会上存

在3个人有相同个数的熟人。

答:每个人有熟人的个数可能为0,2,4...96,98,一共有50种可能,而假设最多只有2个人有相同个数的熟人,则情况为:分别有两个人有0,2,4...96,98个熟人,对于这两个认识O个人的人来说，他们自然也不认识那两个认识98个人的人，而对于那两个认识98个人的人来说，只能有一个人他们不认识，这就与有两个人都不认识他们矛盾，所以存在3个人有相同个数的熟人.