## 6 persons inside an elevator – the math

Prove that if 6 persons are inside an elevator then there is a subgroup of 3 persons that know each other or a subgroup of 3 persons that don’t know each other. Note: for this problem if A  knows B then B also knows A (symmetric relation).

In the previous post I presented an algorithm that check the above statement. Here I will show the mathematical proof. Thanks to J who actually found this nice proof ;).

Consider one person $p_1$. There are other 5 persons that he can know or not. If $p_1$ dont’t know at least 3 of them  (case 1 is $p_1$ knows 3 of them)  then it means that there are 3 persons that $p_1$ don’t know (case 2).

Consider $A= {p_2, p_3, p_4}$ the persons $p_1$ know (case 1) or that $p_1$ don’t know (case 2).

For case 1, if there are to persons $p_i$ and $p_j$ in A that know each other it means that ${p_1, p_i, p_j}$  is a group of 3 persons that know each other. Otherwise, if any two persons from A don’t know each other it means that A is a subgroup of 3 persons that don’t know each other.

Case 2 is similar to case 1, just replace ‘don’t know’ with ‘know’ and  ‘know’ with ‘don’t know’.