Best Answer m00li, 28 April 2014 - 10:35 PM

lets look at an ALIEN world of n people {a_{1},a_{2},a_{3},....,a_{n}} and conjecture that there is NO triplet of 3 in this group that

either ALL know each other

or NONE know each other

What is the maximum population possible in such a world?

__Scenario 1:__ Let's look at a_{1}. He knows k people in this world. Assume, he knows a_{2},a_{3},..,a_{k-1}. Now, if any of a_{1}'s k acquaintances know each other (say a_{3 }and a_{2}) then we have a triplet which MUTUALLY knows each other (namely a_{1},a_{2},a_{3}). Hence NO pair of a_{2},a_{3},..,a_{k+1} can know each other. But, if that's true AND k is >2, we can find a triplet from these k folks who MUTUALLY don't know each other. Hence k<=2 OR there can be no body in SUCH an alien world who knows more than 2 people.

__Scenario 2:__ let's think of the converse case, where a_{1} doesn't know k people, say a_{2},a_{3},..,a_{k-1}. If any pair among this k do not know each other, (say a_{3 }and a_{2}), we will again have a triplet (namely a_{1},a_{2},a_{3}) which mutually doesnt know each other. Hence each of a_{2},a_{3},..,a_{k+1} must know each other. But, if that's true AND k is >2, we can find a triplet from these k folks who mutually know each other. Hence k<=2 OR everyone in this alien world knows atleast 2 people.

The above two scenarios make it clear that any person in this alien world can have maximum two acquaintances and two strangers thus restricting the population to **5**.

Hence proved.