Help with Pigeon Hole Problems
 

Not looking for rigorous proofs here just looking for simple explanations why these are true demonstrating the pigeon hole principle.

Prove that in any polyhedron, there exist two faces with same number of edges.

The points of the plane are colored blue and red in an arbitrary way prove that there exist two points of the same color that are exactly sqrt(2) units apart.

Re: Help with Pigeon Hole Problems
 

I'll think about the first .

2) Consider an equilateral triangle with sides =sqrt2
If the only colors are blue and red , then there exists two points of the same color a distance sqrt 2 apart .

remark: The following is true for any arbitrary distance d .

Re: Help with Pigeon Hole Problems
 

[ QUOTE ]

Prove that in any polyhedron, there exist two faces with same number of edges.

[/ QUOTE ]
A polyhedron will have n faces. Each face will have at least 1 edge and at most n-1 edges. There are a total of n-1 different number of possible edges. Since there are n faces, at least two must have the same number of edges.

Re: Help with Pigeon Hole Problems
 

[ QUOTE ]
[ QUOTE ]

Prove that in any polyhedron, there exist two faces with same number of edges.

[/ QUOTE ]
A polyhedron will have n faces. Each face will have at least 1 edge and at most n-1 edges. There are a total of n-1 different number of possible edges. Since there are n faces, at least two must have the same number of edges.

[/ QUOTE ]

Tom you are my hero and I feel like an idiot now. thanks to both of you.

Re: Help with Pigeon Hole Problems
 

Homework solved.

Re: Help with Pigeon Hole Problems
 

Another proof for 1 .

Each face must have at least 3 edges since 1 and 2 edges are degenerate cases . Now we show that for a polyhedron with n faces , there cannot be a face with more than n edges . For if there were , then the polyhedron would have more than n faces . This is easy to check since for each edge there are 2 faces . So 2*(n+1) - (n+1) = n+1

So we have n faces and they may take on the values
{3,4,5,6,...,n} . This means that there exists two faces with the same number of edges .

Re: Help with Pigeon Hole Problems
 

I can honestly say, i have no idea what you guys are talking about.

what kind of math is this?

Re: Help with Pigeon Hole Problems
 

Discrete/finite mathematics

Re: Help with Pigeon Hole Problems
 

[ QUOTE ]
I can honestly say, i have no idea what you guys are talking about.

what kind of math is this?

[/ QUOTE ]

What kind of math do you take that you've never heard of the pigeonhole principle????

Re: Help with Pigeon Hole Problems
 

thanks jay

im up to chapter 6 in my intro to statistics class.
pigeonholes must be around chapter 13