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 . There are other 5 persons that he can know or not. If dont’t know at least 3 of them (case 1 is knows 3 of them) then it means that there are 3 persons that don’t know (case 2).
Consider the persons know (case 1) or that don’t know (case 2).
For case 1, if there are to persons and in A that know each other it means that 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’.