设有1999个集合,每个集合有45个元素,任意两个集合的并集有89个元素,问此1999个集合的并集有多少个元素就是不明白这里的抽屉原则,为什么1999个集合中必有一个集合A中的元素a出现在A以外的45

Question

设有1999个集合,每个集合有45个元素,任意两个集合的并集有89个元素,问此1999个集合的并集有多少个元素
就是不明白这里的抽屉原则,为什么1999个集合中必有一个集合A中的元素a出现在A以外的45个集合中

Answer 1

任意两个集合,恰有一个公共元素.
取定一个集合A,其他的1998个集合中的每个集合都会与A有一个公共元素.
把A中的每个元素看成一个抽屉,那么我们有45个抽屉.
设A={a(1),a(2),...,a(45)}.
对任意的一个集合B(B不等于A),若B与A的交为{a(k)},就把a(k)这个抽屉里放进一个球.
不等于A的集合有1998个,检查每个这样的集合与A的交,就相当于向45个抽屉放入1998个球.
因1998/45 = 44.4,因此,至少有一个抽屉里的球数不少于45.
即存在某个a=a(k),使得至少有45个不同于A的集合,这些集合中的每个集合与A的交都是{a}.
这就意味着,a至少属于45个不同于A的集合.
设B(1),B(2),...,B(45) 都是不同于A 的集合,他们两两不同,且每个B(j)都与A有公共点a.
对除了A以及B(1),B(2),...,B(45)之外的其他任一集合C,
我们来论证C必然也与A有公共点a,即a属于C.
否则,a不属于C.
因每个B(k)都与C相交,故每个B(k)\{a}也与C相交.
但这些B(k)\{a}两两不交,所以,B(k)\{a}与C的公共元素也两两不同.
这说明C包含于这些B(k)\{a}的并集.
而上述的并集与A不交,所以C与A不交,矛盾.
所以,a属于这1999个集合中的每一个集合,因此他们的并中有1999*(45-1) + 1 = 87957个元素.