Subjects discrete mathematics

Pigeonhole Principle 5223E3

Step-by-step solutions with LaTeX - clean, fast, and student-friendly.

Search Solutions

Pigeonhole Principle 5223E3


1. **Problem:** Apply the Pigeonhole Principle to show that in any group of 13 people at least two were born in the same month. 2. **Pigeonhole Principle Statement:** If $n$ items are put into $m$ containers, with $n > m$, then at least one container must contain more than one item. 3. **Explanation:** Here, the "items" are the 13 people, and the "containers" are the 12 months. 4. Since there are 13 people and only 12 months, by the Pigeonhole Principle, at least one month must have at least two people born in it. 5. **Conclusion:** Therefore, in any group of 13 people, at least two share the same birth month.