4

title can't exactly capture the description of this problem so well. Here's the question in full:

"At a convention, any group of four people contains one who knows the other three. Prove there is someone at the convention who knows everyone else."

I've tried to prove this inductively, but am not sure whether or not that is the correct way to go about it.

Induction Hypothesis: Assume that there is someone at the convention who knows everyone else, given that any group of four people contains one who knows the other three (assume this is true given $n$ people).

Basis case: there are four people at the convention. Therefore, there is one in this group of four who knows the other three (everyone else at the convention).

Induction step: Prove this is true for $n+1$ people. We see that this is the same as inserting one more person into a convention with $n$ people, where there must be someone who knows everyone. Therefore, we only need to show that this person who knows everyone also knows the $n+1$th person we're inserting. And I'm stuck.

If anyone could help me out here, that would be greatly appreciated. Thanks!

2 Answers2

9

This is a way to do it without induction.

Choose any person, say $A$. First, we claim that $A$ knows everyone, except possibly for $2$ people. Suppose that there are three people that $A$ does not know, say $B$, $C$, and $D$. Then the quadruple $\{A,B,C,D\}$ violates the given condition, so the number of people that $A$ does not know is at most $2$.

If $A$ knows everyone, then we are done. If $A$ does not know some person, then call this person $B$.Let $C$ and $D$ be two people other than $A$ or $B$. Then in the quadruple $\{A,B,C,D\}$, the person who knows everyone else in the quadruple cannot be $A$ or $B$, so it must either be $C$ of $D$; in particular, $C$ and $D$ always know each other. This tells us two things. First, since $C$ and $D$ were chosen arbitrarily, every pair of people, not including $A$ or $B$, knows each other. Second, one of $C$ or $D$ must know both $A$ and $B$. Therefore, one of $C$ or $D$ knows everyone.

Thus, we are done!

Pakquebchsoflwty
  • 696
  • Thank you for the explanation on another way to approach this problem! –  Oct 25 '14 at 19:39
3

I will assume that knowing someone is symmetric, i.e. if person X knows Y then Y knows X.

Lets call the $n+1$-th person B. Before B joined someone must have known everyone at the convention, call her A. Now suppose that A doesn't know B and that the convention still has the property that in all groups of 4 there is someone who knows the others. Then we have to show that there is someone else at the convention who knows everyone else.

For any pair of people C and D that aren't A or B we know that either C or D must know all of the others in the group ABCD. In both cases C and D know each other. This shows that any person that isn't A or B knows all other people that aren't A or B. Now pick a specific pair of such people one of them must also know A and B and so he knows everyone at the convention!

MichalisN
  • 5,402
  • Thank you for the explanation! That makes the induction so much clearer here. –  Oct 25 '14 at 19:39