1. Limited time only! Sign up for a free 30min personal 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!

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