Need some help with a proof (using the pigeon hole principle)

In summary, the conversation discusses using the pigeon hole principle to solve problems involving convex polygons with 2n vertices. The main problem the speaker is facing is proving that there is always at least one diagonal that is not parallel to any side of the polygon. They are seeking help and suggestions, and are looking for a connection between the number of diagonals and the number of vertices. They have found a formula for the number of diagonals in a polygon with 2n vertices, which they hope to use in their proof."
  • #1
allistair
20
0
I got 6 problems that I needed to proove using the pigeon hole principle and I was able to solve 5 of them but this last one is giving me some problems.

In each convex polygon with 2*n vertices there is at least one diagonal that isn't parallel with either one of the sides of the polygon.

I would appreciate some help to point me in the right direction or maybe an example of a similar proof that uses the pigeon hole principle, thanks in advance
 
Physics news on Phys.org
  • #2
isn't this a Descrete Maths problem?
 
  • #3
i'm obligated to use the pigeon hole principle, i can't use anything else (i'm not sure what you mean by 'discrete math', or did you mean that i posted this in the wrong forum?)
 
Last edited:
  • #4
How many diagonals are there? How many can be parallel to a side?
 
  • #5
I'm trying to find a function that gives the number of diagonals in funtion of the number of vertices but i don't see a connection both of them

i looked it up and apparently there is a formula for it, for a polygon with 2n vertices the number of diagonals is 2n*(2n-3)/2, i hope i'll be able to use this
 
Last edited:

1. What is the pigeon hole principle?

The pigeon hole principle is a mathematical concept that states that if there are more objects than containers to hold them, then at least one container must hold more than one object.

2. How is the pigeon hole principle used in proofs?

The pigeon hole principle is often used in proofs to show the existence of a certain outcome or scenario. It is particularly useful for proving the existence of patterns or repetitions in a given set of objects.

3. Can you provide an example of a proof that uses the pigeon hole principle?

Sure, one example is the "birthday problem" where the pigeon hole principle is used to show that in a group of 23 people, there is a 50% chance that at least two people share the same birthday. This is because there are only 365 possible birthdays but 23 people in the group, meaning there must be at least one birthday shared by two people.

4. Are there any limitations to the pigeon hole principle?

Yes, the pigeon hole principle assumes that all objects are evenly distributed and there are no other factors at play. This may not always be the case in real-world scenarios, so the principle should be used with caution and in conjunction with other mathematical principles.

5. How can I apply the pigeon hole principle in my own research or projects?

The pigeon hole principle can be applied in various fields such as computer science, statistics, and game theory. It can be useful for analyzing patterns, finding solutions to optimization problems, and making predictions. It is always important to carefully consider the assumptions and limitations of the principle before using it in your own work.

Similar threads

  • Introductory Physics Homework Help
Replies
2
Views
1K
Replies
204
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
2K
Replies
30
Views
511
  • Advanced Physics Homework Help
Replies
2
Views
982
  • Introductory Physics Homework Help
3
Replies
97
Views
11K
Replies
13
Views
1K
  • Introductory Physics Homework Help
Replies
6
Views
2K
Replies
6
Views
695
Back
Top