组合数学基础-问题与练习
- 格式：doc
- 大小：491.50 KB
- 文档页数：4
………………………………………………最新资料推荐………………………………………
1 / 4
组合数学基础-
问题与练习
（陶平生）
基本内容与方法：组合计数；组合构造；组合结构；映射与对应；分类与染色；归纳与
递推；容斥原理；极端原理；调整法；补集法；数形结合法，等等．
1
、设M为n元集，若M有k个不同的子集12,,,kAAA，满足：对于每个
,1,2,,ijk
，ijAA，求正整数k的最大值．
2
、将前九个正整数1,2,,9分成三组，每组三个数，使得每组中的三数之和皆为质数；
求出所有不同分法的种数．
3
、设正整数a的各位数字全由1和2组成，由其中任意 2kk个连续数位上的数
字所组成的k位数，称为数a的一个“k段”；若数a的任两个“k段”都不相同．
证明：对于具有这种性质的最大正整数a，其开初的一个“1k段”和最后的一个“
1k
段”必定相同.
4
、将数集},...,,{21naaaA中所有元素的算术平均值记为)(AP，
（naaaAPn...)(21）. 若B是A的非空子集，且)()(APBP，则称B是A
的一个“均衡子集”．
试求数集}9,8,7,6,5,4,3,2,1{M的所有“均衡子集”的个数．
5、某校有2010
名新生，每人至少认识其中n人，试求n的最小值，使得其中必存在
彼此认识的16个人.
6
、有2nn名运动员，其编号分别是1,2,,n，在一次活动中，他们以任意方式站
成了一排. 如果每次允许将其中一些人两两对换位置，但在同一轮操作过程中,任一人至多
只能参与一次这种对换.
证明：至多只需两轮这样的操作，可使队列变成1,2,,n的顺序排列.
7
、称自然数a开初若干位数字组成的数为a的“前缀”.例如，2,20,201,2011都是
数2011的“前缀”.
证明：对于任一给定的正整数M，存在正整数n，使M为2n的“前缀”.
8、对于2n
元集合1,2,,2Mn，若n元集12,,,nAaaa，
12,,,n
Bbbb
满足：,ABMAB，且11nnkkkkab，则称AB是集
M
的一个“等和划分”（AB与BA算是同一个划分）．
试确定集1,2,,12M共有多少个“等和划分”．
………………………………………………最新资料推荐………………………………………
2 / 4
9、对于由前2n
个正整数构成的集合{1,2,,2}Mn，若能将其元素适当划分，排成
两个n项的数列：1212(,,,),(,,,)nnAaaaBbbb，使得,1,2,,kkabkkn，
则称M为一个友谊集，而数列,AB称为M的一种友谊排列，例如(3,10,7,9,6)A和
(2,8,4,5,1)B便是集合{1,2,,10}M
的一种友谊排列，或记为3,10,7,9,62,8,4,5,1；
0
(1)
、证明：若{1,2,,2}Mn为一个友谊集，则存在偶数种友谊排列；
0
(2)
、确定集合1{1,2,,8}M及2{1,2,,10}M的全体友谊排列．
10、一副纸牌共52张，其中“方块”、“梅花”、“红心”、“黑桃”每种花色的牌各13
张，
标号依次是2,3,,10,,,,JQKA，其中相同花色、相邻标号的两张牌称为“同花顺牌”，
并且A与2也算是顺牌（即A可以当成1使用）.
试确定，从这副牌中取出13张牌，使每种标号的牌都出现，并且不含“同花顺牌”的取
牌方法数．
11
、一副三色牌，共有纸牌32张，其中红黄蓝每种颜色的牌各10张，编号分别是
1,2,,10
；另有大小王牌各一张，编号均为0，从这副牌中任取若干张牌，然后按如下规
则计算分值：每张编号为k的牌计为k2分，若它们的分值之和为2004，就称这些牌为一个
“好”牌组．
试求 “好”牌组的个数．
12
、奥运会排球预选赛有n支球队参加，其中每两队比赛一场，每场比赛必决出胜负，
如果其中有k（3kn）支球队12,,,kAAA，满足：1A胜2A，2A胜3A，…，
1kA
胜kA，kA胜1A，则称这k支球队组成一个k阶连环套；
证明：若全部n支球队组成一个n阶连环套，则对于每个k（3kn）及每支球队
iA1in，i
A
必另外某些球队组成一个k阶连环套.
13
、任意给定 2nn个互不相等的n位正整数，证明：存在1,2,,kn，使得
将它们的第k位数字都删去后，所得到的n个1n位数仍互不相等.
14
、桌面上放有2011枚硬币，其中有的正面朝上，其余的正面朝下，今有2011人依
次按如下方法翻转硬币：第一人翻转其中的一枚，第二人翻转其中的两枚，…，第k人翻转
其中的k枚，…，第2011人则将2011枚硬币全部翻转．
证明：1、不论硬币最初正反面的分布情况如何，他们总可采取适当的步骤，使得
2009
人都操作之后，恰使所有的硬币朝同一个方向；
………………………………………………最新资料推荐………………………………………
3 / 4
2
、硬币最后的统一朝向，只依赖于初始分布，而与具体的翻币方案无关．
15、平面上任给16
个点，每两点间的距离不超过1；
证明：其中必有两点，它们间的距离不超过124．
16、某选区有1000
个选民，分别持有编号为000,001,002,,999的选票，选区共设有
100
个投票站，编号分别是00,01,02,,99．选区制定了一条法律：规定选民z如果要将
选票投到票站A，只有当该选民所持有的选票号码中，若去掉其中某一数码后，剩下的两
位数恰好就是该票站的号码时方可进行，（例如，持135号票的选民，只能到13,15,35号票
站之一去投票）；
问，在这一法规下，该选区最多可以关闭多少个投票站，使得剩下的投票站还能确保
选举照常进行？
17、在平面直角坐标系中给定100
边形P，满足：01、P的顶点坐标都是整数；
0
2
、P的边都与坐标轴平行；03、P的边长都是奇数．
证明：P的面积为奇数．
18、mn矩形ABCD
的一组邻边之长为：,ABmADn，其中,mn是互质的正奇
数，该矩形被分割成mn个单位正方形，设矩形的对角线AC与这些单位正方形的边相交，
顺次得到交点12,,,kAAA（其中1,kAAAC）．
试求1111(1)kjjjjAA的值．
19、边长为n的菱形ABCD
,其顶角A为o60,今用分别与,ABAD及BD平行的三
组等距平行线，将菱形划分成22n个边长为1的正三角形
(如图所示).试求以图中的线段为边的梯形个数sn.
20、某学校有2011名学生，学号分别是1,2,,2011，该校的会场恰有2011
个座位，
分别编号为1,2,,2011，学生的每次集会都是不用对号入座的；如果在一次集会中，任一
个学号为k的学生都不坐在k号位，且任意n个学号为12,,,nkkkaaa的学生，其座位号集
合12,,,nkkk异于学号集合12,,,nkkkaaa，（其中12011n，ma为坐在m号位置
上的学生的学号），就称这种坐法是“奇特”的．对于每种“奇特”坐法：122011,,,aaa，
………………………………………………最新资料推荐………………………………………
4 / 4
令201121kkMak，求M的最小值，并确定达到最小值时的所有入座情况．
