Q. 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{\frac{n}{2}}\rfloor-1$ of them, each of whom either knows both or else knows neither of the two. Here, "knowing" is a symmetric relation and $\lfloor{x}\rfloor$ denotes the greatest integer function.
I am aware of a solution that utilises Pigeonhole Principle to solve the problem. However, I was wondering whether there existed a way to solve this question using invariance, as usually in systems such as these, there is usually one key aspect that is invariant and which solves the problem easily.
This is just a thought. If anyone knows any resources that might help or provide a proof itself, it would be a great help. Thanks a lot :). By the way, this problem appeared in USAMO 1985/4