Combinatorics: Pigeonhole Principle

[Robben]

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?

 

[Dick]

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.

 

[Robben]

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?

 

[Robben]

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?

 

[Dick]

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.

 

[haruspex]

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.

 

[Robben]

What shape should I draw in order to visualize this? I drew a decagon with an edge missing. Is that the right shape?

 

[haruspex]

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 K₅. 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.

 

[Robben]

Thank you very much!