9
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ How did you get that $\min_v\mathrm{deg}v=n$? $\endgroup$ – Leaning Jul 5 '18 at 19:22
  • 3
    $\begingroup$ 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. $\endgroup$ – Barry Cipra Jul 5 '18 at 19:42
  • $\begingroup$ @BarryCipra My bad, thank you. Corrected the description $\endgroup$ – Wunsch Punsch Jul 5 '18 at 20:21
14
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

Transform the problem to graph theory and look at the complement of the graph and use contradiction.

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.

This is clear, take a bipartition of any spanning forest (that respects components) of the graph, and after that push some vertices from the larger part to the smaller part so that the sides have the desired size.

$\endgroup$

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.