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’.

Advertisements
This entry was posted in Math. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s