2006个人分成若干不相交的子集
问题描述：
2006个人分成若干不相交的子集
2006个人分成若干不相交的子集,每个子集至少有3个人,并且:
(1)在每个子集中,没有人认识该子集的所有人;
(2)同一子集的任何3个人中,至少有2个人互不认识
(3)对同一子集任何2个不相识的人,在该子集中恰好只有1个人认识这两个人.
则 满足上述条件的子集最多有能有 个.
答
取其中一个满足要求的子集A来分析：
A＝｛a1,a2,a3...an (n>=3)｝
a1,a2,a3中至少有2个人互不认识 ,假设a1和a2不认识!
则：A中必只有一个人am认识a1和a2!
而A中除了am所有的人都不认识a1和a2!
再看看,认识am的人都有谁,显然a1和a2认识!
若还存在一个am1认识am,则：am1不认识a1,不认识a2
所以：A中必定有且只有一个am2认识am1和a1!
而上面我们说到A中除了am所有的人都不认识a1和a2!
所以我们假设的am1不成立!
换言之,认识am的人就只有a1和a2!
假设集合中的另一个元素am3,显然他不认识am,
那么显然根据（3）,集合中必有一个人认识am,和am3
而我们说了认识am的人就只有a1和a2!
所以我们假设的am3不成立!
所以A中只能有3个元素!｛a1,a2,am｝
但是这样的话am就认识了集合中的所有人,不符合（1）
所以这样的子集是不存在的!