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

组合数学讲座

组合基础问题（陶平生）

基本内容与方法：组合计数；组合构造；组合结构；映射与对应；分类与染色；归纳

与递推；容斥原理；极端原理；调整法；补集法；数形结合法，等等．

1、在一次晚会上，9位舞星共上演

n

个“三人舞”节目，若在这些节目中，任二个人

都曾合作过一次，且仅合作一次，求

n

的值.

，满足：对于每个

i,j

1,2,,k

，2、设

M

为

n

元集，若

M

有

k

个不同的子集

A

i

A

j



A

1

,A

2

,,A

k

，求正整数

k

的最大值．

3、将前九个正整数

1,2,,9

分成三组，每组三个数，使得每组中的三数之和皆为质数；

求出所有不同分法的种数．

4、设正整数

a

的各位数字全由

1

和

2

组成，由其中任意

k

k2

个连续数位上的数字所

组成的

k

位数，称为数

a

的一个“

k

段”；若数

a

的任两个“

k

段”都不相同．

证明：对于具有这种性质的最大正整数

a

，其开初的一个“

k1

段”和最后的一个“

k1

段”必定相同.

5、将数集

A{a

1

,a

2

,...,a

n

}

中所有元素的算术平均值记为

P(A)

，

（

P(A)

a

1

a

2

...a

n

n

）. 若

B

是

A

的非空子集，且

P(B)P(A)

，则称

B

是

A

的

1

一个“均衡子集”．

试求数集

M{1,2,3,4,5,6,7,8,9}

的所有“均衡子集”的个数．

6、某校有

2010

名新生，每人至少认识其中

n

人，试求

n

的最小值，使得其中必存在彼

此认识的

16

个人.

7、有

n

n2

名运动员，其编号分别是

1,2,,n

，在一次活动中，他们以任意方式站成

了一排. 如果每次允许将其中一些人两两对换位置，但在同一轮操作过程中,任一人至多只

能参与一次这种对换.

证明：至多只需两轮这样的操作，可使队列变成

1,2,,n

的顺序排列.

8、称自然数

a

开初若干位数字组成的数为

a

的“前缀”.例如，

2,20,201,2011

都是数

2011

的“前缀”.

证明：对于任一给定的正整数

M

，存在正整数

n

，使

M

为

2

的“前缀”.

n

9、对于

2n

元集合

M

1,2,,2n

，若

n

元集

A

a

1

,a

2

,,a

n

，

B

b

1

,b

2

,,b

n

满足：

ABM,AB

，且

k1

a

b

k

k1

nn

k

，则称

AB

是集

M

的一个“等

和划分”（

AB

与

BA

算是同一个划分）．

M

1,2,,12

试确定集共有多少个“等和划分”．

2

10、对于由前

2n

个正整数构成的集合

M{1,2,,2n}

，若能将其元素适当划分，排成两

个

n

项的数列：

A(a

1

,a

2

,,a

n

),B(b

1

,b

2

,,b

n

)

，使得

a

k

b

k

k,k1,2,,n

，则称

M

为一个

友谊集，而数列

A,B

称为

M

的一种友谊排列，例如

A(3,10,7,9,6)

和

B(2,8,4,5,1)

便是集合

M{1,2,

3,10,7,9,6



,10}

的一种友谊排列，或记为

2,8,4,5,1

；

(1

0

)

、证明：若

M{1,2,,2n}

为一个友谊集，则存在偶数种友谊排列；

(2

0

)

、确定集合

M

1

{1,2,,8}

及

M

2

{1,2,,10}

的全体友谊排列．

11、一副纸牌共

52

张，其中“方块”、“梅花”、“红心”、“黑桃”每种花色的牌各

13

张，

标号依次是

2,3,,10,J,Q,K,A

，其中相同花色、相邻标号的两张牌称为“同花顺牌”，并且

A

与

2

也算是顺牌（即

A

可以当成

1

使用）.

试确定，从这副牌中取出

13

张牌，使每种标号的牌都出现，并且不含“同花顺牌”的

取牌方法数．

12、一副三色牌，共有纸牌

32

张，其中红黄蓝每种颜色的牌各

10

张，编号分别是

1,2,,10

；另有大小王牌各一张，编号均为

0

，从这副牌中任取若干张牌，然后按如下规则

k

计算分值：每张编号为

k

的牌计为

2

分，若它们的分值之和为

2004

，就称这些牌为一个“好”

牌组．

试求 “好”牌组的个数．

13、奥运会排球预选赛有

n

支球队参加，其中每两队比赛一场，每场比赛必决出胜负，

3

如果其中有

k

（

3kn

）支球队

胜

A

1

A

1

,A

2

,,A

k

，满足：

A

1

胜

A

2

，

A

2

胜

A

3

，…，

A

k1

胜

A

k

，

A

k

，则称这

k

支球队组成一个

k

阶连环套；

证明：若全部

n

支球队组成一个

n

阶连环套，则对于每个

k

（

3kn

）及每支球队

A

i

1in

，

A

i

必另外某些球队组成一个

k

阶连环套.

14、任意给定

n

n2

个互不相等的

n

位正整数，证明：存在

k

1,2,,n

，使得将它

们的第

k

位数字都删去后，所得到的

n

个

n1

位数仍互不相等.

15、桌面上放有

2011

枚硬币，其中有的正面朝上，其余的正面朝下，今有

2011

人依次

按如下方法翻转硬币：第一人翻转其中的一枚，第二人翻转其中的两枚，…，第

k

人翻转其

中的

k

枚，…，第

2011

人则将

2011

枚硬币全部翻转．

证明：

1

、不论硬币最初正反面的分布情况如何，他们总可采取适当的步骤，使得

2009

人都操作之后，恰使所有的硬币朝同一个方向；

2

、硬币最后的统一朝向，只依赖于初始分布，而与具体的翻币方案无关．

16、某学校有

2011

名学生，学号分别是

1,2,,2011

，该校的会场恰有

2011

个座位，分

别编号为

1,2,,2011

，学生的每次集会都是不用对号入座的；如果在一次集会中，任一个学

号为

k

的学生都不坐在

k

号位，且任意

n

个学号为

a

k

1

,a

k

2

,,a

k

n

m

的学生，其座位号集合

k

1

,k

2

,,k

n

异于学号集合

a

k

1

,a

k

2

,,a

k

n

，（其中

1n2011

，

a

为坐在

m

号位置上的学生的

学号），就称这种坐法是“奇特”的．对于每种“奇特”坐法

：

a

1

,a

2

,,a

2011

，令

M

a

k

k

k1

2011

2

，求

M

的最小值，并确定达到最小值时的所有入座情况．

4