【原创】原创题目【认识与不认识】

192557 · 发表于 2022-7-27 13:36:27

一所学校有m个学生，两个学生的关系可以用认识或不认识来表述（请注意，认识与不认识不是相互的，例如A认识B，B不认识A）如果认识一个人的人，比那个人认识的人多至少2个，就说他受欢迎，求受欢迎学生的最大个数。

89453 · 发表于 2022-7-27 19:44:44

155556 · 发表于 2022-7-29 14:14:08

m－2

假设有m－1个人认识a，但a都不认识那m－1个人，此时那m－1个人不是受欢迎的学生

再假设，有m－2个人认识a、b，但a和b都不认识那m－2个人，此时m－2个人正好为受欢迎学生

是这样吗

22568 · 发表于 2022-9-25 21:17:45

受欢迎即入度-出度>=2.
受欢迎集为A,补集为B.考虑A中所有点的入度-出度之和.
一方面,至少为2|A|.
另一方面,A内部的边无贡献,只剩AB间的边,故|A||B|>=2|A|.
于是至少剩2个.
显然只有两人认识剩下所有人,其他全都不认识即可.
(m过小就不说了.)

189380 · 发表于 2022-7-27 21:46:43

[如果认识一个人的人，比那个人认识的人多至少2个] 有点绕

[数学趣题] 【原创】原创题目【认识与不认识】