In: Advanced Math
There are (m − 1)n + 1 people in a room. Show that either there are m people who mutually do not know each other, or there is a person who knows at least n others.
If there is a person who knows at least n others then there is nothing to prove.
So assume that no person knows at least n others. That is, given any person, that person knows at most n persons(including himself).
Consider one person among them, say P1. Then since that person knows at most n persons, there are surely (m-1)n+1-n=(m-2)n+1 persons that he doesn't know. Consider a person P2 among them.
So, P1,P2 do not know each other mutually.
Now P2 knows at most n persons among those (m-2)n+1. Thus there are at least (m-3)n+1 in those (m-2)n+1 persons that he doesn't know. Pick a person P3 among them. Now P1,P2,P3 do not know each other mutually.
Continuing like this, we get P1,P2,...,P(m-1) such that they do not know each other mutually and since (m-(m-1+1))+1=1, we are left with at least one person who doesn't know P1,...,P(m-1) mutually. Call that person as Pm.
Thus we have got m persons P1,...,Pm who do not know each other mutually.
This completes the solution.