(A) How many people must be in a group to guarantee that at least two people in
ID: 1719785 • Letter: #
Question
(A) How many people must be in a group to guarantee that at least two people in the group have the same birthday? Identify your pigeons and holes.
(B) How many people must be in a group to guarantee that at least n people in the group have the same birthday? Identify your pigeons and holes.
You may use the Generalized Pigeonhole Principle (Let A be the set of your pigeons, and let B be the set of pigeonholes in which they live. The Generalized Pigeonhole Principle states that for a natural number k, if |A| > k|B|, then there exists a pigeonhole in which more than k pigeons live)
Explanation / Answer
Solution :
(A) There must be 367 people. There are 366 possible birthdays (including leap years), and so to apply the pigeonhole principle we need more than 366 people.
(B) There must be n+1 people. There are n possible birthdays (including leap years), and so to apply the pigeonhole principle we need more than n people.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.