湖南大学离散数学第三章习题一解答.doc

第三章习题一解答 一、求下列集合的幂集 1、杨,李,石 解：P(杨,李,石) =F, 石,李,石,杨,杨,石,杨,李,杨,李,石 2、1,2,2,1,1,2,1,1,2 解：原集合=1,2,2,1,2,1=1,2，只含一个元素，故其幂集只有2 个元素： P=F,1,2 二、利用包含排斥原理，求解以下各题。 1、对60 人调查，25 读每周新闻，26 读时代，26 人读财富，9 人读每周新闻和财富，11 读每周新闻和时代，8 人读时代与财富，还有 8 人什么都不读，请计算： (1) 阅读全部三种杂志的人数。 (2) 分别求只阅读每周新闻、时代、财富杂志的人数。 解：记A=每周新闻的读者，B=时代的读者，C=财富的读者。 由于8 人什么都不读，故只有 52 人读杂志，即 |ABC|=52。已知 |A|=25，|B|=26，|C|=26 |AC|=9，|AB|=11，|BC|=8 （1）由包含排斥原理可知 |ABC|=|A|+|B|+|C|-|AC|-|AB|-|BC|+| ABC|，故 52=25+26+26-9-11-8+| ABC|，即有 | ABC|=3， 所以同时读三种杂志的人为3 人。 （2）注意到 |ST| = |S|-|ST|，故只读每周新闻的人数为： =|A|-|AB|-|AC|+| ABC|=25-9-11+3=8； 只读时代人数为：|B|-|BA|-|BC|+| ABC|=26-11-8+3=10 ； 只读财富的人为：|C|-|CA|-|CB|+| ABC|=26-9-8+3=12。 2、某班25个学生，14人会打篮球，12人会打排球，6人会篮球和排球，5人会打篮球和网球，还有2人会打这三种球，已知6人会网球的都会篮球或排球，求不会打球的人。 解：先求出会打球的人，25-会打球的人=不会打球的人。 |篮|=14, |排|=12, |篮排|=6, |篮网|=5, |篮排网|=2，|网|=6， 又 6= |网(篮排)| = |网篮|+|网排|-|网篮排|, 故 5+ |网排|-2=6， 故 | 网排|=3, 由包含排斥原理可知会打球的人数为 |篮排网|=|篮|+|排|+|网|-|篮排|-|篮网|-|排网|+|篮排网| =14+12+6- 6- 5-3+2=20， 故不会打球有5 人。 3、在 1 到300 的整数中（1 和300 包含在内），分别求满足以下条件的整数个数： (1) 同时能被3，5，7 整除； (2) 不能被3 和 5 整除，也不能被7 整除的数； (3) 可以被3 整除，但是不能被 5 和7 整除； (4) 可以被3 或5 整除，但不能被7 整除； (5) 只被3,5,7 中一个整除的数； 解：用A3 表示1 到300中能被3 整除的数的集合，A5表示1 到300中能被5整除的数的集合，A7表示1 到300中能被7 整除的数的集合。 则有 |A3|=300/3=100， |A5|=300/5=60 ，|A7|=300/7=42； | A3A5 |=300/15=20， | A3A7|=300/21=100/7=14，| A5A7|=300/35=60/7=8， | A3A5A7|=2。 | A3A5A7| = |A3|+| A5|+|A7|-|A3A5|-|A3A7|-|A5A7|+|A3A5A7|=100+60+42-20-14-8+2 =162 (1) 同时能被3，5，7 同时整除的数的个数为 | A3A5A7|=2； (2) 不能被3 和 5 整除，也不能被7 整除的数的个数为 | A3A5A7|=300- | A3A5A7| =300-162=138； (3) 注意到 |AB| = |A|-|AB|，故可被3整除但不能被 5 和7 整除的数的个数为 | A3A5A7| = | A3(A5A7)| = | A3 |-| (A3A5)(A3A7)|=| A3 |-| A3A5|-| A3A7|+| A3A5A7|=100-20-14+2=68; (4) 可以被3 或5 整除，但不能被7 整除的数的个数为 | (A3A5)A7| =| (A3A7)(A5A7)| =| A3A7|+| A5A7|-| A3A5A7| =(| A3|-| A3A7|)+ (| A5|-| A5A7|)-(| A3A5|-| A3A5A7|) = (100-14)+(60-8)-(20-2)=120; (5) 只被3,5,7 中一个整除的数的个数分别为 只被3 整除的数：| A3|-| A3A5|-| A3A7|+| A3A5A7|=100-20-14+2=68； 只被5 整除的数：| A5|-| A5A3|-| A5A7|+| A5A3A7|=60-20-8+2=34 ； 只被7 整除的数：| A7|-| A7A3|-| A7A5|+| A7A3A5|=42-14-8+2=22。 4、求 1120 之间的素数。 提示：采用筛选法求不超过 120 之间的素数。由 120121，故 11，只要去掉2,3,5,7的倍数，则剩下来的数不可能有因数存在，即为素数。 解：令A2，A3，A5，A7分别为1120范围内能被2，3，5，7 整除的数的集合，则1120中去除2,3,5,7的整倍数后所剩的数的个数为| A2A3A5A7| = 120- | A2A3A5A7| 。由于 |A2|=120/2=60，|A3|=120/3=40，|A5|=120/5=24，|A7|=120/7=17；|A2A3|=120/6=20， |A2A5|=120/10=12， |A2A7|=120/14=60/7=8， |A3A5|=120/15=40/5=8 ，|A3A7|=120/21=40/7=5，|A5A7|=120/35=24/7=3； |A2A3A5|=120/(2*3*5) =4 ，|A2A3A7|=120/(2*3*7) =2 ， |A3A5A7|=120/(3*5*7) =1， |A2A5A7|=120/(2*5*7) =1； |A2A3A5A7|=120/(2*3*5*7) =0 ； 所以| A2A3A5A7|=60+40+24+17-(20+12+8+8+5+3)+(4+2+1+1)-0=141-56+8=149-56=93 ， 故1120中去除2,3,5,7的整倍数后所剩的数的个数为120-93=27。但这不是素数的个数，因为去除倍数时还去除了2,3,5,7的一倍，这本是不该去掉的，应当补回来，而这剩下的27个数中1不是素数，应该去掉故素数的总数应当是27+4-1=30 。 5、在 1 和 10000 之间（包括 1 和 10000 在内）不能被4、5、6 整除的数有多少个？ 解：设A4, A5, A6 分别表示110000范围内被4,5,6 整除的数的集合，则要求的数的个数为(注意分母中的是最小公倍数)：=10000 (10000/4+10000/5+10000/6)(10000/20+10000/1210000/30)10000/30=10000(2500+2000+1666)(500+833+333)+166 =10004666=5334 6、在 1 和 10000 之间（包括 1 和 10000）既不是某个整数的平方，也是不是某个整数的立方的数有多少？ 解：设A=x2 | 1 x210000，B=x3 | 1 x310000，则要求的数的个数为. 7、在 1 和 10000 之间（包括 1 和 10000）有多少个整数包含了1，2，3 和4。 解：设A1, A2, A3, A4 分别表示110000范围内含1,2,3,4的数的集合。（1）如果将题意理解为要求整数只含有1,2,3,4之一时，则要求的数的个数为。 而 为110000内不含1,2,3,4的数的个数，这相当于用六个数字0,5,6,7,8,9去填四个空格的方案数。用排列组合中的乘法法则知，共有