Pigeonhole Principle

  • Thread starter Kreizhn
  • Start date
  • #1
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?
 

Answers and Replies

  • #2
743
1
Nevermind, I figured it out. For some reason I thought the colours had to be distinct also.
 

Related Threads on Pigeonhole Principle

  • Last Post
Replies
12
Views
11K
  • Last Post
Replies
8
Views
3K
  • Last Post
Replies
0
Views
2K
  • Last Post
Replies
13
Views
10K
  • Last Post
Replies
8
Views
826
  • Last Post
Replies
17
Views
8K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
3
Views
2K
Replies
2
Views
3K
  • Last Post
Replies
0
Views
432
Top