1、 【 第 1 页 共 42 页 】 第三章 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 此题没有给出： 有多少人通过三门中至少一门 ； 有多
2、少人一门都没通过 。 但是由 max |A1|,|A2|,|A3| =max92,75,65=92 故可以认为： 至少有 92 人通过三门中至少一门考试 ， 即 100|A1 A2 A3|92 至多有 8 人没通过一门考试 ， 即 0| 1A 2A 3A | 8 于是，根据容斥原理，有 |A1 A2 A3|=(|A1|+|A2|+|A3|)-(|A1A2|+|A1A3|+|A2A3|)+|A1A2A3| 即 |A1A2A3|=|A1 A2 A3|-(|A1|+|A2|+|A3|)+(|A1A2|+|A1A3|+|A2A3|) =|A1 A2 A3|-(92+75+65)+(65+54+45)
3、=|A1 A2 A3|-232+164 =|A1 A2 A3|-68 从而 由 92-68|A1 A2 A3|-68100-68 即 24|A1 A2 A3|-6832 可得 24|A1A2A3| 32 故此 ， 通过 3 门学科考试的学生数在 24 到 32 人之间 。 也可用容斥原理，即 | 1A 2A 3A |=|Z|-(|A1|+|A2|+|A3|)+(|A1A2|+|A1A3|+|A2A3|)-|A1A2A3| =100-(92+75+65)+(65+54+45)-|A1A2A3| =100-232+164-|A1A2A3| 【 第 2 页 共 42 页 】 =32 |A1A2A3|
4、 从而 有 |A1A2A3|=32-| 1A 2A 3A | 由已知 0| 1A 2A 3A |8，可得 24|A1A2A3|32 故此，通过 3 门学科考试的学生数在 24 到 32 之间 。 3.13.试证： (a)|A B|=|B|-|AB| (b)|A B C|=|C|-|AC|-|BC|+|(ABC)| 证 .(a)B =BZ (因为 BZ) = B(A A ) (零壹律 :且有互补律 Z=A A ) =(BA) (BA ) (分配律 ) =(AB) (A B) (交换律 ) 另外 (AB)(A B) = (AA )B (结合律，交换律，幂等律 ) = B (互补律 AA =) =
5、(零壹律 ) 所以 |B|=|AB|+|A B| 因此 |A B|=|B|-|AB| (b)|A B C|=| BA C| (de Morgan 律 ) =|C|-|(A B)C| (根据 (a)，令 A1=A B) =|C|-|(AC) (BC)| (分配律 ) 【 第 3 页 共 42 页 】 =|C|-(|AC|+|BC|-|(AC)(BC)|) =|C|-|AC|-|BC|+|(AC)(BC)| =|C|-|AC|-|BC|+|(ABC)| (结合律，交换律，幂等律 ) 3.14. N=1,2, ,1000，求其中不被 5 和 7 除尽，但 被 3 除尽的 数 的数目。 解 .定义：
6、P1(x):3|x A1=x|xNP1(x) P2(x):5|x A2=x|xNP2(x) P3(x):7|x A3=x|xNP3(x) |A1| =1000/3=333 |A1A2|=1000/(35)=66 |A1A3|=1000/(37)=47 |A1A2A3|=1000/(357)=9 因此 |A1 2A 3A |=|A1|-|A1A2|-|A1A3|+|A1A2A3| =333-66-47+9 =229 因此 ，在 1 1000 中能被 3 整除，同时不能被 5 和 7 整除的数有 229 个 。 3.15. N=1,2,120，求其中被 2,3,5,7,m 个数除尽的数的数目， m
7、=0,1,2,3,4 。求不超过 120的素数的数目。 解 .定义 P1(x):2|x A1=x|xN P1(x) P2(x):3|x A2=x|xN P2(x) P3(x):5|x A3=x|xN P3(x) P4(x):7|x A4=x|xN P4(x) |A1|=120/2=60 |A2|=120/3=40 |A3|=120/5=24 |A4|=120/7=17 |A1 A2|=120/(23)=20 |A1 A3|=120/(25)=12 |A1 A4|=120/(27)=8 |A2 A3|=120/(57)=8 |A2 A4|=120/(37)=5 |A3 A4|=120/(57)=
8、3 |A1 A2 A3|=120/(235)=4 |A1 A2 A4|=120/(237)=2 【 第 4 页 共 42 页 】 |A1 A3 A4|=120/(257)=1 |A2 A3 A4|=120/(357)=1 |A1 A2 A3 A4|=120/(2357)=0 |N|=120 p0=|N|=120 p1=|A1|+|A2|+|A3|+|A4|=60+40+24+17=141 p2=|A1A2|+|A1A3|+|A1A4|+|A2A3|+|A2A4|+|A3A4|=20+12+8+8+5+3=56 p3=|A1A2A3|+|A1A2A4|+|A1A3A4|+|A2A3A4|=4+2
9、+1+1=8 p4=|A1A2A3A4|=0 当 m=0 时， q0=p0-p1+p2-p3+p4=120-141+56-8+0=27 当 m=1 时， q1=p1- 12p2+ 23p3- 34p4=141-256+38-40=53 当 m=2 时， q2= p2- 13p3+ 24p4=56-38+60=32 当 m=3 时， q3= p3- 14p4=8-40=8 当 m=4 时， q4= p4=0 由于 120 121 =11，所以不超过 120 的合数一定有不超过 10 的因子，因而一定有2,3,5,7 的素因子 (因为 10 以内的素数只用 2,3,5,7)，所以不超过 120 的
10、素数一定是那些不能被 2,3,5,7 除尽的数 (当然还要去 掉 非素数的数 1)，故此不超过 120 的素数的数目=q0-1=27-1=26 个。 3.16.求正整数 n 的数目， n 除尽 1040,2030中的至少一个数。 解 . 定义： P1(x):x|1040 A1=x|xN P1(x) P2(x):x|2030 A2=x|xN P2(x) 由于 1040=(25)40=240540 2030=(225)30=260530 故此 |A1|=(40+1)(40+1)=1681 |A2|=(60+1)(30+1)=1891 (参见第一章第九题 ) 【 第 5 页 共 42 页 】 |A1
11、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|xN P1(x) P2(x):x|2050 A2=x|xN P2(x) P3(x):x|3040 A3=x|xN P3(x) 由于 1060=(25)60=260560 2050=(225)50=2100550 3040=(235)40=
12、240340540 故此： |A1|=(60+1)(60+1)=3721 |A2|=(100+1)(50+1)=5151 |A3|=(40+1)(40+1)(40+1)=68921 |A1A2|=(60+1)(50+1)=3111 |A1A3|=(40+1)(40+1)=1681 |A2A3|=(40+1)(40+1)=1681 |A1A2A3|=(40+1)(40+1)=1681 根据容斥原理，有 |A1 A2 A3|=(|A1|+|A2|+|A3|)- (|A1A2|+|A1A3|+|A2A3|)+|A1A2A3| =(3721+5151+68921)-(3111+1681+1681)+1
13、681 =73001 所以，至少能整除 1060,2050,3040之一的正整数 n 有 73001 个 。 3.18 求下列集合中不是 2n ， 3n 形式的数的数目， n N 。 （ a） 1， 2， 410 （ =N1） （ b） 310 ， 310 +1， 410 （ =N2） 【 第 6 页 共 42 页 】 【解】：（ a）定义： P1（ x） :x= 2n （ n N） A1= x|x N1 P1(x) P2（ x） :x= 3n （ n N） A1= x|x N2 P2(x) A1=21 ， 2 ， 22)10( 1N 故 |A1|= 210 =100 A2=31 ， 32 ，
14、 321 1N 故 |A2|=21 （因为 321 =9261 410 10648= 322 ） A1 A2=61 ， 62 ， 63 ， 64 1N ，故 |A1 A2|=4 （因为 64 =4096 410 15625= 65 ） 因此，根据容斥原理，有 | 1A 2A |=|N1|-（ |A1|+|A2|） +|A1 A2| = 410 （ 100+21） +4 =9883 （ b）定义： P1（ x） :x= 2n （ n N） A1= x|x N1 P1(x) P2（ x） :x= 3n （ n N） A1= x|x N2 P2(x) A1= 231 ， 22)10( 2N 故 |A
15、1|=100-30=70 （因为 231 =961 310 1024= 232 ） A2= 310 ， 321 2N 故 |A2|=21-9=12 A1 A2= 64 2N 故 |A1 A2|=1 【 第 7 页 共 42 页 】 （因为 63 =729 310 64 =4096 因此，根据容斥原理，有 | 1A 2A |=|N1|-（ |A1|+|A2|） +|A1 A2| = 9001（ 70+12） +1 = 8920 3.19 1000， 1001， 3000，求其中是 4的倍数但不是 100 的倍数的数的数目。 【解】： 令 N1=1000， 1001， 3000，则 |N1|=20
16、01 P1（ x） :4|x A1= x|x N1 P1(x) P1（ x） :100|x A1= x|x N2 P2(x) 于是由 A1=4 250， 4 251， 4 750 N1， 故 |A1|=750 250+1=501， A1 A2=100 10， 100 11， 100 30 N1， 故 |A1 A2|=30 10+1=21 因此 |A1 2A |=|A1| |A1 A2|=501 21=480 所以， 1000 3000 中只能被 4 整除，但不能被 100 整除的数有 480 个。 3.20 在由 a,a,a,b,b,b,c,c,c 组成的排列中，求满足下列条件的排列数， （
17、a）不存在相邻 3 元素相同 （ b）相邻两元素不相同 【解】：（ a） 定义： Z=9 个元素的全排列 ， |Z|= ！ ！ 3339 =1680 P1(x)：排列 x 中有相邻三元素相同，且是 a 【 第 8 页 共 42 页 】 P2(x)：排列 x 中有相邻三元素相同，且是 b P3(x)：排列 x 中有相邻三元素相同，且是 c A1=x |x Z P1(x) |A1 |= !3!3!7 =140 A2=x |x Z P2(x) |A2 |= !3!3!7 =140 A3=x |x Z P3(x) |A3 |= !3!3!7 =140 |A1 A2|=!3!5=20 |A1 A3|=!
18、3!5=20 |A2 A3|=!3!5=20 |A1 A2 A3|=3！ =6 于是，根据容斥原理，有 | 1A 2A 3A |=|Z|（ |A1|+|A2|+|A3|） +（ |A1 A2|+|A1 A3|+|A2 A3|） |A1 A2 A3| =1680 3 140 3 20 6=1314 （ b）定义： Z=9 个元素的全排列 ， |Z|= ！ ！ 3339 =1680 P1(x)：排列 x 中有相邻两个元素相同，且是 a P2(x)：排列 x 中有相邻两个元素相同，且是 b P3(x)：排列 x 中有相邻两个元素相同，且是 c iA =x|x Z iP (x) (1 i 3) |A1
19、|= !3!3!8 !3!3!7 =1120 140=980 (因为将 aa 与 a 看做为不同的两个元素参与排列，在它们相遇之时会产生重复，其重复因子刚好是将 aaa 看作一个整体参与排列的个数 ) 同理可得： |A2|= !3!3!8 !3!3!7 =1120 140=980 【 第 9 页 共 42 页 】 |A3|= !3!3!8 !3!3!7 =1120 140=980 因为 A1 A2 为 aa,bb 图象都出现的排列集合，当我们将 aa 与 a,bb 与 b 看作不同的两对元素进行排列时，在 aa 与 a 相遇而成 aaa 图象及 bb与 b 相遇而成 bbb 图象时会产生重复计
20、数。 当 aaa 图象与 bbb 图象恰出现一个时，重复因子为 2；当图象 aaa 与图象 bbb同时出现时，重复因子为 4 。 设 q1(x)：排列 x 中 aa 与 a相遇而有 aaa 图象 q2(x)：排列 x 中 bb 与 b相遇而有 bbb 图象 故 B1=x |x A1 A2 q1(x) B2=x |x A1 A2 q2(x) 于是 |B1| = |B2| =!3!6=120 |B1 B2| =!3!5=20 P1 = |B1| + |B2| =2 120 =240 P2 = |B1 B2 |=20 q1=P1 2P2 =240 2 20=200 q2=P2=20 从而 |A1 A
21、2| = !3!7 （ q1+3q2） =840 (200+3 20)=580 同理， |A1 A3 | =580 |A2 A3 |=580 因为 A1 A2 A3 为 aa， bb， cc 图象出现的排列集合，当我们将 aa 与 a， bb与 b， cc 与 c 看作不同的三对元素进行排列时，在 aa 与 a 相遇而成 aaa 图象，bb 与 b 相遇而成 bbb 图象， cc 与 c 相遇而成 ccc 图象时会产生重复计数。 当 aaa， bbb， ccc 图象恰出现一个时，重复因子为 2 当 aaa， bbb， ccc 图象恰出现两个时，重复因子为 4 当 aaa， bbb， ccc 图
22、象恰同时出现时，重复因子 为 8 设 q1(x)；排列 x中有 aaa 图象 q2(x)；排列 x中有 bbb 图象 q3(x)；排列 x中有 ccc 图象 iB =x |x A1 A2 A3 iq (x) (1 i 3) |B1| =|B2|=|B3|=5! |B1 B2|=|B1 B3|=|B2 B3|=4!=24 【 第 10 页 共 42 页 】 |B1 B2 B3|=3!=6 P1=|B1|+|B2|+|B3|=3 120=360 P2=|B1 B2| |B1 B3| |B2 B3|=3 24=72 P3=|B1 B2 B3|=6 q1=P1 2P2+3P3=360 2 72 3 6
23、=234 q2=P2 3P3=72 3 6=54 q3=P3=6 因此 |A1 A2 A3| = 6！（ q1 3q2 7q3） =720 (234+3 54+7 6)=282 所以 | 1A 2A 3A | =|Z|-（ |A1|+|A2| |A3|） +（ |A1 A2|+|A1 A3|+|A2 A3|） |A1 A2 A3| = 1680 3 980 3 580 282=198 即 相邻两元素不相同的排列数为 198 3.21 求出 O（ 0， 0）点到（ 8， 4）点的路径数，已知（ 2， 1）到（ 4， 1）的线路，（ 3， 1）到（ 3， 2）的线路被封锁。 【解】：令 P（ 8， 4）， A（ 2， 1）， B（ 4， 1）， C（ 3， 1）， D（ 3， 2） P1（ x）：线段 AB在从 O到 P的路径 X 上 P2（ x） ：线段 CD在从 O到 P的路径 X 上 iA =x|x Z )(xqi (1 i 2) Z=从 O 到 P 的路径 |Z|= 4 48= 412= 1234 9101112 =495 |A1| = 1 12 14 )14()48(=13 37=3 123 567 =105 |A2| = 1 13 24 )24()38(= 14 27=4 1267 =84
