2第二講集合中的計數(shù)問題

1、1第二講 集合中的計數(shù)問題知識要點(diǎn)：n n 個元素的集合的子集個數(shù)；容斥原理。1.1.已知集合A, B,C( (不必相異) )的并集AUBUC二a,b,c,d1，求滿足條件的有序三元組(A, B,C)的個數(shù). .2.2.求滿足A UA2UAsU UAm=ai,a2,aj的集合組(A,A2,IH,Am)的個數(shù)11 1i3.3.稱有限集S的所有元素的乘積為S的“積數(shù)”，給定數(shù)集M=丄，丄，丄|_2 3川100J1求M的所有非空子集的“積數(shù)”之和2求集M的所有含偶數(shù)個元素的子集的“積數(shù)”之和4.4.對于集合1,2,1”，n?和它的每一個非空子集，我們定義“交替和”如下：把集合中的數(shù)按從小到大的順序排

2、列，然后從最大的數(shù)開始交替地加減各數(shù)(例如1,2,4,6,9 ?的交替和是9 -6 4 -2 -1=6,而的交替和就是5). .對于n =7,求所有這些交替和的總和 . .5.5.設(shè)集合M=訃2.川1000?, ,現(xiàn)對于M的任一非空子集x. .令表示x中最大數(shù)與最小數(shù) 之和，那么所有這樣的；：x的算術(shù)平均值為多少?6 6.設(shè)集合A1,2,3,川,100二且對-八A，有2x=y，求子集A中所含元素個數(shù)的最大值. .27.7.已知集合A-23,4,5,6,7?對于X代定義S(X)為X中所有元素之和，求全體S(X)的總和. .8.8.設(shè)M Jl,2,1995?, ,A M ,且當(dāng)x A時，15x-一

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

4、集合A的元素個數(shù)的最小值. .31313設(shè)S =1,2,3,4 n項的數(shù)列：印2,，a.有下列性質(zhì)，對于S的任一非空子集B（B的元素個數(shù)記為B）, ,在該數(shù)列中有相鄰的B項恰好組成集合B，求n的最小值. .1414集A由100個非負(fù)整數(shù)組成，集S由所有形如x y的數(shù)組成，x, y A（允許x = y）， 問S最多有幾個數(shù)？最少有幾個數(shù)？15.15.設(shè)Z是平面上由n（n 3）個點(diǎn)組成的點(diǎn)集，其中任三點(diǎn)不共線，又設(shè)正整數(shù)k滿足不等式-:k k ：n如果Z中的每個點(diǎn)都至少與Z中的k個點(diǎn)有線段相連，證明：這些線段中2一定有三條線段構(gòu)成三角形的三邊. .16.16. 一次會議有2005位數(shù)學(xué)家參加，每人

5、至少有1337位合作者，求證：可以找到4位數(shù)學(xué)家，他們中每兩人都合作過17.17.設(shè)S = *1,2,3，100?, ,求最小的正整數(shù)n，使得S的每個n元子集都含有4個兩兩互質(zhì) 的數(shù). .18.18.設(shè)集合A1,2，,mf，求最小的正整數(shù)m,使得對A的任意一個14-分劃44A,A2,，A4, , 定存在某個集合A(1G14)，在A中有兩個元素a,b,滿足b：a：b.319.19.在某次競選中，各個政黨共作出P種不同的諾言(P 0), ,任何兩個政黨都至少有一種公 共諾言，但沒有兩黨做出完全相同的諾言，證明：政黨的數(shù)目不多于2pJ個. .20.20.( 1 1 )如果存在1,2, , n的一個排列31,32/,an，使得k ak(k=1,2, n)都是完全平 方數(shù)，則稱n為“好數(shù)”，問在集合11,13,15,17,191中，哪些是“好數(shù)”，哪些不是“好數(shù)” 說明理由. .(2 2)如果存在