(adsbygoogle = window.adsbygoogle || []).push({}); 1. The problem statement, all variables and given/known data

The following is the questionverbatim:

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?

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Pigeonhole Principle

**Physics Forums | Science Articles, Homework Help, Discussion**