pageok
pageok
pageok
[Puzzleblogger Kevan Choset, September 19, 2005 at 12:26pm] Trackbacks
Mutual Friends

Prove that in any group of 6 people, there must be either a group of 3 people who are all mutual friends or a group of 3 people who are all mutual strangers. (Some assumptions: Friendship is symmetric — if I'm friends with you, then you're friends with me; and any two people are either friends or strangers.)

John Thacker (mail):
Take one person. There are five other people, each of whom the first person can be friends or strangers with. Therefore, by the pigeonhole principle, either there are are at three people who are friends with the first person, or at least three people who are strangeres with the first person.

Without loss of generality, assume that there is a group of three people who are all friends with the first person. If any pair of them are mutual friends, then that pair plus the first person form a group of 3 mutual friends. If no pair are mutual friends, then that group of three people are all mutual strangers. The reverse argument holds if there is a group of three people all strangers with the first person.

Thus, either way there is a group of 3 people mutual friends or a group of 3 mutual strangers.
9.19.2005 1:39pm
Jake:
Let's number the people one through 6.

Person one could have six different numbers of friends:

If person one has 5 friends, then nobody else can be friends with each other without forming a group of three mutual friends (e.g. if 2 is friends with 3, then 1, 2, and 3 will be mutual friends), and if nobody else is friends with each other there will be five mutual strangers.

If person one has no friends, then nobody else can be strangers without forming a group of 3 mutual strangers, and if everybody else is friends with each other then there will be a group of five mutual friends.

If person one has one friend, then none of the four people that he is not friends with can be strangers, lest they form a group of three mutual strangers. And if everybody else is friends, then there is a group of four mutual friends.

If person one has two friends, then none of the three people that he is not friends with can be strangers with each other, or they will form a group of three mutual strangers. And if they are all friends, they form a group of three mutual friends.

The case of four friends is symmetric to the case of one friend, and the case of three friends is symmetric to the case of two friends (the same way that five friends is symmetric to no friends).
9.19.2005 1:42pm
Jake:
Or you could do it John's way, which is better.
9.19.2005 1:43pm
Bob Woolley (mail):
I'd approach it by considering each of the possible numbers of non-friended people.

If there are 0 non-friended people (NFPs), there can only be (A) 3 mutually exclusive groups of 2 friends, or (B) 2 exclusive groups of 3 mutual friends, or (C) 1 group of 2 friends and another group of 4 mutual friends, or (D) all 6 are mutual friends. Each possibility means that there is either at least one set of 3 or more mutual friends (B, C, and D), or at least one set of 3 or more strangers to each other (A).

If there is 1 NFP, the remaining 5 must be either (A) 5 mutual friends, or (B) one pair of 2 friends and a separate group of 3 mutual friends. Either way, there is one group of at least 3 mutual friends.

If there are 2 NFPs, the remaining 4 must be either (A) 4 mutual friends, or (B) 2 pairs of friends. In case B, a set consisting of one person from each pair plus the NFP form a set of mutual strangers.

For 3, 4, 5, and 6 NFPs, there is, by definition, at least one set of 3 people who are strangers to each other, regardless of what pairings are available to the rest.
9.19.2005 1:55pm
Zubon (mail) (www):
Just to note, you cannot have n-1 people who are strangers to everyone (5 NFPs). In that case, you would have 1 person who is friends with...himself?
9.19.2005 1:59pm
Brendon:
It seems to me that you just need to satisfy the worst case mutual stranger case. That's where each person is friends with the person to the right and left. 1 with 2, 2w/3, 3/w4 etc and 6w/1. In that case, there are no 3 mutual friends, but you can get 3 mutual strangers (1,3,5 or 2,4,6). In the case of 5 people, there isn't enough "space" for this to happen. 6 is the minimum for 3 non-connected friends.
9.19.2005 2:29pm
Sasha (mail):
I don't think Bob Wooley is right. Let "f" mean "is friends with" and "s" mean "is strangers with," and consider the following two groups: [A f B f C] (but [A s C]), and [X f Y f Z] (but [X s Z]). I don't think that fits into his categories.

As for Brendon, I don't think his scenario is the "worst case," assuming that's a useful concept. Surely the worst case for mutual friendship is that everyone is mutual strangers, and the worst case for mutual strangership is that everyone is mutual friends? Brendon's "friendship in a ring" scenario is some intermediate stage -- one way of arranging people but not necessarily the hardest way to achieve three mutual friends or three mutual strangers.
9.19.2005 2:34pm
Sasha (mail):
Oh yes, I meant to say: On the other hand, John Thacker and Jake are right.
9.19.2005 2:35pm
Kristian (mail) (www):
Gah, Graph theory...
9.19.2005 2:41pm
Bob Woolley (mail):
Sasha is clearly correct. I didn't account for that possible combination in my thinking or in my answer.
9.19.2005 2:55pm
Tom Anger (mail) (www):
Sasha got there before I did. I like the "friendless" group of six strangers. Fits my personality.
9.19.2005 3:16pm
Syd Henderson (mail):
Doing John's argument with labels:

Case(1) Suppose person A is friends with three people, B, C, and D. If any pair of B, C and D are friends, then that pair and A form a mutual admiration society. If no pair of B, C and D are friends, then they are a trio of mutual strangers.

Case (2) If A is friends with fewer than three of the others, than he is stranger to the rest, say D, E and F. If any pair of D, E and F are strangers, than that pair and A are mutually strangers. If no pair of D, E and F are strangers, then those three are the mutual friends.
9.19.2005 3:32pm
Ken B:
Draw edges in the graph, red between friends blue between strangers. These are disjoint sets and each vertex has 5 links. Thus you have a complete graph. Now call a node red if it has a red edge. At least half the graph must be red or non-red. (Same argument for green nodes too.)
9.19.2005 3:38pm
Volokh groupie (mail):
C'mon Kevin. This was the 1st problem in my intro combinatorics class.
9.19.2005 4:17pm
Kevin L. Connors (mail) (www):
This is a little too easy: For integers A and B, If (A < 3) and (B < 3) then A + B <= 4.
9.19.2005 4:21pm
Kevin L. Connors (mail) (www):
OH, wait. I breezed over the "mutual" qualifer. BTW, isn't the term "mutual strangers" redundant?
9.19.2005 4:26pm
Syd Henderson (mail):
They can form a mutual stranger society, which would never meet.
9.19.2005 4:33pm
Sasha (mail):
Whoa, who knew, but googling "mutual strangers" gives you links to exactly this problem, including to the very elegant proof from graph theory.
9.19.2005 4:49pm
Kevin L. Connors (mail) (www):
I agree with Volokh groupie. I don't know that I had this exact problem, but this is a classic proof by contridiction.
9.19.2005 4:54pm
MattJ (mail):
Friends? Strangers?

All those people are my enemies. We're hardly friends or strangers.
9.19.2005 5:36pm
byrd (mail):
I've been in groups of six where we were all friends. I've also been in groups of six where we were all strangers. And all the other combinations where there were neither three friends nor three strangers.

Obviously, everybody corrected the miswording on their own. Did anybody do it subconsciously so that you didn't even notice there was a miswording?
9.19.2005 6:55pm
Drewsil (mail):
My preffered method

Consider the most popular person (person with the most friends, in case of ties flip a coin). Assume that there is no group of 3 friends (completely connected subgraph with 3 vertices). Then there must be a group of three strangers as

if the most popular person has two or less friends then there will be at least 3 people that are strange to him. At least 2 of these three will also be strangers to each other by assumption (ie otherwise all 3 are friends). So there are 3 strangers (the most popular person and the 2 others he does not know).

If the most popular person has three or more friends then by assumption none of his friends know each other, and so must all be strangers, but there are at least 3 of them.
9.19.2005 7:00pm
Karl Lembke (mail) (www):
I notice many respondents are assuming you meant that a group of six people would necessarily contain at least three mutual friends or at least three strangers.

Did you?
9.19.2005 7:05pm
pbswatcher (mail) (www):
Karl Lembke indicates the crucial point. The assertion is true if the wording is "at least three mutual friends or at least three strangers." The alternative is "exactly three mutual friends or exactly three strangers" in which case the assertion if false, for example 6 mutual friends.
9.19.2005 8:43pm
Eric Jablow (mail):
Ah, Ramsey's Theorem. The simplest generalization is to change the numbers '3' in the question. For example, "What is the smallest number of people such that either [at least] 3 of them are mutual friends, or [at least] 4 of them are mutual strangers?" Call this R(3, 4). The answer is 9.

Ramsey's Theorem stares, among other things, that R(m,n) is always finite. [That's m mutual friends, or n mutual strangers.] However, it is extremely hard to compute, even for small m and n. All we know is that 43 ≤ R(5,5) ≤ 49, for example.

See MathWorld for details.
9.19.2005 10:55pm
FlavaFlay:
Karl Lembke and pbswatcher, the question states "there must be either a group of 3 people who are all mutual friends or a group of 3 people who are all mutual strangers."

The language of the question only asserts the existence of one of the two groups. One of these two groups may exist within a larger group for which the condition of complete "mutuality" is satisfied. For example, a group of 3 people who are all mutual friends exists in a group of 4 mutual friends.
9.19.2005 11:44pm
uh clem (mail):
Several good proofs. The only thing remaining is to provide a counterexample for a group of 5 to prove the 6 is the minimum number for which this is true.
Counterexample for 5:

A friends with E &B
B friends with A &D
C friends with E &D
D friends with C &B
E friends with A &C

or as a graph:

A
/ \
/ \
E B
\ /
\ /
x
/ \
D---C





There are others.
9.20.2005 12:38pm