# There are $2n+1$ people. For each $n$ people there is somebody who is friend with each of them. Prove there is a “know-them-all” person.

I have a following problem.

There are $2n+1$ people in the room. For any group of $n$ people there is a person (different from them) who is friends with each person in this group. Prove that there is a person, who knows all $2n$ other people.

One can easily see, that $\min_v \deg v = n$. From this we can get a lower bound for number of edges $N_e$: $$N_e = \frac{1}{2}\sum_v \deg v \geq \frac{(2n+1) \cdot n}{2}$$ I do not know where to move from this point (and do not think, that this is the right direction) and pretty stuck right now. Can you give a hint?

• How did you get that $\min_v\mathrm{deg}v=n$? – Leaning Jul 5 '18 at 19:22
• Is "knowing" a reciprocal relation? E.g., I "know" plenty of movie stars, but I'm pretty sure they don't know me from Adam. – Barry Cipra Jul 5 '18 at 19:42
• @BarryCipra My bad, thank you. Corrected the description – Wunsch Punsch Jul 5 '18 at 20:21

Say a group $M$ is good if everyone in $M$ knows everyone in $M$. Note that such group exist (say with $2$ people).
Take maximal good subgroup $M$. If size of this group $M$ is $k\leq n$ then there is somebody who knows them all. So we can add him to this group and we get new good group $M'$ which is bigger then $M$. A contradiction. So $M$ is of size $k\geq n+1$. Then in $M^C$ we have at most $n$ people, so there is somebody in $M$ who know everybody in $M^C$. But then this one knows everybody.
We have a graph with $2n+1$ vertices in which every vertex has degree at least $1$ and we must prove we can split into groups of size $n$ and $n+1$ such that each vertex in the group of size $n+1$ has an edge to the other size.