2011-06-10, 09:19 PM
That's basically a graph connectedness question.
Basically, set up relationships between people as lines connecting them.
Do a cut that contains 3 people.
- all connected: they all know each other
- all unconnected: they don't know each other
- 2 connected, 1 isol: okay
So basically the question is, what's the largest number composed entirely of that third option. Plus 1.
3 people: possible. A knows B, neither know C.
Inductive: try to add a person so that none of the possible sets of 3 gain someone attached to the pair.
ie. 4th person must know C.
4 people: A knows B, C knows D.
Try again. How do we add a 5th person? If we add it to an existing group (knowing any of the 4) that forms 3 who know each other. If we add it outside, we get 3 who know nothing about anyone else in the group.
So... 5 people.
Basically, set up relationships between people as lines connecting them.
Do a cut that contains 3 people.
- all connected: they all know each other
- all unconnected: they don't know each other
- 2 connected, 1 isol: okay
So basically the question is, what's the largest number composed entirely of that third option. Plus 1.
3 people: possible. A knows B, neither know C.
Inductive: try to add a person so that none of the possible sets of 3 gain someone attached to the pair.
ie. 4th person must know C.
4 people: A knows B, C knows D.
Try again. How do we add a 5th person? If we add it to an existing group (knowing any of the 4) that forms 3 who know each other. If we add it outside, we get 3 who know nothing about anyone else in the group.
So... 5 people.