1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatorics: Pigeonhole Principle

  1. Apr 21, 2015 #1
    1. The problem statement, all variables and given/known data

    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.

    2. Relevant equations

    None

    3. 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?
     
  2. jcsd
  3. Apr 21, 2015 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  4. Apr 22, 2015 #3
    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?
     
  5. Apr 22, 2015 #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?
     
  6. Apr 22, 2015 #5

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  7. Apr 22, 2015 #6

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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.
     
  8. Apr 22, 2015 #7
    What shape should I draw in order to visualize this? I drew a decagon with an edge missing. Is that the right shape?
     
  9. Apr 22, 2015 #8

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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.
     
  10. Apr 22, 2015 #9
    Thank you very much!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Combinatorics: Pigeonhole Principle
  1. Pigeonhole principle (Replies: 12)

  2. Pigeonhole Principle (Replies: 1)

Loading...