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

1、1第二讲 集合中的计数问题知识要点：n n 个元素的集合的子集个数；容斥原理。1.1.已知集合A, B,C( (不必相异) )的并集AUBUC二a,b,c,d1，求满足条件的有序三元组(A, B,C)的个数. .2.2.求满足A UA2UAsU UAm=ai,a2,aj的集合组(A,A2,IH,Am)的个数11 1i3.3.称有限集S的所有元素的乘积为S的“积数”，给定数集M=丄，丄，丄|_2 3川100J1求M的所有非空子集的“积数”之和2求集M的所有含偶数个元素的子集的“积数”之和4.4.对于集合1,2,1”，n?和它的每一个非空子集，我们定义“交替和”如下：把集合中的数按从小到大的顺序排

2、列，然后从最大的数开始交替地加减各数(例如1,2,4,6,9 ?的交替和是9 -6 4 -2 -1=6,而的交替和就是5). .对于n =7,求所有这些交替和的总和 . .5.5.设集合M=讣2.川1000?, ,现对于M的任一非空子集x. .令表示x中最大数与最小数 之和，那么所有这样的；：x的算术平均值为多少?6 6.设集合A1,2,3,川,100二且对-八A，有2x=y，求子集A中所含元素个数的最大值. .27.7.已知集合A-23,4,5,6,7?对于X代定义S(X)为X中所有元素之和，求全体S(X)的总和. .8.8.设M Jl,2,1995?, ,A M ,且当x A时，15x-一

3、A, ,求card (A)的最大值. .9.9.设A1,2,3，2n,2n B是A的一个子集，且B中的任意三个不同元素x,y,z，都有x + yz，求B的最大值. .10.10.设A是1,2,，2000?的子集，card(A) _1000,证明：要么A中有一个数为 2 2 的幕，要么A中存在两个数a,b，使a b为 2 2 的幕. .11.11.已知集合S中有 1010 个元素，每个元素都是两位数，求证：一定可以从S中取出两个无公共元集的子集，使两个子集的元素和相等12.12.集合A的元素都是正整数，其中最小的是1,最大的是100，除1以外，每一个元素都等于集合A中的两个数（可以相同）的和，求

4、集合A的元素个数的最小值. .31313设S =1,2,3,4 n项的数列：印2,，a.有下列性质，对于S的任一非空子集B（B的元素个数记为B）, ,在该数列中有相邻的B项恰好组成集合B，求n的最小值. .1414集A由100个非负整数组成，集S由所有形如x y的数组成，x, y A（允许x = y）， 问S最多有几个数？最少有几个数？15.15.设Z是平面上由n（n 3）个点组成的点集，其中任三点不共线，又设正整数k满足不等式-:k k ：n如果Z中的每个点都至少与Z中的k个点有线段相连，证明：这些线段中2一定有三条线段构成三角形的三边. .16.16. 一次会议有2005位数学家参加，每人

5、至少有1337位合作者，求证：可以找到4位数学家，他们中每两人都合作过17.17.设S = *1,2,3，100?, ,求最小的正整数n，使得S的每个n元子集都含有4个两两互质 的数. .18.18.设集合A1,2，,mf，求最小的正整数m,使得对A的任意一个14-分划44A,A2,，A4, , 定存在某个集合A(1G14)，在A中有两个元素a,b,满足b：a：b.319.19.在某次竞选中，各个政党共作出P种不同的诺言(P 0), ,任何两个政党都至少有一种公 共诺言，但没有两党做出完全相同的诺言，证明：政党的数目不多于2pJ个. .20.20.( 1 1 )如果存在1,2, , n的一个排列31,32/,an，使得k ak(k=1,2, n)都是完全平 方数，则称n为“好数”，问在集合11,13,15,17,191中，哪些是“好数”，哪些不是“好数” 说明理由. .(2 2)如果存在