May I ask if anyone has any tips on where to start with this:
What's the minimum number of people you can have in a room so you can find three people (A,B,C) such that either:
a) A has never met B, A has never met C, B has never met C
b) A has met B, A has met C, B has met C
Apologies for my dumbness(Thinking)
February 10th 2010, 07:12 PM
Suppose one of the people is Bob. Amongst the 5 other people, Bob knows at least 3 of them or he doesn't know at least 3 of them. Without loss of generality, suppose he knows three of them. Amongst those 3 people, if two of them know each other, then those two, along with Bob, are three people who know each other and we're done. Otherwise those three people don't know each other and we're done also!