|
     
|
Question: Suppose you have a group of six people. Each pair of people are either friends or enemies. Is there a subset of three people who are either mutually friends or mutually enemies? If so, prove it. If not, construct a counterexample. Answer: I assert that there is always a group of either three mutual friends or three mutual enemies in a group of 6 people in which each pair of people are either friends or enemies. Proof: First we need some notation. Consider each person as a vertex in a completely connected simple graph. Each edge is labled "friends" or "enemies". Lets say 'f' and 'e' for brevity. Now lets assume, towards contradiction, that we have a graph fitting the above description such that for all sets of three verticies, t= {n1, n2, n3}, there is no t' such that {n1', n2'} ={n2', n3'} = {n1',n3'}. In order for this to occur, each t must have the property that {n1, n2} does not equal {n1, n3}. Now consider any particular t in a graph with no mutual friends or enemies. It has the property that two of its edges, {n1, n2} and {n1, n3} both = p, which is either e or f. The other edge, {n2, n3} = ^p (read: "not p". so if p = e, ^p = f, and if p = f, ^p = e). In other words, in a group of three people that are not all mutual friends or enemies, either one person is friends with the other two and the other two are enemies, or vice versa. Consider an arbitrary group of 5 people (labeled p1-5) in which each pair of people are either friends or enemies. Assume that there is no sub group of three whom are all mutual friends or enemies (if such a group of 5 people doesn't exist in the first place, then the proof is already done.) Now lets add a 6th person, p6. We must now add 5 new edges to the graph: {p6, p1}... {p6, p5}. There must be a degree 3 subset of these 5 new edges such that all three edges = p. This is true by the pigeon hole principle: if 5 pigeons fly into two holes, then one of the holes has three or more pigeons. Lets call these 3 pigeons, err, edges {p6, px} {p6, py} and {p6, pz} where x, y, z are distinct elements from {1, 2, 3, 4, 5}. Notice that px, py and pz are not a group of mutual friends or enemies, by our assumption. So among the edges {px, py} {py, pz} and {pz, px}, at least one = f (lets say {py, pz} = f) and at least one = e (lets say {px, py} = e) . If three of the new edges are all f, then {p6, py} {p6, pz} {py, pz} is a group of mutual friends. If three of the new edges are all e, then {p6, px} {p6, py} {px, py} is a group of mutual enemies. QED -- Dave Newquist |
