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$.


$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.


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.

  • $\begingroup$ Your attempt has good motivation. However maybe there could be a case of a correct choice of the two people, for which they don't both have the same number of friends. Interesting problem, but does it come from some known source or is it only a conjecture by you? [this info should be in the post, IMO] $\endgroup$ – coffeemath Aug 29 '13 at 8:49
  • $\begingroup$ I've added the source. I'm self-studying combinatorics and this book has a lot of good examples. I'm still working on this problem. :) Any ideas? $\endgroup$ – chowching Aug 29 '13 at 8:59

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.

  • $\begingroup$ But sir in your argument above, the one with 4 people; we can choose the two people as $a$ and $b$ both who are not friends with $d$. So we have $n/2 - 1=1$ people i.e. $d$ who does not know the two people $a$ and $b$. This works because $a$ is friends with only $b$ and $d$ is friends with only $c$. We can also choose $c$ and $d$ as the two people because we can get one person i.e. $a$ who does not know both of them. $\endgroup$ – chowching Aug 29 '13 at 11:25
  • $\begingroup$ @chowching Yes you're right. The only point of my example is that, if we insist the two chosen people have the same number of friends (as in your attempted argument), then it might not work. Note that $a$ has one friend and $b$ has two friends, so your approach would not consider this choice, since in your approach you start with two people who have the same number of friends. Also $c$ has two friends and $d$ has one. But in my example you cannot find two people $x,y$ who have the same number of friends, and where the pair $x,y$ works. $\endgroup$ – coffeemath Aug 29 '13 at 11:47
  • $\begingroup$ Oh I see now. So what I have to look for now is an explanation such that if $P1$ and $P2$ have the same number of friends and that the pair $P1$ and $P2$ does not satisfy what is asked in the problem (it is possible that the pair will satisfy) then I can find two others which will. $\endgroup$ – chowching Aug 29 '13 at 12:34
  • $\begingroup$ @chowching Yes, that's right. And maybe just starting with any pair with same number of friends, and they don't satisfy, then that info can be used later by keeping one of them and trying with some other. But also maybe another approach is needed where you don't consider numbers of friends individually. $\endgroup$ – coffeemath Aug 29 '13 at 12:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.