Name: Anonymous 2006-11-13 0:19
Consider a party of n people (where n is even and n > 11). Clearly, everyone knows themselves. If n/2 of the peolpe know exactly 1 person other then themselves and n/2 of the people know exactly 5 people other than themselves:
1) Prove there is at least 1 person known to 4 people
2) Suppose that one of the people knows exactly 1 person realized that they knew someone else, which means that they know exactly 2 people other then tehmselves. Does this make a difference? Can there now be at least 1 person that is known to 5 people or does this not make a difference at all. Explain your answer.
I know this problem can be done by pigeon hole principle (probably the easiest way to do it) but I don't see what are the "boxes" are and I think that the n people are the pigeons. Anyone got any ideas?
1) Prove there is at least 1 person known to 4 people
2) Suppose that one of the people knows exactly 1 person realized that they knew someone else, which means that they know exactly 2 people other then tehmselves. Does this make a difference? Can there now be at least 1 person that is known to 5 people or does this not make a difference at all. Explain your answer.
I know this problem can be done by pigeon hole principle (probably the easiest way to do it) but I don't see what are the "boxes" are and I think that the n people are the pigeons. Anyone got any ideas?