Problem
COM-B2-M04-P012 Players Who Know Everyone
In a group of \(n\ge 3\) people, acquaintance is mutual. It is known that at least one person does not know everyone. What is the largest possible number of people who can still know everyone else? Prove your answer.
If there were \(n-1\) such people, what would happen to the remaining person?
The answer is \(n-2\). First show that \(n-1\) is impossible. If \(n-1\) people know everyone, then the remaining person knows each of these \(n-1\) people. Hence the remaining person also knows everyone, contradicting the condition.
Now show attainability. Let two people \(A\) and \(B\) not know each other, while everyone else knows everyone. Then exactly \(n-2\) people know all others, and \(A\) and \(B\) do not know everyone. The condition is satisfied.
The idea is inspired by a standard olympiad-style question about the maximum number of universal vertices, but the statement and solution are prepared as an original training problem.