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

《组合数学第四版卢开澄标准答案-第三章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章3.12.一年级有100名学生参加中文，英语和数学的考试，其中92人通过中文考试，75人通过英语考试，65人通过数学考试；其中65人通过中，英文考试，54人通过中文和数学考试，45人通过英语和数学考试，试求通过3门学科考试的学生数。[解].令：A1={通过中文考试的学生}A2={通过英语考试的学生}A3={通过数学考试的学生}于是

2、Z

3、=100，

4、A1

5、=92，

6、A2

7、=75，

8、A3

9、=65

10、A1∩A2

11、=65，

12、A1∩A3

13、=54，

14、A2∩A3

15、=45此题没有给出：j有多少人通过三门中至少一门；k有多少人一门都没通过。但是由max{

16、A1

17、,

18、A2

19、,

20、

21、A3

22、}=max{92,75,65}=92故可以认为：j至少有92人通过三门中至少一门考试，即100≥

23、A1∪A2∪A3

24、≥92k至多有8人没通过一门考试，即0≤

25、∩∩

26、≤8于是，根据容斥原理，有

27、A1∪A2∪A3

28、=(

29、A1

30、+

31、A2

32、+

33、A3

34、)-(

35、A1∩A2

36、+

37、A1∩A3

38、+

39、A2∩A3

40、)+

41、A1∩A2∩A3

42、即

43、A1∩A2∩A3

44、=

45、A1∪A2∪A3

46、-(

47、A1

48、+

49、A2

50、+

51、A3

52、)+(

53、A1∩A2

54、+

55、A1∩A3

56、+

57、A2∩A3

58、)=

59、A1∪A2∪A3

60、-(92+75+65)+(65+54+45)=

61、A1∪A2∪A3

62、-232+164=

63、A

64、1∪A2∪A3

65、-68从而由92-68≤

66、A1∪A2∪A3

67、-68≤100-68即24≤

68、A1∪A2∪A3

69、-68≤32可得24≤

70、A1∩A2∩A3

71、≤32故此，通过3门学科考试的学生数在24到32人之间。也可用容斥原理，即

72、∩∩

73、=

74、Z

75、-(

76、A1

77、+

78、A2

79、+

80、A3

81、)+(

82、A1∩A2

83、+

84、A1∩A3

85、+

86、A2∩A3

87、)-

88、A1∩A2∩A3

89、=100-(92+75+65)+(65+54+45)-

90、A1∩A2∩A3

91、=100-232+164-

92、A1∩A2∩A3

93、【第42页共42页】=32－

94、A1∩A2∩A3

95、从而有

96、A1∩A2∩A3

97、=32-

98、∩∩

99、由已知0

100、≤

101、∩∩

102、≤8，可得24≤

103、A1∩A2∩A3

104、≤32故此，通过3门学科考试的学生数在24到32之间。3.13.试证：(a)

105、∩B

106、=

107、B

108、-

109、A∩B

110、(b)

111、∩∩C

112、=

113、C

114、-

115、A∩C

116、-

117、B∩C

118、+

119、(A∩B∩C)

120、[证].(a)B=B∩Z(因为BÍZ)=B∩(A∪)(零壹律:且有互补律Z=A∪)=(B∩A)∪(B∩)(分配律)=(A∩B)∪(∩B)(交换律)另外(A∩B)∩(∩B)=(A∩)∩B(结合律，交换律，幂等律)=Æ∩B(互补律A∩=Æ)=Æ(零壹律)所以

121、B

122、=

123、A∩B

124、+

125、∩B

126、因此

127、∩B

128、=

129、B

130、-

131、A∩B

132、(b)

133、∩∩C

134、=

135、∩C

136、(deM

137、organ律)=

138、C

139、-

140、(A∪B)∩C

141、(根据(a)，令A1=A∪B)=

142、C

143、-

144、(A∩C)∪(B∩C)

145、(分配律)【第42页共42页】=

146、C

147、-(

148、A∩C

149、+

150、B∩C

151、-

152、(A∩C)∩(B∩C)

153、)=

154、C

155、-

156、A∩C

157、-

158、B∩C

159、+

160、(A∩C)∩(B∩C)

161、=

162、C

163、-

164、A∩C

165、-

166、B∩C

167、+

168、(A∩B∩C)

169、(结合律，交换律，幂等律)3.14.N={1,2,…,1000}，求其中不被5和7除尽，但被3除尽的数的数目。[解].定义：P1(x):3

170、xA1={x

171、xÎNÙP1(x)}P2(x):5

172、xA2={x

173、xÎNÙP2(x)}P3(x):7

174、xA3={x

175、

176、xÎNÙP3(x)}

177、A1

178、=ë1000/3û=333

179、A1∩A2

180、=ë1000/(3×5)û=66

181、A1∩A3

182、=ë1000/(3×7)û=47

183、A1∩A2∩A3

184、=ë1000/(3×5×7)û=9因此

185、A1∩∩

186、=

187、A1

188、-

189、A1∩A2

190、-

191、A1∩A3

192、+

193、A1∩A2∩A3

194、=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

195、xA1={x

196、xÎ

197、N∩P1(x)}P2(x):3

198、xA2={x

199、xÎN∩P2(x)}P3(x):5

200、xA3={x

201、xÎN∩P3(x)}P4(x):7

202、xA4={x

203、xÎN∩P4(x)}

204、A1

205、=⌊120/2⌋=60

206、A2

207、=⌊120/3⌋=40

208、A3

209、=⌊120/5⌋=24

210、A4

211、=⌊120/7⌋=17

212、A1∩A2

213、=⌊120/(2×3)⌋=20

214、A1∩A3

215、=⌊120/(2×5)⌋=12

216、A1∩A4

217、=⌊120/(2×7)⌋=8

218、A2∩A3

219、=⌊120/(5×7)⌋=8

220、A2∩A4

221、=120/(3×7)⌋=5

222、A3∩A4

223、=⌊120/(5×7)⌋=3

224、A1∩A2∩A3

225、=⌊1

226、20/(2×3×5)⌋=4

227、A1∩A2