- #1
Kreizhn
- 743
- 1
Homework Statement
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.
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?