3.5 Pigeonhole Principle, Inclusion-Exclusion

Below is a list of properties that a group of people might possess.

For each property, either give the minimum number of people that must be in a group to ensure that the property holds, or else write nh to indicate that the property need not hold even for arbitrarily large groups of people.

Assume that every year has exactly 365 days; ignore leap years.

1. At least 2 people were born on the same day of the year (ignore the year of birth).

   Exercise 1

    Numerical Response 

   We let the people be pigeons and the days of the year be holes (365 holes). If we have 365+1 pigeons, two of them must be in the same hole (i.e. the two must be born on the same day).



2. At least 2 people were born on January 1st.

   Exercise 2

    Text Response  Answer:nh
   No matter how many people you have, you cannot force any one of them to be born on a specific day. For example, everyone might be born on January 2nd.



3. At least 3 people were born on the same day of the week.

   Exercise 3

    Numerical Response 

   We let people be pigeons and the days on the week be holes (7 holes). Using the generalized pigeonhole principle, we need 2\(\cdot\)7+1 people to force 3 of them to be in the same hole (i.e. born on the same day of the week).



4. At least 4 people were born in the same month.

   Exercise 4

    Numerical Response 

   We let the people be pigeons and the months of the year be holes (12 holes). Using the generalized pigeonhole principle, we need 3\(\cdot\)12+1 people to force 4 of them to be born in the same month.



5. At least 2 people were born exactly one week apart.

   Exercise 5

    Text Response  Answer:nh
   Again, you cannot force this property. For example, everyone might be born on the same day of the year.
   CheckShow Answer