\problemdata      
        {?} % latex-friendly label for the prob.
        {Pigeonhole} % The topic(s) of the problem content.
        {Rosen \S 4.2, Exs 10, 40} % Source (if known)
        {Fall 2001, PS8} % Usage (list ones you are aware of).
        {Christos Kapoutsis, S02} % Last revision info (author, date).

\begin{problem}
\bparts
\ppart Rosen \S 4.2, Exercise 10.

\solution{The midpoint of the segment whose endpoints are $(a,b)$ and
$(c,d)$ is $\left(\cfrac{a+c}{2},\cfrac{b+d}{2}\right)$.  Clearly the
coordinates of these fractions will be integers as well if and only if
$a$ and $c$ share parity (both odd or even) and $b$ and $d$ also share
parity.  Thus, there are four possible pairs of parities: (odd,odd),
(odd,even), (even,odd), (even,even).  Since we are given five points,
the pigeonhole principle guarantees that at least two of them will
have the same pair of parities; therefore, the midpoint of the line
segment joining those two points will have integral coordinates.}

\ppart Rosen \S 4.2, Exercise 30.

\solution{At a party with $n$ people, there are $n$ possibilities
for the number of ``other people'' a person can know ($0$ through
$n-1$), so we cannot apply the pigeonhole principle directly; however,
note that there cannot exist a party in which some person (say, Lars)
knows no one and another (say, Kirk) knows all $n-1$ other people,
because ``know'' is a symmetric relation: if Kirk knows Lars, then
Lars knows Kirk, contradicting the assumption that Lars knows no one.
Thus, there are in reality only $n-1$ possiblities, whereupon we can
apply the pigeonhole principle.}

\eparts
\end{problem}
