已知在n个人中,任意3人中至少有2人相互认识.任意4人中至少有2人相互不认识.求n的最大值.

Question

已知在n个人中,任意3人中至少有2人相互认识.任意4人中至少有2人相互不认识.求n的最大值.

Answer 1

6个
先任选4个人 编为 1,2,3,4
因为至少要有2人互不认识
且任意的3个人 至少有2个相互认识
所以我们不妨假设 1,2相互认识 1,3相互认识,2,3相互认识 4和其他人都不认识
现在加入 一个人 5
他不能和 1,2,3中任何一个人相互认识
因为一旦认识 就不满足 任意4人中至少有2人相互不认识
所以他 必须和 4 相互认识 因为也不认识的话
就不满足 任意的3个人 至少有2个相互认识 （例如 1,4,5）
所以现在的情况是 1,2,3,一组 4,5一组
现在再加入一个人 6
同样的 他也不能和 1,2,3相互认识
所以 现在就是 1,2,3一组4,5,6一组
然后再加入一个人 7
不管他加入那组 都不行
因为加入会 不满足 任意4人中至少有2人相互不认识
而不加入 会 不满足 任意的3个人 至少有2个相互认识 （例如 1,4,7）
所以 最多的 情况是 6人