2006个人分成若干不相交的子集

279912922022-10-04 11:39:541条回答

2006个人分成若干不相交的子集
2006个人分成若干不相交的子集,每个子集至少有3个人,并且:
(1)在每个子集中,没有人认识该子集的所有人;
(2)同一子集的任何3个人中,至少有2个人互不认识
(3)对同一子集任何2个不相识的人,在该子集中恰好只有1个人认识这两个人.
则 满足上述条件的子集最多有能有 个.

已提交,审核后显示!提交回复

共1条回复
衣宁 共回答了18个问题 | 采纳率77.8%
取其中一个满足要求的子集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)
所以这样的子集是不存在的!
1年前

相关推荐

大家在问