高中数学竞赛教材讲义 第一章 集合与简易逻辑

第一章集合与简易逻辑一、基础知识定义1一般地，一组确定的、互异的、无序的对象的全体构成集合，简称集，用大写字母来表示；集合中的各个对象称为元素，用小写字母来表示，元素x在集合A中，称x属于A，记为Ax，否则称x不属于A，记作Ax。例如，通常用N，Z，Q，B，Q+分别表示自然数集、整数集、有理数集、实数集、正有理数集，不含任何元素的集合称为空集，用来表示。集合分有限集和无限集两种。集合的表示方法有列举法：将集合中的元素一一列举出来写在大括号内并用逗号隔开表示集合的方法，如{1，2，3}；描述法：将集合中的元素的属性写在大括号内表示集合的方法。例如{有理数}，}0{xx分别表示有理数集和正实数集。定义2子集：对于两个集合A与B，如果集合A中的任何一个元素都是集合B中的元素，则A叫做B的子集，记为BA，例如ZN。规定空集是任何集合的子集，如果A是B的子集，B也是A的子集，则称A与B相等。如果A是B的子集，而且B中存在元素不属于A，则A叫B的真子集。定义3交集，}.{BxAxxBA且定义4并集，}.{BxAxxBA或定义5补集，若},{,1AxIxxACIA且则称为A在I中的补集。定义6差集，},{\BxAxxBA且。定义7集合},,{baRxbxax记作开区间),(ba，集合},,{baRxbxax记作闭区间],[ba，R记作).,(定理1集合的性质：对任意集合A，B，C，有：（1）);()()(CABACBA（2）)()()(CABACBA；（3）);(111BACBCAC（4）).(111BACBCAC【证明】这里仅证（1）、（3），其余由读者自己完成。（1）若)(CBAx，则Ax，且Bx或Cx，所以)(BAx或)(CAx，即)()(CABAx；反之，)()(CABAx，则)(BAx或)(CAx，即Ax且Bx或Cx，即Ax且)(CBx，即).(CBAx（3）若BCACx11，则ACx1或BCx1，所以Ax或Bx，所以)(BAx，又Ix，所以)(1BACx，即)(111BACBCAC，反之也有.)(111BCACBAC定理2加法原理：做一件事有n类办法，第一类办法中有1m种不同的方法，第二类办法中有2m种不同的方法，…，第n类办法中有nm种不同的方法，那么完成这件事一共有nmmmN21种不同的方法。定理3乘法原理：做一件事分n个步骤，第一步有1m种不同的方法，第二步有2m种不同的方法，…，第n步有nm种不同的方法，那么完成这件事一共有nmmmN21种不同的方法。二、方法与例题1．利用集合中元素的属性，检验元素是否属于集合。例1设},,{22ZyxyxaaM，求证：（1）)(,12ZkMk；（2）)(,24ZkMk；（3）若MqMp,，则.Mpq[证明]（1）因为Zkk1,，且22)1(12kkk，所以.12Mk（2）假设)(24ZkMk，则存在Zyx,，使2224yxk，由于yx和yx有相同的奇偶性，所以))((22yxyxyx是奇数或4的倍数，不可能等于24k，假设不成立，所以.24Mk（3）设Zbayxbaqyxp,,,,,2222，则))((2222bayxpq22222222aybxbyaaMyaxbybxa22)()(（因为ZyaxbZyaxa,）。2．利用子集的定义证明集合相等，先证BA，再证AB，则A=B。例2设A，B是两个集合，又设集合M满足BAMBABAMBMA,，求集合M（用A，B表示）。【解】先证MBA)(，若)(BAx，因为BAMA，所以MxMAx,，所以MBA)(；再证)(BAM，若Mx，则.BAMBAx1）若Ax，则BAMAx；2）若Bx，则BAMBx。所以).(BAM综上，.BAM3．分类讨论思想的应用。例3}02{},01{},023{222mxxxCaaxxxBxxxA，若CCAABA,，求.,ma【解】依题设，}2,1{A，再由012aaxx解得1ax或1x，因为ABA，所以AB，所以Aa1，所以11a或2，所以2a或3。因为CCA，所以AC，若C，则082m，即2222m，若C，则C1或C2，解得.3m综上所述，2a或3a；3m或2222m。4．计数原理的应用。例4集合A，B，C是I={1，2，3，4，5，6，7，8，9，0}的子集，（1）若IBA，求有序集合对（A，B）的个数；（2）求I的非空真子集的个数。【解】（1）集合I可划分为三个不相交的子集；A\B，B\A，IBA,中的每个元素恰属于其中一个子集，10个元素共有310种可能，每一种可能确定一个满足条件的集合对，所以集合对有310个。（2）I的子集分三类：空集，非空真子集，集合I本身，确定一个子集分十步，第一步，1或者属于该子集或者不属于，有两种；第二步，2也有两种，…，第10步，0也有两种，由乘法原理，子集共有1024210个，非空真子集有1022个。5．配对方法。例5给定集合},,3,2,1{nI的k个子集：kAAA,,,21，满足任何两个子集的交集非空，并且再添加I的任何一个其他子集后将不再具有该性质，求k的值。【解】将I的子集作如下配对：每个子集和它的补集为一对，共得12n对，每一对不能同在这k个子集中，因此，12nk；其次，每一对中必有一个在这k个子集中出现，否则，若有一对子集未出现，设为C1A与A，并设1AA，则ACA11，从而可以在k个子集中再添加AC1，与已知矛盾，所以12nk。综上，12nk。6．竞赛常用方法与例问题。定理4容斥原理；用A表示集合A的元素个数，则,BABABACBACBCABACBACBA，需要xy此结论可以推广到n个集合的情况，即nikjijinkjijiiniiAAAAAAA111.)1(11niinA定义8集合的划分：若IAAAn21，且),,1(jinjiAAji，则这些子集的全集叫I的一个n-划分。定理5最小数原理：自然数集的任何非空子集必有最小数。定理6抽屉原理：将1mn个元素放入)1(nn个抽屉，必有一个抽屉放有不少于1m个元素，也必有一个抽屉放有不多于m个元素；将无穷多个元素放入n个抽屉必有一个抽屉放有无穷多个元素。例6求1，2，3，…，100中不能被2，3，5整除的数的个数。【解】记}）2（2,1001{},100,,3,2,1{xxxxAI记为整除能被且，}5,1001{},3,1001{xxxCxxxB，由容斥原理，31002100CBAACCBBACBACBA7430100151001010061005100，所以不能被2，3，5整除的数有26CBAI个。例7S是集合{1，2，…，2004}的子集，S中的任意两个数的差不等于4或7，问S中最多含有多少个元素？【解】将任意连续的11个整数排成一圈如右图所示。由题目条件可知每相邻两个数至多有一个属于S，将这11个数按连续两个为一组，分成6组，其中一组只有一个数，若S含有这11个数中至少6个，则必有两个数在同一组，与已知矛盾，所以S至多含有其中5个数。又因为2004=182×11+2，所以S一共至多含有182×5+2=912个元素，另一方面，当},2004,10,7,4,2,1,11{NkrttkrrS时，恰有912S，且S满足题目条件，所以最少含有912个元素。例8求所有自然数)2(nn，使得存在实数naaa,,,21满足：}.2)1(,,2,1{}1}{nnnjiaaji【解】当2n时，1,021aa；当3n时，3,1,0321aaa；当4n时，1,5,2,04321aaaa。下证当5n时，不存在naaa,,,21满足条件。令naaa210，则.2)1(nnan所以必存在某两个下标ji，使得1njiaaa，所以1111nnnaaaa或21aaann，即12a，所以1,2)1(1nnnaanna或2)1(nnan，12a。（ⅰ）若1,2)1(1nnnaanna，考虑2na，有22nnaa或22aaann，即22a，设22nnaa，则121nnnnaaaa，导致矛盾，故只有.22a考虑3na，有23nnaa或33aaann，即33a，设23nnaa，则02212aaaann，推出矛盾，设33a，则2311aaaann，又推出矛盾，所以4,22naan故当5n时，不存在满足条件的实数。（ⅱ）若1,2)1(2annan，考虑2na，有12nnaa或32aaann，即23a，这时1223aaaa，推出矛盾，故21nnaa。考虑3na，有23nnaa或nnaa33a，即3a=3，于是123nnaaaa，矛盾。因此32nnaa，所以12211aaaann，这又矛盾，所以只有22aan，所以4n。故当5n时，不存在满足条件的实数。例9设A={1，2，3，4，5，6}，B={7，8，9，……，n}，在A中取三个数，B中取两个数组成五个元素的集合iA，.201,2,20,,2,1jiAAiji求n的最小值。【解】.16minn设B中每个数在所有iA中最多重复出现k次，则必有4k。若不然，数m出现k次（4k），则.123k在m出现的所有iA中，至少有一个A中的数出现3次，不妨设它是1，就有集合{1，121,,,bmaa}},,,,1{},,,,,1{365243bmaabmaa，其中61,iAai，为满足题意的集合。ia必各不相同，但只能是2，3，4，5，6这5个数，这不可能，所以.4k20个iA中，B中的数有40个，因此至少是10个不同的，所以16n。当16n时，如下20个集合满足要求：{1，2，3，7，8}，{1，2，4，12，14}，{1，2，5，15，16}，{1，2，6，9，10}，{1，3，4，10，11}，{1，3，5，13，14}，{1，3，6，12，15}，{1，4，5，7，9}，{1，4，6，13，16}，{1，5，6，8，11}，{2，3，4，13，15}，{2，3，5，9，11}，{2，3，6，14，16}，{2，4，5，8，10}，{2，4，6，7，11}，{2，5，6，12，13}，{3，4，5，12，16}，{3，4，6，8，9}，{3，5，6，7，10}，{4，5，6，14，15}。例10集合{1，2，…，3n}可以划分成n个互不相交的三元集合},,{zyx，其中zyx3，求满足条件的最小正整数.n【解】设其中第i个三元集为,,,2,1},,,{nizyxii则1+2+…+niizn1,43所以niiznn142)13(3。当n为偶数时，有n38，所以8n，当n为奇数时，有138n，所以5n，当5n时，集合{1，11，4}，{2，13，5}，{3，15，6}，{9，12，7}，{10，14，8}满足条件，所以n的最小值