2,第二讲 集合中的计数问题

第二讲 集合中的计数问题

知识要点：n个元素的集合的子集个数；容斥原理。

1. 已知集合A,B,C(不必相异)的并集A?B?C??a,b,c,d?，求满足条件的有序三元组(A,B,C)的个数.

2. 求满足A1?A2?A3???Am??a1,a2,?,an?的集合组(A1,A2,?,Am)的个数.

3. 称有限集S的所有元素的乘积为S的“积数”，给定数集M??,,?,①求 M的所有非空子集的“积数”之和

②求集M的所有含偶数个元素的子集的“积数”之和

4. 对于集合?1,2,?,n?和它的每一个非空子集，我们定义“交替和”如下：把集合中的数按从小到大的顺序排列，然后从最大的数开始交替地加减各数（例如?1,2,4,6,9?的交替和是9?6?4?2?1?6,而?5?的交替和就是5）.对于n?7，求所有这些交替和的总和.

5.设集合M??1,2.?1000?,现对于M的任一非空子集x.令?x表示x中最大数与最小数之和，那么所有这样的?x的算术平均值为多少？

6． 设集合A??1,2,3,?,100?,且对最大值.

?11?231??, 100??x,y?A，有2x?y，求子集A中所含元素个数的

1

7.已知集合A??2,3,4,5,6,7?对于X?A,定义S(X)为X中所有元素之和，求全体S(X)的总和.

8.设M??1,2,?,1995?,A?M,且当x?A时，15x?A,求card(A)的最大值.

9.设A??1,2,3,?,2n,2n?1?,B是A的一个子集，且B中的任意三个不同元素x,y,z，都 有x?y?z，求B的最大值.

10.设A是?1,2,?,2000?的子集，card(A)?1000,证明：要么A中有一个数为2的幂，要么A中存在两个数a,b，使a?b为2的幂.

11. 已知集合S中有10个元素，每个元素都是两位数，求证：一定可以从S中取出两个无公共元集的子集，使两个子集的元素和相等.

2

12. 集合A的元素都是正整数，其中最小的是1，最大的是100，除1以外，每一个元素都等于集合A中的两个数（可以相同）的和，求集合A的元素个数的最小值.

13. 设S??1,2,3,4?，n项的数列：a1,a2,?,an有下列性质，对于S的任一非空子集B(B的元素个数记为B),在该数列中有相邻的B项恰好组成集合B，求n的最小值.

14.集A由100个非负整数组成，集S由所有形如x?y的数组成，x,y?A（允许x?y）， 问S最多有几个数？最少有几个数？

15.设Z是平面上由n(n?3)个点组成的点集，其中任三点不共线，又设正整数k满足不 等式

n?k?n.如果Z中的每个点都至少与Z中的k个点有线段相连，证明：这些线段中2一定有三条线段构成三角形的三边.

16.一次会议有2005位数学家参加，每人至少有1337位合作者，求证：可以找到4位数学家，他们中每两人都合作过.

3

17.设S??1,2,3,?,100?,求最小的正整数n，使得S的每个n元子集都含有4个两两互质 的数.

18.设集合A??1,2,?,m?，求最小的正整数m，使得对A的任意一个14?分划

A1,A2,?,A14,一定存在某个集合Ai(1?i?14)，在Ai中有两个元素a,b,满足b?a?

4b. 319.在某次竞选中，各个政党共作出P种不同的诺言(P?0),任何两个政党都至少有一种公共诺言，但没有两党做出完全相同的诺言，证明：政党的数目不多于2

20.（1）如果存在1,2,?,n的一个排列a1,a2,?,an，使得k?ak(k?1,2,?,n)都是完全平方数，则称n为“好数”，问在集合?，哪些不是“好数”，11,13,15,17,19?中，哪些是“好数”说明理由.

（2）如果存在1,2,?n的一个排列a1,a2,?,an使k?ak(k?1,2,?n)都是完全平方数，则称n为“好数”，问在正整数集中，哪些是“好数”，那些不是“好数”，说明理由.

p?1个.

4