There is $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 either knows both or else knows neither of the two. Assume that "knowing" is a symmetric relation, and that $\lfloor n/2\rfloor$ denotes the greatest integer less than or equal to $n/2$.
Source: Principles and Techniques in Combinatorics by Koh and Chen.
Here is my idea:
Either a person knows someone or not. If there is at least $2$ people who do not know any one or who know $0$ person then I can take these two people and I am sure that these two are unknown to the remaining $n-2$ people.
So suppose the number of people who do not know anyone is $1$ or zero.
Let us start if there are no people who do not know anyone (everyone knows someone). So the only possible number of friends a person can have is from $1, 2, 3, . . , n-1$. Or $n-1$ choices. Since there are n people by Pigeonhole Principle there will be at least two that will have the same number of friends. Let these two be $P1$ and $P2$. Let $k=$ the number of friends of $P1=$ the number of friends of $P2$.
Let
$A=$ the set contaning $P1$ and its $k$ friends. $|A|=k+1$
$B=$ the set contaning $P2$ and its $k$ friends. $|B|=k+1$
If $A$ and $B$ are disjoint then $|A|+|B|=2k+2\leq n$ or $k\leq\frac{n}{2}-1$.
Here comes my problem. Since if $k=\frac{n}{2}-1$ then $|A|=|B|=\frac{n}{2}$ and $A$ and $B$ are disjoint, I can't show what the problem is asking.
Any idea guys? Maybe some hints. :) Thanks.
UPDATE
I just found out that this problem is similar to the following:
A graph has $n>2$ points. Show that we can find two points $A$ and $B$ such that at least $\lfloor n/2\rfloor-1$ of the remaining points are joined to either both or neither of $A$ and $B$.
Which is a problem in 1985 USAMO.
I don't quite understand the solution though.
This is not a solution, but is aimed at why the approach of equal number of friends can't work. Suppose $n=4$ and the people are $a,b,c,d$ and they are arranged in a line $abcd$ where $x$ knows $y$ if and only if $x,y$ are adjacent on the line. Then the ends $a,d$ each have $1$ friend, and the inners $b,c$ each have $2$ friends, yet neither pair works.
Since here $n/2-1=1$ a pair works iff they have either a common friend or a common non-friend. If you look at $b,c$ each with 2 friends, then $b$ knowns $a$ but not $d$, while $c$ knows $d$ but not $a$. So the pair $b,c$ doesn't work, even though each has $2$ friends. Similarly you can show the pair $a,d$ doesn't work.
On the other hand, any other pair does work, i.e. if you take two having different numbers of friends in this example, that pair works. Here this means taking one at an end and the other in one of the inner positions. For example the pair $a,b$ each does not know $d$, so that pair $a,b$ works, while pair $a,c$ each knows $b$, so that the pair $a,c$ works. (The other two possibilities are symmetric to these.)
It seems from this example that one has to look at more than just some property of an individual, such as number of friends, to prove this statement.