\documentstyle[11pt,epic,eepic]{article}

\begin{document}

\noindent {\bf Problem 1:}

I recently went to a part with my spouse; there were 11 other
married couples there.  A lot of handshaking happened (but of course
no one shook hands with their spouse).  At the end, it turned out that
for every $k$ from $0$ to $22$, someone other than me had shaken hands
with exactly $k$ people.  How many people did I shake hands with?
Prove it.

\bigskip

\noindent {\bf Problem 2:}

Suppose I have a Manhattan-type $n\times n$ grid of horizontal and
vertical streets.  On each street between two neighboring
intersections, I put a one way sign (note different parts of the
street can point in different directions).  See the figure below.

\begin{figure}[h]
\begin{center}
\setlength{\unitlength}{0.0075in}
\begin{picture}(90,105)(0,-10)
\put(5,85){\ellipse{10}{10}}
\put(45,85){\ellipse{10}{10}}
\put(85,85){\ellipse{10}{10}}
\put(5,45){\ellipse{10}{10}}
\put(45,45){\ellipse{10}{10}}
\put(85,45){\ellipse{10}{10}}
\put(5,5){\ellipse{10}{10}}
\put(45,5){\ellipse{10}{10}}
\put(85,5){\ellipse{10}{10}}
\path(7.000,67.000)(5.000,75.000)(3.000,67.000)
\path(5,75)(5,55)
\path(47.000,67.000)(45.000,75.000)(43.000,67.000)
\path(45,75)(45,55)
\path(85,75)(85,55)
\path(83.000,63.000)(85.000,55.000)(87.000,63.000)
\path(5,35)(5,15)
\path(3.000,23.000)(5.000,15.000)(7.000,23.000)
\path(47.000,27.000)(45.000,35.000)(43.000,27.000)
\path(45,35)(45,15)
\path(87.000,27.000)(85.000,35.000)(83.000,27.000)
\path(85,35)(85,15)
\path(15,85)(35,85)
\path(27.000,83.000)(35.000,85.000)(27.000,87.000)
\path(15,5)(35,5)
\path(27.000,3.000)(35.000,5.000)(27.000,7.000)
\path(55,5)(75,5)
\path(67.000,3.000)(75.000,5.000)(67.000,7.000)
\path(63.000,47.000)(55.000,45.000)(63.000,43.000)
\path(55,45)(75,45)
\path(55,85)(75,85)
\path(67.000,83.000)(75.000,85.000)(67.000,87.000)
\path(23.000,47.000)(15.000,45.000)(23.000,43.000)
\path(15,45)(35,45)
\end{picture}
\end{center}
\end{figure}

We'll say that a {\em sink} is a point (intersection) with all arrows
aiming into it, and a {\em source} is a point with all arrows aiming
out of it.

We noticed that whenever we labeled the streets so that there was no source
or sink, there always seemed to be at least one city block that you
could drive directly around, by making four right turns or four left
turns.  For example, such a cycle is in the upper right corner of the
figure.

Prove that this is indeed true.  ({\em Hint: use well-ordering.})

\end{document}




