Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Pigeonhole Principle

  1. Aug 6, 2010 #1
    1. The problem statement, all variables and given/known data
    The following is the question verbatim:

    Imagine a set of 10 objects, each of which is painted one of 3 possible colors. Show that there exists 2 disjoint subsets of this set such that each subset consists of 3 objects all painted the same color.

    3. The attempt at a solution

    This is a problem that is supposed to demonstrate the pigeonhole principle. I know how to use said pigeonhole principle, so maybe it's just the wording that is confusing me.

    Trivially, if I am allowed to choose among all possible sets of ten objects consisting of 3 colors (say r,g,b) then of course I can construct two disjoint sets each of which contain at least three objects of the same color. If the set is {r1 r2 r3 g4 g5 g6 g7 g8 g9 g10} then obviously {r1 r2 r3}, {g4, ..., g10} works. Of course there are many others.

    On the same hand we're not guaranteed that in any decomposition of the set there are two disjoint sets containing at least three. For example {r1 r2 g3 g4 b5 b6 b7 b8 b9 b10} could be decomposed as say {r1 r2 g3 g4} {b5, ... b10}.

    Maybe I'm misunderstanding the question? Could someone clear this up for me?
     
  2. jcsd
  3. Aug 6, 2010 #2
    Nevermind, I figured it out. For some reason I thought the colours had to be distinct also.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook