BrainDen.com - Brain Teasers
• 0

# Mutual relations

## Question

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.

## Recommended Posts

• 0

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

##### Share on other sites

• 0

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.
##### Share on other sites

• 0

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

##### Share on other sites

• 0

I mean you said 5 but I said prove 6

##### Share on other sites

• 0

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.

##### Share on other sites

• 0

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.

##### Share on other sites

• 0

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.

## Join the conversation

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

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.