Combinatorics: Pigeonhole Principle

In summary: I see now, thank you!In summary, the problem involves coloring the edges connecting points in a complete graph with two colors, red and blue. The goal is to prove that in a 9-set, if the 2-subsets are colored red and blue, there will either be a red 3-set or a blue 4-set. To prove this, the Pigeonhole Principle is used, which states that if there are 10 points and at least 9 colors, then there must be at least 2 points with the same color. Using this principle, it can be shown that in a 9-set, there will either be four red edges or six blue edges. This is because the nine edges connecting a
  • #1
Robben
166
2

Homework Statement



If the 2-subsets of a 9-set are colored red and blue, there is either a red 3-set or a blue 4-set.

Homework Equations



None

The Attempt at a Solution



My book first proved for 10 points, the proof given is:

Consider first for 10 points. Consider the nine edges joining one point x to the others. By the Pigeonhole Principle, either there are four red edges or six blue edges.

Here is where I got confused, why is it that "there are four red edges or six blue edges"? Also, when it says the 2-subsets are colored red and blue does that mean for a 9-set X where X = {1,2,3,4,5,6,7,8,9} then all two subsets that consist of this set X are colored blue and red, e.g. for a 2-subset {1,2} then 1 is colored blue and 2 is colored red?
 
Physics news on Phys.org
  • #2
Robben said:

Homework Statement



If the 2-subsets of a 9-set are colored red and blue, there is either a red 3-set or a blue 4-set.

Homework Equations



None

The Attempt at a Solution



My book first proved for 10 points, the proof given is:

Consider first for 10 points. Consider the nine edges joining one point x to the others. By the Pigeonhole Principle, either there are four red edges or six blue edges.

Here is where I got confused, why is it that "there are four red edges or six blue edges"? Also, when it says the 2-subsets are colored red and blue does that mean for a 9-set X where X = {1,2,3,4,5,6,7,8,9} then all two subsets that consist of this set X are colored blue and red, e.g. for a 2-subset {1,2} then 1 is colored blue and 2 is colored red?

You really have to give a more complete statement of the terms in your problem than that. This isn't a terminology used beyond this particular problem. Help us to help you. I lucked out googling your question and found this http://db.math.ust.hk/notes_download/elementary/combinatorics/de_D4.pdf. It's looks pretty similar to example 1.3. It looks like you are coloring edges connecting points in a complete graph, not points. I.e. if {1,2} is red then the edge connecting points 1 and 2 is red. {1,2,3} is a red 3-set if {1,2}, {2,3} and {1,3} are colored red. As to "there are four red edges or six blue edges" that should be pretty easy. The nine edges connecting a single point to the others can either have 0 reds and 9 blues, or 1 red and 8 blues, or 2 reds and 7 blues etc etc. Convince yourself that each possibility has either 4 reds or 6 blues. Hope that helps you to get started.
 
  • Like
Likes Robben
  • #3
Dick said:
You really have to give a more complete statement of the terms in your problem than that. This isn't a terminology used beyond this particular problem. Help us to help you. I lucked out googling your question and found this http://db.math.ust.hk/notes_download/elementary/combinatorics/de_D4.pdf. It's looks pretty similar to example 1.3. It looks like you are coloring edges connecting points in a complete graph, not points. I.e. if {1,2} is red then the edge connecting points 1 and 2 is red. {1,2,3} is a red 3-set if {1,2}, {2,3} and {1,3} are colored red. As to "there are four red edges or six blue edges" that should be pretty easy. The nine edges connecting a single point to the others can either have 0 reds and 9 blues, or 1 red and 8 blues, or 2 reds and 7 blues etc etc. Convince yourself that each possibility has either 4 reds or 6 blues. Hope that helps you to get started.

Thank you, that linked helped! But I am still confused as to why there are four red edges or six blue edges. If there are four red edges then there are five blue edges. And similarly if there are six blue edges then there are three red edges but why is it that each possibility has either 4 reds or 6 blues?
 
  • #4
Actually I see now why that is. Thank you! But I have one last question. The proof continues by saying suppose there are four red edges, and let X be the set of their four endpoints other than x. If X contains a red edge yz then xyz is a red triangle. But why is that the case? Since X contains the points of their endpoints isn't it always the case that there is a red edge and why would that necessary make xyz a triangle?
 
  • #5
Robben said:
Actually I see now why that is. Thank you! But I have one last question. The proof continues by saying suppose there are four red edges, and let X be the set of their four endpoints other than x. If X contains a red edge yz then xyz is a red triangle. But why is that the case? Since X contains the points of their endpoints isn't it always the case that there is a red edge and why would that necessary make xyz a triangle?

If the four endpoints are u,v,y,z, then all of the edges connecting them to x are red since they are the endpoints of red edges with x. Then if one of them, say yz is also red then xyz is a red triangle, right? It's not necessarily true that one is red. They might all be blue. Then what? Think about this a little more.
 
  • Like
Likes Robben
  • #6
Robben said:
Actually I see now why that is. Thank you! But I have one last question. The proof continues by saying suppose there are four red edges, and let X be the set of their four endpoints other than x. If X contains a red edge yz then xyz is a red triangle. But why is that the case? Since X contains the points of their endpoints isn't it always the case that there is a red edge and why would that necessary make xyz a triangle?
Let the members of X be y, z, w, t. xy, xz, xw, xt are all red edges. If yz is a red edge then xyz is a red triangle.
 
  • Like
Likes Robben
  • #7
What shape should I draw in order to visualize this? I drew a decagon with an edge missing. Is that the right shape?
 
  • #8
Robben said:
What shape should I draw in order to visualize this? I drew a decagon with an edge missing. Is that the right shape?
The graph showing x and X is K5. You can't draw it in the plane without a crossing.
You could draw X as a square, the members of X being the corners. Put x in the middle and join to the corners. The diagonals are all red, by definition of X.
Let y and z be the two top corners. If yz is red then xyz is a red triangle.
 
  • Like
Likes Robben
  • #9
Thank you very much!
 

1. What is the Pigeonhole Principle in combinatorics?

The Pigeonhole Principle is a fundamental concept in combinatorics that states that if there are n pigeons and m pigeonholes, with n > m, then at least one pigeonhole must contain more than one pigeon. In other words, if there are more items than there are categories to put them in, then at least one category must contain more than one item.

2. How is the Pigeonhole Principle applied in combinatorics problems?

The Pigeonhole Principle is often used to prove the existence of certain combinations or patterns in combinatorics problems. By setting up the problem in terms of pigeons and pigeonholes, the principle can be used to show that there must be at least one instance of the desired combination or pattern.

3. Can the Pigeonhole Principle be used to solve all combinatorics problems?

No, the Pigeonhole Principle is not a complete solution for all combinatorics problems. While it can be a useful tool in certain situations, there are many other techniques and strategies that may be needed to fully solve a problem.

4. Are there any variations of the Pigeonhole Principle?

Yes, there are several variations of the Pigeonhole Principle, including the generalized Pigeonhole Principle and the Strong Pigeonhole Principle. These variations have different conditions and may be applicable in different types of combinatorics problems.

5. Can the Pigeonhole Principle be extended to more than two categories?

Yes, the Pigeonhole Principle can be extended to any number of categories. If there are n categories and m items, with n > m, then at least one category must contain more than m/n items. This variation is known as the Generalized Pigeonhole Principle.

Similar threads

  • Special and General Relativity
5
Replies
146
Views
5K
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
  • Calculus and Beyond Homework Help
Replies
7
Views
1K
  • Calculus and Beyond Homework Help
Replies
15
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
575
  • Calculus and Beyond Homework Help
Replies
6
Views
805
  • Calculus and Beyond Homework Help
Replies
1
Views
439
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Precalculus Mathematics Homework Help
Replies
5
Views
978
Back
Top