Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon.

Pages: 1-

Pigeon Hole principle

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?

Name: Anonymous 2006-11-13 20:44

use graph theory and with two vertices (people) joined by an edge if they know each other. then show that there exists at least one vertice v of degree 4.

can't be bothered to rephrase the second in therms of graph theory.

Don't change these.
Name: Email:
Entire Thread Thread List