2024年3月16日发(作者：邰梓)
第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
;
其中各数满足：0a
1
5;0<=a
2
<=4;0a
3
3;0a
4
2;0a
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
2024年3月16日发(作者：邰梓)
第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
;
其中各数满足：0a
1
5;0<=a
2
<=4;0a
3
3;0a
4
2;0a
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