March 1999
<<February March April>>
| (Part A): Pick a person arbitrarily, whom we will call Sam. Pick arbitrarily one of the people he knows; call her Julie. There are at most 33 people whom Sam does not know (including Sam himself), and at most 33 people whom Julie does not know, so among the 100 people in the room, at least 34 whom both Sam and Julie know; these 34 do not include Sam or Julie themselves. Pick one, say Bob. Argue the same way: among the 100 people in the room, at most 33 don't know Sam (including Sam himself), at most 33 don't know Julie, and at most 33 don't know Bob, so there is one person (Donna) known to all three. Then Sam, Julie, Bob and Donna form a clique. (Part B): Yes, by the same reasoning, because at the start of the process we picked the first person arbitrarily (and could pick Joe), and picked one of the people he knows arbitrarily (and could have picked Grace). Then continue as before. (Part C): Now there need not be a clique of four people. Suppose the 101 people are 33 freshmen, 34 sophomores and 34 juniors. Each person knows everyone in the other two classes but knows nobody in his own class. (It's a strange school.) Any set of four people would have to include two people from the same class, who don't know each other. |
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com