`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.) (link) 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 (link) 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 (link) Jake: Or you could do it John's way, which is better. 9.19.2005 1:43pm (link) 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 (link) 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 (link) 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 (link) 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 (link) Sasha (mail): Oh yes, I meant to say: On the other hand, John Thacker and Jake are right. 9.19.2005 2:35pm (link) Kristian (mail) (www): Gah, Graph theory... 9.19.2005 2:41pm (link) 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 (link) 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 (link) 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 (link) 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 (link) Volokh groupie (mail): C'mon Kevin. This was the 1st problem in my intro combinatorics class. 9.19.2005 4:17pm (link) 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 (link) 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 (link) Syd Henderson (mail): They can form a mutual stranger society, which would never meet. 9.19.2005 4:33pm (link) 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 (link) 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 (link) MattJ (mail): Friends? Strangers? All those people are my enemies. We're hardly friends or strangers. 9.19.2005 5:36pm (link) 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 (link) 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 (link) 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 (link) 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 (link) 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 (link) 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 (link) 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 `pageok` `pageok`