%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 2000 Quiz 2
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem \pts{21} \textbf {A Strange Set}
% difficulty: medium-hard

Define the function $fp(x) = x - \floor{x}$.  ($fp$ stands for
``fractional part.'')  Recall that $\floor{x}$ is the greatest integer
less than or equal to $x$.  So, $\floor{8.2} = 8$ and $\floor{-2.3} =
-3$.   Let $h = \sqrt{37}$

Let $S = \{ n \in \mathbb{Z} \ | \ n \neq 0 \wedge  fp(nh) < 0.01 \}$. 


Use the pigeonhole principle to prove that $S$ is nonempty.  Other methods
will not get credit.


\solution{\bigskip
{\bf Solution:}

We let $fp(nh)$ be our pigeon (for each $n$ there is one pigeon), and let
the pigeonholes be ranges of size $.01$.  So the first pigeonhole would be
those $n$ for which the first two digits of $fp(nh)$ after the decimal
point are 0 and 0, the secound would have digits 0 and 1, and so on.  
Since there are infinitely many pigeons and only 100 pigeonholes, by the
pigeonhole principle, there must be a pigeonhole with more than one pigeon
in it.

Let $m$ and $n$ be two different numbers such that $fp(nh)$
and $fp(mh)$ end up in the same hole.  Suppose, without loss
of generality, that $fp(nh) \geq fp(mh)$.  Then,
$fp(nh) - fp(mh) < .01$.

Suppose $l$ and $m$ are the digits associated with the pigeonhole both
$n$ and $m$ fall into.  Then, we can write $k = 10l + m$ and write

$nh = \frac{k}{100} + \alpha + \floor{nh}$ and

$mh = \frac{k}{100} + \beta + \floor{mh}$ where $0 \leq \beta \leq \alpha 
< .01$

Now, we can subtract these two equations and get

$$nh-mh = \alpha - \beta + \floor{nh}-\floor{mh}.$$

Since $\alpha \geq \beta$ we know $\alpha - \beta \geq 0$.  Since $\alpha 
< .01$ we know $\alpha < 1$, so $\alpha - \beta < 1$.  Thus, 

$$nh-mh = \alpha - \beta + \floor{nh-mh}.$$

by the definition of the floor function.  Thus, $\alpha - \beta = 
fp(nh-mh) = fp ((n-m)h)$.  Since $n-m$ is an integer and is not equal to 0 
(since $m$ and $n$ were different numbers), and since $0 \leq fp((n-m)h) 
< .01$ we know $n-m$ must be an element of $S$.  Thus, $S$ is nonempty.
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 1998 Midterm
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\problem {\bf (6 points)}  The Pigeonhole Principle can be used to prove
each of the following statements.  In each case, say what the pigeons
are, what the holes are, and what the function is that maps pigeons to
holes.

{\bf Example.} If I pick five cards from a deck, then I will have at
least two cards from some suit.

Pigeons: The five cards.

Holes: The four suits.

Function: A card is mapped to its suit.

\bigskip

\begin{problemparts}

\problempart {\bf (2 points)}  If everyone in an $n$-player tournament wins
at least one match, then there must be two players with the same
number of wins.

\bigskip

Pigeons:  \solution{The $n$ players in the tournament.}

Holes: \solution{The numbers $1, 2, \ldots, n-1$}

Function:

\solution{A player is mapped to the number of matches that he or she
won.}

\problempart {\bf (2 points)}  This afternoon, 19 pigeons flew through 32
holes in a fence in such a way that at least one pigeon flew through
each of the holes.  Therefore, some pigeon flew through at least two
holes.

\bigskip

Pigeons:  \solution{32 holes}

Holes:  \solution{19 pigeons}

Function:

\solution{A hole is mapped to the first pigeon that flew through it.}

\problempart {\bf (2 points)}  In any collection of six different, non-empty
subsets of $\{a,b,c,d,e\}$, there exist two sets that intersect.

\bigskip

Pigeons: \solution{The six different, non-empty subsets.}

Holes: \solution{The elements $a$, $b$, $c$, $d$, and $e$.}

Function:

\solution{A subset is mapped to the first element in the
list $a$, $b$, $c$, $d$, $e$ that it contains.}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 1998 Final exam
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem {\bf (10 points)} Suppose that five points are placed inside
a square with sides of length 1.  Prove that the distance between some
pair of points is at most $\sqrt{2}/2$.

\solution{Divide the square into four subsquares with edge-length
$\frac{1}{2}$.  By the pigeonhole principle, some two of the five
points must be placed inside the same subsquare.  The distance between
these two points can be at most $\sqrt{2}/2$.}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 2000 Final exam
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 9
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{6} \textbf {MIT Football}

MIT's football coach goes to K-mart to buy 32 football jerseys.  While
he is away, instead of practicing, the team proves theorems about the
numbers on the jerseys.

For each of the theorems, fill in whichever blanks are asked for.  You
do not have to complete the proof.  For example, 

{\bf Theorem 1}\\
If the numbers on the jerseys are integers in the set $\{1, \ldots, 31\}$ then
two of the jerseys have the same number.

Pigeons: \underline{Jerseys}

Pigeonholes:  \underline{Integers in the set $\{1, \ldots, 31\}$}

Pigeon $p$ is in hole $h$ if:  \underline{Jersey $p$ has number $h$ on it.}

\problempart {\bf (2 points).  Theorem 2}\\ If the numbers on the
jerseys are integers in the set $\{1, \ldots, 100\}$ then the
difference between the numbers on some pair of jerseys is a multiple
of 31.

Pigeons: Jerseys

Pigeonholes:  \underline{\hspace{3in}}

Pigeon $p$ is in hole $h$ if:  \underline{\hspace{3in}}

\solution{\bigskip {\bf Solution:}

Pigeonholes:  Integers in the set $\{0, \ldots, 30\}$.

Pigeon $p$ is in hole $h$ if: The number on jersey $p$ is equal to $h$
modulo 31.
}


\problempart {\bf (4 points).  Theorem 3}\\ If the numbers on the
jerseys are integers in the set $\{1, \ldots, 100\}$ then if the
jerseys are lined up in ascending order by their numbers, there is a
nonempty consecutive subset of the jerseys whose numbers add up to a
multiple of 32.

Pigeons: \underline{\hspace{3in}}

Pigeonholes:  \underline{\hspace{3in}}

Pigeon $p$ is in hole $h$ if:  \underline{\hspace{3in}}

\solution{\bigskip {\bf Solution:}

Pigeons:  Sums of the first $i$ jerseys, from $i = 1$ to $32$

Pigeonholes:  Integers in the set $\{0, \ldots, 31\}$

Pigeon $p$ is in hole $h$ if:  $p \equiv h$ mod $32$.}
