|
有三个集合A、B、C。记这三个集合中元素的个数分别为|A|、|B|、|C|。记A与B的交集为A∩B，它的元素的个数为|A∩B|；同理，B与C的交集为B∩C，它的元素的个数为|B∩C|；C与A的交集为C∩A，它的元素的个数为|C∩A|。再记A、B、C三个集合的交集为A∩B∩C，它的元素的个数为|A∩B∩C|。那么，A、B、C的并集A∪B∪C中元素的个数|A∪B∪C|为 |A∪B∪C| = |A| + |B| + |C| - |A∩B| - |B∩C| - |C∩A| + |A∩B∩C| 证明： 我们利用文氏图进行证明。 即 下面是一道典型的三集合容斥原理的应用题。 问题：1到1000这1000个正整数中，能够被3整除，或能够被5整除，或能够被7整除的数有多少个？ 解答： 设1到1000这1000个正整数组成的集合为A。A中能被3整除的数有333个（3，6，9，…，999），它可这样求得：1000=333*3+1，其中的1为余数，它小于3。记这个能被3整除的数的集合为A3，它的元素的个数|A|=333。能被5整除的数有200个（5，10，15，…，995，1000），它可这样求得：1000=200*5。记这个能被5整除的数的集合为A5，它的元素的个数为|A|=200。能被7整除的数有142个（7，14，21，…，994），它可这样求得：1000=142*7+6。记这个能被7整除的数的集合为A7，它的元素的个数为|A|=142。 既能被3整除又能被5整除的数一定是能够被15整除的数，这是集合A3和A5的交集。记这个集合为A3∩A5，它的元素的个数可以这样求得：1000=66*15+10。所以 |A3∩A5|=66。 同理可得 |A3∩A7|=47（1000=47*21+13）； |A5∩A7|=28（1000=28*35+20）。 既能被3整除，又能被5整除，还能被7整除的数的集合为集合A3、集合A5和集全A7的交集A3∩A5∩A7，它的元素的个数为 |A3∩A5∩A7|=9（（1000=9*105+55） 根据容斥原理，有 |A3∪A5∪A7| = |A3|+|A5|+|A7| - |A3∩A5| - |A3∩A7| - |A5∩A7| + |A3∩A5∩A7| = 333+200+142-66-47-28+9 = 543 所以，1到1000这1000个正整数中，能够被3整除，或能够被5整除，或能够被7整除的数有543个。
| 
发表于 2022-1-22 11:41:25
置顶卡