
\problemdata     
{S01-PS6-2}           
{Pigeonhole principle}              
{S99-PS7, S01-PS6} 		
{S01 Karger}


\begin{problem}

 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 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.  No proofs are required.

\begin{problemparts}
\problempart At least 2 people were born on the same day of the year.

\solution{This property holds for every group of 366 or more people.}

\problempart At least 2 people were born on January 1.

\solution{This property need not hold, even for arbitrarily large
groups of people.}

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

\solution{
This property holds for every group of 15 or more people.
}

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

\solution{
This property holds for every group of 37 or more people.
}

\problempart At least 2 people were born exactly one week apart.

\solution{This property need not hold.  For example, everyone might be
born on the same day of the year.
}

\problempart At least 9 people were born on a weekend or at least 11
people were born during the week.

\solution{This property holds for every group of at least $(9-1) +
(11-1) + 1 = 19$ or more people.}

\problempart At least 2 people were born on the same day of the year or else
2 people were born exactly one week apart.

\solution{There are two interpretations of this question, which differ
on whether, say, people born on Dec 31 and Jan 6 were born a week
apart.  If such ``wraparound'' is considered, then the answer is 183
people.  If ``wraparound'' is ignored, then the answer is 184 people.
}

\end{problemparts}

\end{problem}