Functions - 5

COMP109 Lectures 2020-11-13

Theorem of Friends and Strangers

Show that in any group of six people there are either three who all know each other or three complete strangers.

On this graph blue is people who know each other and red is people who don’t. From the graph you can see that only two people will know each other.

What the question is saying is that no matter how you colour this you will always have a triangle of three people with red lines (don’t know) or blue lines (do know).

Proof

Let $A,B,C,D,E,\underset{―}{F}$ denote people under consideration.

Construct $f:\{A,B,C,D,E\}\to \{0,1\}$ as follows: $f(x)=1$ if $x$ knows $F$, or $0$ else.

This means that we are taking out the person $F$ and considering who they know in a binary format.

$|A|=5,|B|=2$ Therefore there must exist $\{x_1,x_2,x_3\}\subseteq \{A,B,C,D,E\}$ such that $f(x_1)=f(x_2)=f(x_3)$

Case 1

Suppose that $f(x_1)=f(x_2)=f(x_3)=1$. This means that they all know each other.

Dotted means don’t know.

Case 1.1

There is a pair who know each other.

Case 1.2

There is no pair who know each other.

So $x_1,x_2,x_3$ are complete strangers.

Case 2

$f(x_1)=f(x_2)=f(x_3)=0$

Dotted means don’t know.

Case 2.1

$x_1,x_2,x_3$ all know each other.

Case 2.2

Three is a pair who don’t know each other.

As you can see in any case there is a triangle of three people with links stating that they know or don’t know each other in any case. This proves the statement. This is as we can see that three know or don’t know each other in any situation.