组合数学第四版卢开澄标准答案-第三章解析

第三章

3.12.一年级有100名学生参加中文,英语和数学的考试,其中92人通过中文考试,75人通

过英语考试,65人通过数学考试;其中65人通过中,英文考试,54人通过中文和数学考试,45人通过英语和数学考试,试求通过3门学科考试的学生数。 [解].令:A1={通过中文考试的学生} A2={通过英语考试的学生} A3={通过数学考试的学生}

于是 |Z| =100,|A1|=92,|A2|=75,|A3|=65

|A1∩A2|=65,|A1∩A3|=54,|A2∩A3|=45

此题没有给出:

?有多少人通过三门中至少一门; ?有多少人一门都没通过。

但是由 max{ |A1|,|A2|,|A3| }=max{92,75,65}=92

故可以认为:

?至少有92人通过三门中至少一门考试,即100≥|A1∪A2∪A3|≥92

?至多有8人没通过一门考试,即0≤|A1∩A2∩A3| ≤8 于是,根据容斥原理,有

|A1∪A2∪A3|=(|A1|+|A2|+|A3|)-(|A1∩A2|+|A1∩A3|+|A2∩A3|)+|A1∩A2∩A3| 即 |A1∩A2∩A3|=|A1∪A2∪A3|-(|A1|+|A2|+|A3|)+(|A1∩A2|+|A1∩A3|+|A2∩A3|)

=|A1∪A2∪A3|-(92+75+65)+(65+54+45) =|A1∪A2∪A3|-232+164 =|A1∪A2∪A3|-68

从而由 92-68≤|A1∪A2∪A3|-68≤100-68 即 24≤|A1∪A2∪A3|-68≤32 可得 24≤|A1∩A2∩A3| ≤32

故此,通过3门学科考试的学生数在24到32人之间。

也可用容斥原理,即

|A1∩A2∩A3|=|Z|-(|A1|+|A2|+|A3|)+(|A1∩A2|+|A1∩A3|+|A2∩A3|)-|A1∩A2∩A3|

=100-(92+75+65)+(65+54+45)-|A1∩A2∩A3| =100-232+164-|A1∩A2∩A3|

【第 1 页 共 42 页】

=32-|A1∩A2∩A3|

从而有 |A1∩A2∩A3|=32-|A1∩A2∩A3|

由已知 0≤|A1∩A2∩A3|≤8,可得 24≤|A1∩A2∩A3|≤32

故此,通过3门学科考试的学生数在24到32之间。 3.13.试证:(a)|A∩B|=|B|-|A∩B|

(b)|A∩B∩C|=|C|-|A∩C|-|B∩C|+|(A∩B∩C)| [证].(a)B =B∩Z (因为B?Z)

= B∩(A∪A) (零壹律:且有互补律Z=A∪A)

=(B∩A)∪(B∩A) (分配律)

=(A∩B)∪(A∩B) (交换律)

另外 (A∩B)∩(A∩B)

= (A∩A)∩B (结合律,交换律,幂等律)

=?∩B (互补律A∩A=?) =? (零壹律) 所以 |B|=|A∩B|+|A∩B|

因此 |A∩B|=|B|-|A∩B|

(b)|A∩B∩C|=|A?B∩C| (de Morgan律)

=|C|-|(A∪B)∩C| (根据(a),令A1=A∪B) =|C|-|(A∩C)∪(B∩C)| (分配律)

【第 2 页 共 42 页】

=|C|-(|A∩C|+|B∩C|-|(A∩C)∩(B∩C)|) =|C|-|A∩C|-|B∩C|+|(A∩C)∩(B∩C)|

=|C|-|A∩C|-|B∩C|+|(A∩B∩C)| (结合律,交换律,幂等律) 3.14. N={1,2,…,1000},求其中不被5和7除尽,但被3除尽的数的数目。 [解].定义: P1(x):3|x A1={x|x?N?P1(x)}

P2(x):5|x A2={x|x?N?P2(x)} P3(x):7|x A3={x|x?N?P3(x)}

|A1| =?1000/3?=333 |A1∩A2|=?1000/(3×5)?=66 |A1∩A3|=?1000/(3×7)?=47 |A1∩A2∩A3|=?1000/(3×5×7)?=9 因此 |A1∩A2∩A3|=|A1|-|A1∩A2|-|A1∩A3|+|A1∩A2∩A3| =333-66-47+9

=229

因此 ,在1~1000中能被3整除,同时不能被5和7整除的数有229个。

3.15. N={1,2,?,120},求其中被2,3,5,7,m个数除尽的数的数目,m=0,1,2,3,4 。求不超过120

的素数的数目。

[解].定义 P1(x):2|x A1={x|x?N∩P1(x)}

P2(x):3|x A2={x|x?N∩P2(x)} P3(x):5|x A3={x|x?N∩P3(x)} P4(x):7|x A4={x|x?N∩P4(x)}

|A1|=?120/2?=60 |A2|=?120/3?=40 |A3|=?120/5?=24 |A4|=?120/7?=17

|A1∩A2|=?120/(2×3)?=20 |A1∩A3|=?120/(2×5)?=12 |A1∩A4|=?120/(2×7)?=8

|A2∩A3|=?120/(5×7)?=8 |A2∩A4|=120/(3×7)?=5 |A3∩A4|=?120/(5×7)?=3

|A1∩A2∩A3|=?120/(2×3×5)?=4 |A1∩A2∩A4|=?120/(2×3×7)?=2

【第 3 页 共 42 页】

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4