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

2020年11月30日发(作者：柏子庭)
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阶幻方。
(1)
A
D
F
B
X
G
C
E
H

因为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取子游戏是平衡的还是非平衡的？游戏< br>人I的第一次取子方式是从大小为19的堆中取走6枚硬币，游戏人II的第一次取子方
式是什么 ？
答:

大小为22的
堆
大小为19的
堆
大小为14的
堆
大小为11的
堆

16
1
1
0
0
偶数
8
0
0
1
1
偶数
4
1
0
1
0
偶数
2
1
1
1
1
偶数
1
0
1
0
1
偶数
因此,游戏初始是平衡的.