There are $n$ people at a party. Prove that there are two people such that, of the remaining $n-2$ people, there are at least $\lfloor n/2\rfloor -1$ of them, each of whom knows both or else knows neither of the two. Assume that "know" is a symmetrical relation; $\lfloor x\rfloor$ denotes the greatest integer less than or equal to $x$.
I saw a solution: Consider the number of pairs $(X, \{Y, Z\})$, where $X, Y, Z$ are distinct points such that $X$ is joined to just one of $Y, Z$. If $X$ is joined to just $k$ points, then there are just $k(n - 1 - k) \leq (n - 1)^2/4$ such pairs $(X, \{Y, Z\})$. Hence in total there are at most $n(n - 1)^2/4$ such pairs. But there are $n(n - 1)/2$ possible $\{Y, Z\}$. So we must be able to find one of them $\{A, B\}$ which belongs to at most $[ (n - 1)/2 ]$ such pairs. Hence there are at least $n - 2 - [ (n - 1)/2 ] = [n/2] - 1$ points $X$ which are joined to both of $A$ and $B$ or to neither of $A$ and $B$. [If confused by the $[ ]$, consider $n = 2m$ and $n = 2m+1$ separately. But I don't understand the following inequality $k(n - 1 - k) \leq (n - 1)^2/4$. Someone can help me ou have other solution, please?
Thanks a lot!
Since $X$ is joined to $k$ points, to choose the set $\{Y,Z\}$, we must choose one point $X$ is joined to, and one point $X$ is not joined to. There are $k$ choices for the first point and $n-1-k$ choices for the second. Hence the number of pairs $\{Y,Z\}$ is equal to $k(n-1-k)$, which by the inequality $a(2b-a)\le b^2$, cannot exceed $(n-1)^2/4$.