Thread: Problem Solving/Logic Problem

In a party with 100 people, among any set of four there is at least one person who knows each of the other three. There are three people who are not mutually acquainted with each other(that is none of the three knows any of the other two). Prove that the other 97 people know everyone at the party. (Assume that if A knows B, then B also knows A.)


I'm not sure I even understand the question, so I'm having trouble even getting started

Originally Posted by johnhisenburg87

In a party with 100 people, among any set of four there is at least one person who knows each of the other three. There are three people who are not mutually acquainted with each other(that is none of the three knows any of the other two). Prove that the other 97 people know everyone at the party. (Assume that if A knows B, then B also knows A.)

This a a clever graph theory question.
Suppose that are the three people who are not mutually acquainted with each other(that is none of the three knows any of the other two). Suppose two other people are not mutually acquainted with each other.
Consider the set . Is it true that among that set of four there is at least one person who knows each of the other three?
How does that prove it?

Originally Posted by johnhisenburg87

In a party with 100 people, among any set of four there is at least one person who knows each of the other three. There are three people who are not mutually acquainted with each other(that is none of the three knows any of the other two). Prove that the other 97 people know everyone at the party. (Assume that if A knows B, then B also knows A.)...

Remove the 3 who don't know each other from 100. You are left with 97 people who when divided in groups of 4 at least one knows the other 3. Let's look at one group:
{1,2,3,4} {1} knows {2,3,4}...now you can divide 97 people in groups of 4 in 3464840 ways! {1} placed in any group either knows 3 others or one person knows him. Now extend this analogy to person {2} ...{3}...{97} Hence, all know each other. [NB.: just kick the 3 out of the part!]

(I'll assume that everyone at the party knows themself - it doesn't really matter to the problem.)
Label the people P1, P2, P3, ... P100.
We're given that 3 of them are all mutual strangers. Without loss of generality, say they're P98, P99, and P100.
Claim 1: Each of the people P1 through P97 knows all 3 of those special ones (P98, P99, and P100).
Reason: Assume Claim #1 is false. Then one of them (let's say it's P21), doesn't know one of those special last three (let's say it's P98, so we're assuming that P21 doesn't know P98). In that case, the set of four people {P21, P98, P99, P100} would have no one who knew all the others in that set. (P21 doesn't know all the others, because P21 doesn't know P98. P99 doesn't know all the others, because P99 doesn't know P100 or P98. The same reasoning goes for P98 and P100.) But that contradicts what we're given. Thus the initial assumption ("Assume Claim #1 is false") was false, and so Claim #1 is proven.
Claim 2: Each of the people P1 through P97 knows all the other people P1 through P97.
Reason: Assume Claim #2 is false. Then there's some pair (in P1 through P97) who don;t know each other. Without loss of generality, assume it's P1 and P2. So P1 and P2 don't know each other. Now consider the set of 4 people { P1, P2, P98, P99 }. None of them know all the others in that set (P1 doesn't know P2, P2 doesn't know P1, P98 doesn't know P99, and P99 doesn't know P98). But that contradicts that at least one of those 4 must know the other 3. Thus the initial assumption was false, and so Claim #2 is proven.
Claim 3: The other 97 people (P1 through P97 in our labelling system) know everyone at the party.
Reason: By Claim #1, each of those 97 people knows each of the special 3 people (P98, P99, P100). By Claim 2, each of those 97 people knows each of the non-special 97 other people (P1 through P97). Thus each of those 97 non-special people knows everyone at the party. QED
Restate it this way (where no edge means the two verticies know each other):
Proposition: Let G be a simple graph with 4 or more verticies, and the property that any induced subgraph on 4 vertices has at least one isolated vertex. If G contains a 3-clique, then G has exactly 3 edges.