有 个集合,每个集合有 个元素,任意两个集合的并集有 个元素。 求这 个集合的并集的元素个数。
这是解答题,请在纸上写出完整过程。写完后对照解答给自己评分。
先由两个集合的并集大小求出交集大小。
固定一个集合后,把其余集合按唯一交点分类,用抽屉原理找高频元素;再让一个不含该元素的集合同时去碰这些集合,检查容量是否足够。
记这些集合为 。由容斥,任意两个不同集合的交集大小都是 。 固定 ,其与其余 个集合各有一个交点。因 , 的某个元素 至少属于另外 个集合。 取其中 个,与 合成 个均含 的集合。这 个集合的任意两个交集恰为 。 若原集族中有集合 不含 ,它必须与上述每个集合相交,而且这 个交点两两不同:若某点重复,就会同时属于两个集合而不等于 ,违背唯一交点条件。 于是 ,与 矛盾。因此所有集合都含 ,除 外两两不交。 所求并集元素数为
每个集合45次元素出现,总出现数为 。若共同点只在并集中算一次,重复计入的次数正为 ;从总出现数扣去这一项可再核验计数。抽屉步骤用的是 ,必须是另外1986个集合,不是1987个。
两两只有一个交点的等势集族,可用“某点高频出现—不含它者容量超限”把局部交条件提升为全族公共点。公共点之外才可以直接相加;在证明这一步之前,不应假定不同集合的其他元素互不相同。
核心是由抽屉原理选出高频公共点,再用集合容量排除不含它的成员。
已记下,谢谢!