Pigeon hole birthday problem?

Question

If there are 10,000 people, how many people must have the same birthday (ignoring year)?

This is the way I went about this problem:

10000 people / 365 days in a year = 27.397 people per day

$\Rightarrow$ there must be at least 27 people who have the same birthday.

Is this correct?

Answer 1

You are almost correct. You could conclude that there are at-least $28$ people with the same birthday.

In general, if there are $n$ people, then you can conclude that there must be atleast $$\left \lceil \dfrac{n}{365} \right \rceil$$ who have the same birthday. Note that it is $\left \lceil \dfrac{n}{365} \right \rceil$ and not $\left \lfloor \dfrac{n}{365} \right \rfloor$.

To see why it should be $\lceil \rceil$ and not $\lfloor \rfloor$, take $n=366$, then you can conclude that there are at-least two people sharing a birthday.

Answer 2

Your calculation proves that there is a group of least $28$ people with the same birthday.

We really should show also that it is possible that the maximum is $28$. For with different numbers it is possible that for number-theoretic reasons, the number computed using $\left\lceil\frac{n}{k}\right\rceil$ is not the actual minimum.

Make $200$ groups of $28$ that share a birthday, for a total of $5600$ people. That leaves $165$ potential birthdays, and $4400$ people. We can divide them into $162$ groups of $27$, and $1$ group of $26$. There are many other ways to have a maximum of $28$.

Answer 3

I’m going to include $29$ February as a possibility. If each of the $366$ possible birthdays is represented only $27$ times or fewer, we could have at most $27\cdot366=9882$ people. We actually have $10,000$ people, more than $9882$, so some birthday must be represented more than $27$ times. Thus, there must be at least one birthday shared by at least $28$ people.

Can we do better? No, because $28\cdot366=10,248$; we could, for instance, have $118$ birthdays each shared by $28$ people and $248$ each shared by $27$ people, since $118\cdot28+248\cdot27=10,000$. Thus, we can’t guarantee that there is a birthday shared by $29$ people.

This reasoning, when carried out in general, leads to the conclusion that if you divide $n$ things into $k$ categories, at least one category must contain at least $\left\lceil\frac{n}k\right\rceil$, where $\left\lceil\frac{n}k\right\rceil$ is the smallest integer greater than or equal to $\frac{n}k$.