2024年5月1日发(作者：)

第1章 32 *

第2章

第3章

第4章

第5章

4, 16, 20 *

4, 5, 26 *

8, 15, 23, 33 *

可选: 27, 28

第6章 3, 5, 17, 25 *

第7章 6, 11, 21, 24, 38 *

第8章

第9章 11, 12, 15, 16

第10章 12, 17, 43, 46 *

第14章 15, 20, 26, 32 *

第一章

1.32．证明：在具有奇数枚硬币且堆的数目是奇数的Nim取子游戏中，游戏人I总能够取胜。

注：原版题目为证明若在一个Nim取子游戏中，有奇数枚硬币的堆的数目是奇数，则游戏

人I总能够取胜。

证明：设共有k堆硬币，且每堆中硬币的个数分别为n

1

, n

2

,…, n

k

, 令a

1

, a

2

,…, a

k

分别表示n

1

,

n

2

,…, n

k

的二进制表示的最低位。则a

i

=1当且仅当n

i

为奇数。由于有奇数个a

i

等于1，所以

最低位是非平衡的。因此这是一个非平衡的Nim取子游戏。所以游戏人I总能够取胜。

第二章

2.4、证明：如果从{1，2，……，2n}中选择n+1个整数，那么总存在两个整数，它们之间

的差为1。

证明一：设取到n+1个数a

1

< a

2

< … < a

n+1

. 若没有两个数的差为1，则对于任意1 i  n，

a

i+1

－a

i

 2. 于是a

n+1

 2n + a

1

 2n+1，矛盾。

证明二：将{1,2,…,2n}分成n组数：{1,2}, {3,4}, …, {2n-1,2n}. 由鸽巢原理，取出的n+1个

数必有两个属于同一组。

2.16、证明，在一群n>1个人中，存在两个人，他们在这群人中有相同数目的熟人（假设没

有人和他/她自己是熟人）。

证明：n个人中，每人认识的人数是0～n-1，但是若有一人A与0个人互相认识，则其它

所有人至少与A不互相认识，所以不可能有人与n-1个人互相认识。即n个人认识的人数

中不可能同时有0和n-1. n个人认识的人数只有n-1种值，所以存在两人在这群人种有相同

数目的熟人。

2.20、证明，r（3，3，3）<=17.

对于K17，任取其中一点P，与其他16点的连线中，根据鸽巢原理，至少有6条为红色，

或者至少有6条为兰色，或者至少有6条为绿色。

不妨取6条染成红色，即16点中就有6点与P点连线为红色。若这6点中有两点以红

色边相连，则这两点与A组成红色三角形。若这6点中组成的K6中无红色边，即只有兰和

绿两种颜色的边。根据K6—>K3，K3也知或者有一兰三角形或者有一绿三角形。

因此结论得证。

第三章 排列与组合

4，下列各数有多少互异正因子。

426

1）3

×5×7×11, 因子数为5×3×7×2=210

2) 620=2×2×5×31, 所以因子数为3×2×2＝12

3）10=25, 所以因子数为11×11＝121

5，确定成为下列 各数的因子的10的最大幂。

1）50！

50中有10个5，2个25.所以，有10＋2＝12个0

2）1000！

1000中有200个5，40个25，8个125，1个625，有200＋40＋8+1＝249个0

26，确定多重集S＝{3a,4b,5c}的10排列的个数。

所有10组合即对应全排列数如下：

{a,4b,5c} 10!/(4!×5!)＝1260

{2a,3b,5c} 10!/(2!×3!×5!)=2520

{3a,2b,5c} 10!/(3!×2!×5!)=2520

{2a,4b,4c} 10!/(2!×4!×4!)=3150

{3a,3b,4c} 10!/(3!×3!×4!)=4200

{3a,4b,3c} 10!/(3!×4!×3!)=4200

S的10排列数为1260+2520+2520+3150+4200+4200=17850.

第四章习题

8.｛1，2，3，4，5，6｝有多少排列具有

ⅰ恰好15个逆序？

ⅱ恰好14个逆序？

ⅲ恰好13个逆序？

解：对于一个排列i

1

i

2

…i

6

, 令其逆序列为a

1

a

2

…a

6

, 则该排列的逆序数为：a

1

+a

2

+a

3

+a

4

+a

5

+a

6

;

其中各数满足：0a

1

5;0<=a

2

<=4;0a

3

3;0a

4

2;0a

5

1;a

6

=0;

则总的逆序数为：0 a

1

+a

2

+a

3

+a

4

+a

5

+a

6

15;

恰有15个逆序的排列为：1

恰有14个逆序的排列为：5

恰有13个逆序的排列为：4+C(5,2)=14

15.对于{x7,x6,…x1,x0}的下列每一个组合，通过使用基为2的生成算法确定其直接后继组

合。

ⅰ){x4,x1,x0}

ⅱ){x7,x5,x3}

ⅲ){x7,x5,x4,x3,x2,x1,x0}

ⅳ){x0}

解：ⅰ)写成基为2的形式：00010011

得其直接后继组合：00010100

组合为：{x4,x2}

101010