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

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

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有多少人通过三门中至少一

16、门；k有多少人一门都没通过。但是由max{

17、A1

18、,

19、A2

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、

58、A2∩A3

59、)=

60、A1∪A2∪A3

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

62、A1∪A2∪A3

63、-232+164=

64、A1∪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)+

90、(65+54+45)-

91、A1∩A2∩A3

92、=100-232+164-

93、A1∩A2∩A3

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

95、A1∩A2∩A3

96、从而有

97、A1∩A2∩A3

98、=32-

99、∩∩

100、由已知0≤

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

121、∩)(分配律)=(A∩B)∪(∩B)(交换律)另外(A∩B)∩(∩B)=(A∩)∩B(结合律，交换律，幂等律)=Æ∩B(互补律A∩=Æ)=Æ(零壹律)所以

122、B

123、=

124、A∩B

125、+

126、∩B

127、因此

128、∩B

129、=

130、B

131、-

132、A∩B

133、(b)

134、∩∩C

135、=

136、∩C

137、(deMorgan律)=

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∩

161、C)

162、=

163、C

164、-

165、A∩C

166、-

167、B∩C

168、+

169、(A∩B∩C)

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

171、xA1={x

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

173、xA2={x

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

175、xA3={x

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

185、)û=9因此

186、A1∩∩

187、=

188、A1

189、-

190、A1∩A2

191、-

192、A1∩A3

193、+

194、A1∩A2∩A3

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

196、xA1={x

197、xÎ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、

203、xA4={x

204、xÎN∩P4(x)}

205、A1

206、=⌊120/2⌋=60

207、A2

208、=⌊120/3⌋=40

209、A3

210、=⌊120/5⌋=24

211、A4

212、=⌊120/7⌋=17

213、A1∩A2

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

215、A1∩A3

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

217、A1∩A4

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

219、A2∩A3

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

221、A2∩A4

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

223、A3∩A4

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

225、A1∩A2∩A3

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

227、A1∩A2