Mutual relations

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

[m00li]

lets look at an ALIEN world of n people {a₁,a₂,a₃,....,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₁. He knows k people in this world. Assume, he knows a₂,a₃,..,a_k-1. Now, if any of a₁'s k acquaintances know each other (say a₃ and a₂) then we have a triplet which MUTUALLY knows each other (namely a₁,a₂,a₃). Hence NO pair of a₂,a₃,..,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₁ doesn't know k people, say a₂,a₃,..,a_k-1. If any pair among this k do not know each other, (say a₃ and a₂), we will again have a triplet (namely a₁,a₂,a₃) which mutually doesnt know each other. Hence each of a₂,a₃,..,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.

[bonanova]

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.

[BMAD]

lets look at an ALIEN world of n people {a₁,a₂,a₃,....,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₁. He knows k people in this world. Assume, he knows a₂,a₃,..,a_k-1. Now, if any of a₁'s k acquaintances know each other (say a₃ and a₂) then we have a triplet which MUTUALLY knows each other (namely a₁,a₂,a₃). Hence NO pair of a₂,a₃,..,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₁ doesn't know k people, say a₂,a₃,..,a_k-1. If any pair among this k do not know each other, (say a₃ and a₂), we will again have a triplet (namely a₁,a₂,a₃) which mutually doesnt know each other. Hence each of a₂,a₃,..,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)

[BMAD]

I mean you said 5 but I said prove 6

[m00li]

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.

[bonanova]

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

1. If the three others all have mutual S relations, they comprise an S trio.
2. If any pair of the other three are F, they and Sam form an F trio.

Q.E.D.

[bonanova]

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.

1. Among three rock stars, Elvis knows Mick and Bob, but Mick and Bob are strangers.
2. Among three groupies, Sam knows Pete and Jane, but Pete and Jane are strangers.
3. Sam, Pete and Jane, being groupies, all know Elvis, Mick and Bob
4. None of Elvis, Mick and Bob know any of Sam, Pete and Jane.
5. No three of six are "mutually acquainted"
6. No three of six are "mutually unacquainted"
7. Ergo, with that interpretation there is no proof.
8. Mick, Bob, Pete and Jane, however, are "not mutually acquainted."
9. With that interpretation the proof exists.