Solving the Pigeonhole Principle Homework Problem

  • Thread starter Kreizhn
  • Start date
  • Tags
    Principle
In summary, the question asks to show that there exists 2 disjoint subsets of a set of 10 objects, each painted one of 3 possible colors, where each subset consists of 3 objects all painted the same color. The pigeonhole principle can be used to demonstrate this, as shown in the example of {r1 r2 r3 g4 g5 g6 g7 g8 g9 g10} where the subsets {r1 r2 r3} and {g4, ..., g10} satisfy the requirement. However, it is not guaranteed that in any decomposition of the set there will be two disjoint subsets containing at least three objects of the same color.
  • #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?
 
Physics news on Phys.org
  • #2
Nevermind, I figured it out. For some reason I thought the colours had to be distinct also.
 

1. What is the Pigeonhole Principle?

The Pigeonhole Principle is a mathematical concept that states that if there are more pigeons than pigeonholes, then at least one pigeonhole must have more than one pigeon. It is often used to prove the existence of a solution to a problem or to show that a certain outcome is inevitable.

2. How is the Pigeonhole Principle applied in solving homework problems?

The Pigeonhole Principle can be applied to homework problems by using it to prove the existence of a solution or to eliminate potential solutions that do not fit the criteria. It can also be used to show that a certain outcome is inevitable, even if it may not seem intuitive at first glance.

3. What are some common examples of using the Pigeonhole Principle to solve homework problems?

One common example is proving that in a group of 13 people, at least 2 people must have the same birthday. Another example is showing that in a deck of 52 cards, there must be at least 2 cards with the same suit.

4. Are there any limitations to the Pigeonhole Principle?

Yes, the Pigeonhole Principle can only be applied to problems that involve finite sets. It also cannot be used to find the exact number of solutions, only to prove that at least one solution exists.

5. How can the Pigeonhole Principle be used to improve problem-solving skills?

By understanding and applying the Pigeonhole Principle, it can help develop critical thinking skills and improve problem-solving abilities. It can also be used to approach problems in a systematic and logical manner, which can be applied to various fields and real-life situations.

Similar threads

MHB Betting Strategy: Win Profits 90% of the Time
    • General Math
Replies
4
Views
728
MHB Gambling Strategy Help: Win 90% of 4 Round Games
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
924
Matlab code running loops to meet conditions
    • Engineering and Comp Sci Homework Help
Replies
8
Views
1K
Solve Resistor Cube Problem: Find Voltage Across Current Source
    • Engineering and Comp Sci Homework Help
Replies
8
Views
4K
Solving Problem with Pigeonhole Principle: Sum of 10?
    • Calculus and Beyond Homework Help
Replies
12
Views
12K
Mathematica Mathematica not supporting graphs code is as
    • MATLAB, Maple, Mathematica, LaTeX
Replies
15
Views
4K

Hot Threads

Recent Insights

Back
Top