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

第三章

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 页】

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

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

p1=|A1|+|A2|+|A3|+|A4|=60+40+24+17=141

p2=|A1∩A2|+|A1∩A3|+|A1∩A4|+|A2∩A3|+|A2∩A4|+|A3∩A4|=20+12+8+8+5+3=56 p3=|A1∩A2∩A3|+|A1∩A2∩A4|+|A1∩A3∩A4|+|A2∩A3∩A4|=4+2+1+1=8 p4=|A1∩A2∩A3∩A4|=0

① 当m=0时，q0=p0-p1+p2-p3+p4=120-141+56-8+0=27

当m=1时，q1=p1-????p2+????p3-????p4=141-2×56+3×8-4×0=53

?2??1??3??2??4??3?当m=2时，q2= p2-????p3+????p4=56-3×8+6×0=32

?3??1??4??2?当m=3时，q3= p3-????p4=8-4×0=8

?4??1?当m=4时，q4= p4=0

② 由于120<121=11，所以不超过120的合数一定有不超过10的因子，因而一定有2,3,5,7的素因子(因为10以内的素数只用2,3,5,7)，所以不超过120的素数一定是那些不能被2,3,5,7除尽的数(当然还要去掉非素数的数1)，故此不超过120的素数的数目=q0-1=27-1=26个。

3.16.求正整数n的数目，n除尽1040,2030中的至少一个数。 [解]. 定义：P1(x):x|1040 A1={x|x?N∩P1(x)}

P2(x):x|2030 A2={x|x?N∩P2(x)}

由于 1040=(2×5)40=240×540 2030=(22×5)30=260×530 故此 |A1|=(40+1)(40+1)=1681

|A2|=(60+1)(30+1)=1891 (参见第一章第九题)

【第 4 页 共 42 页】

|A1∩A2|=(40+1)(30+1)=1271

于是 |A1∪A2|=|A1|+|A2|-|A1∪A2|=1681+1891-1271=2301 因此，能至少除尽1040和2030之一的正整数的数目是2301 。 3.17.n是除尽1060,2050,3040中至少一个数的除数，求n的数目。 [解]. 定义： P1(x):x|1060 A1={x|x?N∩P1(x)}

P2(x):x|2050 A2={x|x?N∩P2(x)} P3(x):x|3040 A3={x|x?N∩P3(x)}

由于 1060=(2×5)60=260×560 2050=(22×5)50=2100×550 3040=(2×3×5)40=240×340×540 故此： |A1|=(60+1)(60+1)=3721 |A2|=(100+1)(50+1)=5151 |A3|=(40+1)(40+1)(40+1)=68921 |A1∩A2|=(60+1)(50+1)=3111 |A1∩A3|=(40+1)(40+1)=1681 |A2∩A3|=(40+1)(40+1)=1681 |A1∩A2∩A3|=(40+1)(40+1)=1681 根据容斥原理，有

|A1∪A2∪A3|=(|A1|+|A2|+|A3|)- (|A1∩A2|+|A1∩A3|+|A2∩A3|)+|A1∩A2∩A3| =(3721+5151+68921)-(3111+1681+1681)+1681 =73001

所以，至少能整除1060,2050,3040之一的正整数n有73001个 。

3.18 求下列集合中不是n2，n3形式的数的数目，n∈N 。

（a）{1，2，……，104} （=N1） （b）{103，103+1，……，104} （=N2）

【第 5 页 共 42 页】

本文来源：https://www.bwwdw.com/article/kl0d.html