BMAD Posted April 28, 2014 Report Share Posted April 28, 2014 Prove that in any group of 6 people, at least 3 must be either mutually acquainted with each other, or mutually unacquainted with each other. Quote Link to comment Share on other sites More sharing options...

0 m00li Posted April 28, 2014 Report Share Posted April 28, 2014 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. Quote Link to comment Share on other sites More sharing options...

0 bonanova Posted April 28, 2014 Report Share Posted April 28, 2014 Not really a proof.Color each edge of a complete 6-node graph either red (friends) or blue (strangers.) There will be a red triangle or a blue triangle. A proof would be to inspect all such colorings. Quote Link to comment Share on other sites More sharing options...

0 BMAD Posted April 29, 2014 Author Report Share Posted April 29, 2014 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. Well stated but I have two issues: you said the max population is 6 but I asked you to prove for 6. Mutually unacquainted is not the opposite of mutually acquainted. I forget the English word for what I mean...is it contrapositive. As in ...if it isn't night it is day (mutual Acquaintances do not work this way) Quote Link to comment Share on other sites More sharing options...

0 BMAD Posted April 29, 2014 Author Report Share Posted April 29, 2014 I mean you said 5 but I said prove 6 Quote Link to comment Share on other sites More sharing options...

0 m00li Posted April 29, 2014 Report Share Posted April 29, 2014 I proved that if there is a group which does not satisfy your condition, then its population CANNOT be more than 5. Hence, if the population is more than 5 (6,7,8,...) it HAS to satisfy your condition. My proof doesnt state that mutual acquaintances and mutual strangers are the only two possibilities, rather it states that we cannot have a group of more than 5 ever, where the size of both mutual acquaintances and mutual strangers is less than 3. Quote Link to comment Share on other sites More sharing options...

0 bonanova Posted April 29, 2014 Report Share Posted April 29, 2014 I would agree that any pair of two people are either strangers or acquaintances. That is A cannot know B unless B also knows A, and A cannot be a stranger to B unless B is also a stranger to A. So ... Each of the six people has a relationship F(riend) or S(tranger) with each of the other five. By the pigeonhole principle there must be at least three of one or the other. WOLOG we can say that one of the persons, call him Sam, is F with at least three of the others. There are two cases If the three others all have mutual S relations, they comprise an S trio. If any pair of the other three are F, they and Sam form an F trio. Q.E.D. Quote Link to comment Share on other sites More sharing options...

0 bonanova Posted May 1, 2014 Report Share Posted May 1, 2014 m00li's post #3 answers the OP. Post #4 stated two objections. Let's look at the objections. [1] Differences between 5 and 6. OP asks for proof that in a group of 6 people condition A or condition B exists. Post#3 proves that if A or B does not exist the group can have no more than 5 people. "Not (A or B) implies less than 6" is logically the same as "6 implies (A or B)." [2] "Mutually unacquainted" is different from "not mutually acquainted." Post #3 (and post #7, but post #3 was first) assume they are the same. If there is a third possibility then no proof exists. To show this, let's construct a third, asymmetrical relationship: Let's say that I am acquainted with someone who is not acquainted with me. Say a groupie (not the fish) is "acquainted" with a Rock Star who is not acquainted with the groupie. Since the groupie knows the star, they cannot be "mutually unacquainted."Since the star does not know the groupie, neither can they be "mutually acquainted."All that can be said of them is that they are "not mutually acquainted." Using "mutually unacquainted" and "not mutually acquainted" as different relationships prevents the requested proof. Here's how that might play out. Among three rock stars, Elvis knows Mick and Bob, but Mick and Bob are strangers. Among three groupies, Sam knows Pete and Jane, but Pete and Jane are strangers. Sam, Pete and Jane, being groupies, all know Elvis, Mick and Bob None of Elvis, Mick and Bob know any of Sam, Pete and Jane. No three of six are "mutually acquainted" No three of six are "mutually unacquainted" Ergo, with that interpretation there is no proof. Mick, Bob, Pete and Jane, however, are "not mutually acquainted." With that interpretation the proof exists. Quote Link to comment Share on other sites More sharing options...

## Question

## BMAD

Prove that in any group of 6 people, at least 3 must be either mutually acquainted with each other, or mutually unacquainted with each other.

## Link to comment

## Share on other sites

## 7 answers to this question

## Recommended Posts

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.