\documentstyle[12pt,twoside]{article}

\newcommand{\problem}{%
  \paragraph{Problem}}
\newcommand(\solution}{%
  \paragraph{Solution}}

\begin{document}


\begin{problems}

%BEGIN Kavita's problems
% Fall 1998


%**************
%   PSET 7    *
%**************

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Wantonly stolen from Brualdi.

\problem {\bf (15 points)} Prove that among every set of $52$
integers, there exists a pair with sum or difference divisible by 100.

\solution{ We assign each of the 52 numbers to one of 51 bins, which
are defined as follows.

First, we define 49 ``ordinary'' bins.  Let bin 1 contain numbers
congruent to 1 or 99 modulo 100.  Let bin 2 contain numbers congruent
to 2 to 98 modulo 100.  Continuing in this vein, let bin 49 contain
numbers congruent to 49 or 51 modulo 100.  Now we define two
``special'' bins.  Let bin 0 contain numbers congruent to 0 modulo
100, and let bin 50 contain numbers congruent to 50 modulo 100.

By the Pigeonhole Principle, at least two numbers are assigned to the
same bin.  If two numbers are assigned to an ordinary bin and are
congruent modulo 100, then their difference is divisible by 100.  If
two numbers are assigned to an ordinary bin and are not congruent
modulo 100, then their sum is divisible by 100.  If two numbers are
assigned to a special bin, then both their sum and their difference is
divisible by 100.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%  These are mostly stolen from Brualdi.

\problem {\bf (25 points)} Theory Pig has often complained that the
name ``Pigeonhole Principle'' is verbose and awkward.  He proposes the
more concise term ``Pig Principle'' for the same idea.  Recently, he
devised a couple problems involving this idea in order to promote his
terminology.

\begin{problemparts}
\problempart Suppose that $m$ pigs are lined up, and each pig is given
one or more tasty treats.  Prove that there is always a set of pigs
that are consecutive in the lineup and that all together receive a
number of treats that is a multiple of $m$.

For example, suppose that there are $m = 5$ pigs, and that they
receive 1, 6, 2, 7, and 9 treats respectively.  Then the claim holds
in this case, because the second, third, and fourth pigs received $6 +
2 + 7 = 15$ treats altogether, and 15 is a multiple of 5.

\solution{ Let $P_i$ be the total number of treats given out to the
first $i$ pigs.  There are two cases.  In the first case, suppose that
at least one of $P_1, P_2, \ldots, P_m$ is congruent to 0 modulo $m$.
In particular, suppose that $P_j$ is congruent to 0 modulo $m$.  This
implies that the number of treats received by the first $j$ pigs is a
multiple of $m$, and so the claim holds.  In the second case, suppose
that none of $P_1, P_2, \ldots, P_m$ is congruent to 0 modulo $m$.
Then each of the $m$ terms $P_1, P_2, \ldots, P_m$ is congruent to one
of the $m-1$ values $1, 2, \ldots, m-1$ modulo $m$.  By the Pig
Principle, there are at least two terms $P_j$ and $P_k$ that are
congruent to the same value modulo $m$.  Thus pigs $j+1, j+2, \ldots,
k$ received a total of $P_k - P_j$ treats, which is a multiple of $m$.
}

\problempart Suppose that during each day of an 13-week term, a
certain theoretically-inclined pig receives at least one affectionate
pat.  However, suppose that this pig never receives more than 12 pats
in any one of the 13 weeks, on account of his being underappreciated
by the TA staff.  Prove that there exists a sequence of consecutive
days during which the pig receives exactly 25 affectionate pats.

\solution{ Let $P_i$ be the total number of pats that the pig receives
in the first $i$ days.  Since he gets least one pat every day, the
sequence $P_1, P_2, \ldots, P_{91}$ is strictly increasing.  Since he
gets at most 12 pats per week, the final term, $P_{91}$, is at most $13
\cdot 12 = 156$.  Now the sequence $P_1 + 25, P_2 + 25, \ldots, P_{91}
+ 25$ is also strictly increasing, and the largest term, $P_{91} + 25$,
is at most $156 + 25 = 181$.  Therefore, the 182 values $P_1, \ldots,
P_{91}$ and $P_1 + 25, \ldots, P_{91} + 25$ all lie between 1 and 181.
By the Pig Principle, at least two of these values must be the same.
Since no two of the numbers $P_1, \ldots, P_{91}$ are equal, and no
two of the numbers $P_1 + 25, \ldots, P_{91} + 25$ are equal, there
must be an $i$ and a $j$ such that $P_i = P_j + 25$.  This implies
that on days $j+1, j+2, \ldots i$, the pig receives exactly 25
affectionate pats.

\bigskip

Fat chance.
}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%END   Kavita's problems

%BEGIN Joe's problems
\problem %source: spring00 ps6
\textbf{Pigeonhole Principle}

\begin{problemparts}

\vspace{-\baselineskip}
\problempart
% problem 5, problem set 7, fall 1998

%[[[This one comes from Fall 98, pset 7, problem 5.  It might be nice
%to change the numbers.  Solutions are given there too.]]]

%Prove that among every set of $52$ integers, there exists a pair with
%sum or difference divisible by 100.

Prove that among every set of $18$ integers, there exists a pair with
sum or difference divisible by $32$.

\solution{%
  The solution must be adjusted from $52$ and $100$ to $18$ and $32$,
  respectively.

  We assign each of the 52 numbers to one of 51 bins, which are
  defined as follows.

  First, we define 49 ``ordinary'' bins.  Let bin 1 contain numbers
  congruent to 1 or 99 modulo 100.  Let bin 2 contain numbers
  congruent to 2 to 98 modulo 100.  Continuing in this vein, let bin
  49 contain numbers congruent to 49 or 51 modulo 100.  Now we define
  two ``special'' bins.  Let bin 0 contain numbers congruent to 0
  modulo 100, and let bin 50 contain numbers congruent to 50 modulo
  100.

  By the Pigeonhole Principle, at least two numbers are assigned to
  the same bin.  If two numbers are assigned to an ordinary bin and
  are congruent modulo 100, then their difference is divisible by 100.
  If two numbers are assigned to an ordinary bin and are not congruent
  modulo 100, then their sum is divisible by 100.  If two numbers are
  assigned to a special bin, then both their sum and their difference
  is divisible by 100.  
  }

\vspace{-\baselineskip}
\problempart
% problem 6a, problem set 7, fall 1998

One of the 6.042 TAs has decided to conduct his next tutorial in the
following manner: he will arrange his $m$ students in alphabetical
order and hand out tutorial problems to each of the students such that
each student ends up with one or more problems.  The TA claims that
using such an arrangement, there is always a group of (one or more)
students that are consecutive in the alphabetical order and
collectively receive a number of problems that is a multiple of $m$.

As an example, consider a 6.042 tutorial with $m = 10$ students in
which the students are arranged in alphabetical order and each of
which receives $1, 2, 4, 8, 16, 16, 8, 4, 2, 1$ problems.  Then, since
the fourth, fifth, and sixth students have collectively received $40$
problems, the TA's claim holds.

Prove this claim for all $m$.

%The same pset, problem 6a.
%It's a very cute problem.
%But change not only the numbers but also the story.
%Or just make it about a sequence of $m$ consecutive positive natural
%numbers.

%Maybe say there are 120 students in the class.
%Arrange them in alphabetical order.
%Everyone owns one or more books. 
%Claim that there is some group of (one or more) students that are
%consecutive in alphabetical order, and whose total number of books is
%a multiple of 120.

\solution{%
  Let $P_i$ be the total number of problems given out to the first $i$
  students.  There are two cases.  In the first case, suppose that at
  least one of $P_1, P_2, \ldots, P_m$ is congruent to 0 modulo $m$.
  In particular, suppose that $P_j$ is congruent to 0 modulo $m$.
  This implies that the number of problems received by the first $j$
  pigs is a multiple of $m$, and so the claim holds.  In the second
  case, suppose that none of $P_1, P_2, \ldots, P_m$ is congruent to 0
  modulo $m$.  Then each of the $m$ terms $P_1, P_2, \ldots, P_m$ is
  congruent to one of the $m-1$ values $1, 2, \ldots, m-1$ modulo $m$.
  By the Pigeonhole Principle, there are at least two terms $P_j$ and
  $P_k$ that are congruent to the same value modulo $m$.  Thus
  students $j+1, j+2, \ldots, k$ received a total of $P_k - P_j$
  problems, which is a multiple of $m$.%
  }
\end{problemparts}

\problem %source: spring00 ps7
Jelly beans of 8 different colors are in 6 jars.  There are 20
  jelly beans of each color.  Use the pigeonhole principle to prove
  that there is some jar that contains at least two beans each from two
  different colors of jelly beans.
  
  \omitsolution{There are 20 beans of each color. Since there are 6 jars, by
    the strong pigeonhole principle for each color there is a jar
    containing at least $20/6\geq 2$ beans of that color.  Since the
    number of colors is greater then the number of jars, using the
    pigeonhole principle again, there must be a jar containing two pairs
    of jelly beans from two different colors of jelly beans.}

%END   Joe's problems

%BEGIN Ray's problems


%%%%%%%%%%%%%  S99 ps3

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (15 points)} Many two-person games in which players
alternate moves--- like chess, checkers, and tic-tac-toe--- can be
represented abstractly by "game trees".

The root of a game tree has children labeled with each of the possible
initial moves by the first player.  For example, in the game tree for
tic-tac-toe, the root has nine children corresponding to the nine
boxes that the first player could mark with an "X".  Each of these
nodes has eight children corresponding to the eight remaining boxes
which the second player could mark with an "O", and so on.

In general, each node corresponds to a situation in the game, and its
children correspond to each of the possible moves by the player whose
turn it is in that situation.  The leaves of the tree correspond to
situations where no moves are possible --- the game is over.  The
leaves are labelled with \emph{win}, \emph{lose}, or \emph{draw},
indicating the outcome for the first player.  (A win for one player is
a loss for the other--- no "everybody wins"-type games at MIT. {\tt
:-)})

A \emph{strategy} for a player in a game specifies which move the
player should make in any situation where it is that player's turn to
move.  A \emph{winning} stategy ensures that the player will win no
matter what moves the other player makes.  Similarly, a
\emph{non-losing} stategy ensures that the player will \emph{win or
draw} no matter what moves the other player makes.

For example, most elementary school children figure out non-losing
strategies in tic-tac-toe for \emph{both} the first and second players.
There is no winning strategy in tic-tac-toe for either player.  No one
knows if any player has a winning strategy for chess or checkers.
However, on general principles, we can be sure that at least one player
has a non-losing strategy.

\begin{problemparts}

\problempart Prove that for any two-person game with a finite game
tree, at least one of the players has a non-losing strategy.

\solution{The proof is by strong induction on the depth of the game
tree.  Let $P(n)$ be the proposition that for a game tree of depth
$n$, at least one of the players has a non-losing strategy.

In the base case, a tree of depth 0 is a node labeled {\em win}, {\em
lose}, or {\em draw}.  If the node is labeled {\em win} or {\em draw},
then the first player has a non-losing strategy.  If the node is
labeled {\em draw} or {\em lose}, then the second player has a
non-losing strategy.  In all three cases, the proposition $P(0)$
holds.

In the inductive step, for $n \geq 0$ assume $P(1), P(2), \ldots,
P(n)$ to prove $P(n+1)$.  A game tree of depth $n+1$ consists of a
root joined to subtrees of depth at most $n$.  Let $A$ be the player
making a move in the situation corresponding to the root node, and let
$B$ be the other player.

If player $B$ has a non-losing strategy for every subtree, then player
$B$ has a non-losing strategy for the full game tree; no matter what
move player $A$ makes, player $B$ is left with a game tree for which
he has a non-losing strategy.

On the other hand, if player $B$ lacks a non-losing strategy for some
subtree, then by strong induction player $A$ has a non-losing strategy
for the same subtree.  Furthermore, player $A$ has a non-losing
strategy for the full game tree; namely, pick the subtree for which he
has a non-losing strategy on his first move, and then pursue that
non-losing strategy for the subtree.

In either case, at least one of the players has a non-losing strategy.
This shows that $P(0), P(1), \ldots, P(n)$ imply $P(n+1)$ and
completes the proof by strong induction.}

\problempart Show that either exactly one player has a winning
strategy, or both players have non-losing strategies.

\solution{}

\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (10 points)} A pair 6.042 students, Wendy and Steve,
have decided to devote some of their spare time this term to
establishing dominion over the entire galaxy.  Recognizing this as an
ambitious project, they worked out the following table of tasks on the
back of Steve's copy of the notes for recitation 2.

\begin{enumerate}
\item {\bf Devise a logo} and cool imperial theme music - 8 days.
\item {\bf Build a fleet} of Hyperwarp Stardestroyers out of eating
paraphenalia swiped from Lobdell - 18 days.
\item {\bf Seize control} of the United Nations - 9 days, after task \#1.
\item {\bf Get shots} for Wendy's cat, Muffy - 7 days, after task \#1.
\item {\bf Train an army} of elite interstellar warriors by dragging
people to see {\em The Phantom Menace} dozens of times - 4 days, after
tasks \#3 and \#4.
\item {\bf Launch the fleet} of Stardestroyers, crush all sentient
alien species, and establish a Galactic Empire - 6 days, after tasks \#2 and
\#5.
\item {\bf Defeat Microsoft} - 8 days, after tasks \#2 and \#5.
\end{enumerate}

Wendy and Steve want to complete all these tasks in the shortest
possible time.  However, they have agreed on some constraining work
rules.

\begin{itemize}

\item Only one person can be assigned to a particular task; they can
not work together on a single task.

\item Once a person is assigned to a task, that person must work
exclusively on the assignment until it is completed.  So, for example,
Wendy cannot work on building a fleet for a few days, run get shots
for Muffy, and then return to building the fleet.

\end{itemize}

For each task, the table above lists the time required for completion
and which other tasks must be finished before the given task is begun.

\begin{problemparts}
\problempart Express the information in the task list using some type
of graph.

\solution{ The information in the table is represented below in the
form of a directed acyclic graph.  Each vertex represents a task,
and the weight of a vertex is the completion time.  Each directed edge
represents a dependendency between tasks.

\bigskip
\centerline{\resizebox{!}{3.0in}{\includegraphics{conquest.eps}}}
\bigskip
}

\problempart Wendy and Steve want to know how long conquering the
galaxy will take.  Steve suggests dividing the total number of days of
work by the number of workers, which is two.  What lower bound on the
time to conquer the galaxy does this give, and why might the actual
time required be greater?

\solution{
\begin{eqnarray*}
\frac{8 + 18 + 9 + 7 + 4 + 6 + 8}{2} & = & 30 \text{ days}
\end{eqnarray*}

If working together and interrupting work on a task were permitted,
then this answer would be correct.  However, the rules may prevent
Wendy and Steve from both working all the time.}

\problempart Wendy proposes a different method for determining the
duration of their project.  She suggests looking at the duration of
the ``critical path'', the longest sequence of tasks such that each
depends on the one before.  What lower bound does this give, and why
might it also be too low?

\solution{The longest sequence of tasks is devising a logo (8 days),
seizing the U. N. (9 days), training the army (4 days), and then
defeating Microsoft (8 days).  Since these tasks must be done
sequentially, galactic conquest will require at least 29 days.

If there were enough workers, this answer would be correct; however,
with only two workers, Wendy and Steve may be unable to make progress
on the critical path every day.}

\problempart What is the minimum number of days that Wendy and Steve
need to conquer the galaxy?  No proof is required.

\solution{
36 days - add explanation.
}

\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%% S99 ps7



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (15 points)} 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 1 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}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (10 points) } Let $D$ be the diamond-shaped region of the
real plane consisting of all points $(x, y)$ such that $|x| + |y| \leq
1$.
Prove that among every set of 5 points in $D$, there must exist two
distinct points that are at most unit distance apart.  \hint  Consider
the diagram below.

\bigskip
\centerline{\resizebox{2.0in}{!}{\includegraphics{figs/diamond.eps}}}
\bigskip

\solution{The diagram for the preceding problem part shows that the
set $D$ can be partitioned into four smaller diamonds.  By the
pigeonhole principle, at least two of the five points must be
contained in the same small diamond.  These two points are distance at
most one apart.

(Note that boundary points can be assigned to smaller diamonds
arbitrarily.)
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (15 points) } Let $G$ be a simple, undirected graph with
a total of 100 vertices, all with even degree.  Prove that there
exists a set of three vertices, all with the same degree.

\solution{There are two cases.  First, suppose that there is a vertex
with degree 98.  Then there is at most one vertex with degree 0.  The
remaining 98 vertices must have degrees in the range $2, 4, \ldots,
96$, which includes 48 possibilities.  Therefore, by the pigeonhole
principle, there are at least three vertices with the same degree.

On the other hand, suppose that there is no vertex with degree 98.
Then all 100 vertices must have degrees in the range $0, 2, \ldots,
96$, which includes 49 possibilities.  Again, by the pigeonhole
principle, there must be at least three vertices with the same degree.
}



%END   Ray's problems

%BEGIN Ivan's problems (spring '98)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset6 problem1 spring98
\problem 

Consider a standard checkerboard with 64 squares arranged on an 8 by 8 grid.
Suppose I place 33 checkers on the squares.  Prove that either two checkers must
be in one square, or two adjacent squares must both have checkers in them.  Adjacent
squares are those that share a full border(not just a corner).  I.e., no square has
more than four squares adjacent to it, and corner squares have only two squares
adjacent to them.

\solution{
{\bf Solution:}
Suppose I place the checkers on the squares.  
Suppose I label each square with a number between 1
and 64, putting a 1 in the upper left square, a 2 in the square to its right,
a 3 in the next square to the right until I put an 8 in the upper right
square, and continuing this pattern with a 9 below the 1... until I put a 64
in the lower right square.  Now consider the 32 pairs of squares denoted by
$2k-1, 2k$, for $1 \leq k \leq 32$.  (So 1 pairs with 2, 3 pairs with 4 etc.)
It is clear that for each pair of squares, the two squares in the pair
are adjacent to each other.  

Since there are 32 pairs and 33 checkers, then,
by the pigeonhole principle, at least one pair must receive two checkers.
Either both of these checkers go into the same square in that pair, or each
goes into a different square in that pair, and, therefore, either two checkers
go into one square or two adjacent squares(the pair) each get a checker.
Therefore, if I place 33 checkers onto the squares, either two checkers must
be in one square or two adjacent squares must both have checkers in them.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset7 problem7 spring98
%pigeonhole subset sum
\problem{\mbox{}}

Let $a_1,\ldots,a_n$ be $n$ positive integers  ($n \geq 2$)
such that $1 \leq a_i \leq  \lfloor (2^n-2)/n \rfloor$ for all $i =1,\ldots,n$.
Prove that there are two disjoint non-empty  subsets $S,T \subseteq 
\{1,\ldots,n\}$ such that
\[ \sum_{i \in S} a_i= \sum_{i \in T} a_i \ . \]

\solution{
There are $2^n -1$ non-empty subsets $S$ of $\{1,\ldots,n\}$.
Consider, for each such subset, the sum $sum(S) = \sum_{i \in S} a_i$.
Since $1 \leq sum(S) \leq 2^n-2$, it follows that there are two different
sets $S_1$ and $S_2$ such that $sum(S_1) = sum(S_2)$ (we
use the pigeonhole principle: the pigeons are the sets $S$ and
the holes are the numbers $sum(S)$; there are $2^n-1$ pigeons
and $2^n-2$ holes.) We now define $S_1' = S_1 - (S_1 \cap S_2)$ and
$S_2' = S_2 - (S_1 \cap S_2$). We now have
 \[ sum (S'_1) = sum(S_1) - sum(S_1 \cap S_2) = sum(S_2) - sum(S_1 \cap S_2)
= sum(S'_2) \]
and $S'_1$ and $S'_2$ are disjoint. Therefore, $S'_1$ and $S'_2$
are the desired solution.
}

%END   Ivan's problems

%BEGIN George's problems
%%%%%%%%%%%%%%  Fall 2000 PS 7     %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%

\problem 
\begin{problemparts}
\problempart
Theory Pig has often complained that the
name ``Pigeonhole Principle'' is verbose and awkward.  He proposes the
more concise term ``Pig Principle'' for the same idea.  Recently, he
devised a problem involving this idea in order to promote his
terminology.\\
\\
Suppose that $m$ pigs are lined up, and each pig is given
one or more tasty treats.  Prove that there is always a set of pigs
that are consecutive in the lineup and that all together receive a
number of treats that is a multiple of $m$.

For example, suppose that there are $m = 5$ pigs, and that they
receive 1, 6, 2, 7, and 9 treats respectively.  Then the claim holds
in this case, because the second, third, and fourth pigs received $6 +
2 + 7 = 15$ treats altogether, and 15 is a multiple of 5.

\solution{ Let $P_i$ be the total number of treats given out to the
first $i$ pigs.  Thus in the above example, $P_1 = 1$, $P_2 = 7$,
$P_3=9$, etc. There are two cases.  In the first case, suppose that 
at least one of $P_1, P_2, \ldots, P_m$ is congruent to 0 modulo $m$.
In particular, suppose that $P_j$ is congruent to 0 modulo $m$.  This
implies that the number of treats received by the first $j$ pigs is a
multiple of $m$, and so the claim holds.  In the second case, suppose
that none of $P_1, P_2, \ldots, P_m$ is congruent to 0 modulo $m$.
Then each of the $m$ terms $P_1, P_2, \ldots, P_m$ is congruent to one
of the $m-1$ values $1, 2, \ldots, m-1$ modulo $m$.  By the Pig
Principle, there are at least two terms $P_j$ and $P_k$ that are
congruent to the same value modulo $m$.  Thus pigs $j+1, j+2, \ldots,
k$ received a total of $P_k - P_j$ treats, which is a multiple of $m$.
}
   
%%%%%%%%%%%%%%  Fall 2000 PS 7     %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%

\problempart  A lattice point is a point in a coordinate plane for which
both coordinates are integers.  Prove that no matter what five lattice
points might be chosen in the plane at least one of the segments that joins
two of the chosen points must pass through some lattice point in the plane.


\solution{To show that one of the line segments connecting five lattice points
must pass through some lattice point in the coordinate plane, note that there four
``parity'' classes for the coordinates of a lattice point: odd, odd; odd, even;
even, odd; and even, even. On the pigeonhole principle some two of the five lattice
points, say $(x_1, y_1)$ and $(x_2, y_2)$ must belong to the same class. This implies
that $x_1 + x_2$ and $y_1 + y_2$ are both even numbers, making the midpoint
of the segment joining the points, namely $[(x_1 + x_2)/2, (y_1 + y_2)/2]$, 
a lattice point.

}                     
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%END   George's problems

%BEGIN Josh's problems
%END   Josh's problems

%BEGIN Tina's problems
\ppart \textbf{Pigeonhole Principle}

{\bf (a)} Do \S 4.2, Exercise 10 from the Rosen textbook.

\solution{The midpoint of the segment whose endpoints are $(a,b)$ and
$(c,d)$ is $\left(\frac{a+c}{2},\frac{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.}

{\bf (b)} Do \S 4.2, Exercise 30 from the Rosen textbook.

\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.}

{\bf (c)} Do \S 4 Supplementary Exercises, Exercise 10 from the Rosen textbook.

\solution{Using the generalised pigeonhole principle, we see that we
need $5\times 12+1 = 61$ people.}

{\bf (d)} Do \S 4 Supplementary Exercises, Exercise 16 from the Rosen textbook.

\solution{Partition the set of numbers from $1$ to $2n$ into the $n$
pigeonholes $\{1,2\},\{3,4\},\ldots,\{2n-1,2n\}$. If we have $n+1$ numbers
from this set (the pigeons), then two of them must be in the same hole.
This means that among our collection are two consecutive numbers. Clearly
consecutive numbers are relatively prime (since every common divisor must
divide their difference, 1).}
%%%%%%%%%%%%%%%%%%%%

%END   Tina's problems




%%% begin Yu-Han's problems for Fall 2001

% Rosen problems, similar to above
% outcomes 7, pigeonhole
% Yu-Han, Fall 2001


\problem 

\bparts
\ppart Rosen \S 4.2, Exercise 10.

\solnospace{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.

\solnospace{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




% The Pig Walk
% outcomes 1,7

\problem {\bf The Pig Walk}

Suppose that Theory Pig wants to take a walk on his neighborhood grid to location
$(n, n)$.  He starts at position $(0, 0)$.  At any
time, he can step North (incrementing the first coordinate) or step East
(incrementing the second coordinate).  In this problem, we'll use the Division
Rule to count how many different ways he can reach position $(n, n)$, for
$n \in \nats$.

\begin{problemparts}

\problempart Let's take a mapping that maps a length $2n$ sequence, $p$, 
of the integers $1, 2,
\ldots, 2n$, into a sequence, $p'$, in which odd numbers remain in the same
positions and even numbers remain in the same positions, but the odd and
even numbers are each sorted into increasing order.  This map is $k$ to
one for what $k$?  Explain.

\solnospace{$k=n!^2$.  Let's look at the even numbers in $p'$ first.  
How many different
ways can we re-order them so as to get strings $p$?  
Take the first even number and consider the
locations we can put it in.  There are $n$ choices, corresponding to the locations
where even numbers occur in string $p'$.  The next even number in $p'$ has $n-1$
choices, etc... so we have $n \times n-1 \times \cdots \times 1 = n!$ possible
re-orderings.  Similarly, there are $n!$ re-orderings for the odd numbers, and so
we have a total of $n!^2$ re-orderings for both the odd and even numbers together,
by the Product Rule.  Since each re-ordering corresponds to a $p$ that maps to
the same $p'$, the given map must be a $n!^2$ to 1 mapping. 
}

\ppart How many different ways are there to list the numbers $1, 2,
\ldots, 2n$ such that the even numbers appear in increasing order and the
odd numbers appear in decreasing order?

\solnospace{There are $(2n)!$ ways to list the numbers $1, 2, \ldots, n$.
Mapping any such list, $p$, into, $p'$, defines a $n!^2$-to-1 mapping that
takes an arbitrary listing to a listing in which the odd and even numbers
are sorted in increasing order.  Thus, by the Division Rule, there are
$(2n)!/n!^2$ listings in which the odd and even numbers appear in
increasing order.}

\problempart Explain why the number of paths Theory Pig can follow is the
same as the answer to part~(b).

\solnospace{Each time Theory Pig takes a step North, write down an even
number, starting with 2 and working up.  Each time Theory Pig takes a
step East, write down an odd number, starting with $2n-1$ and working down.

Note that if we use binomial coefficients, to be introduced next week,
then the solution is easy: Theory Pig must take $2n$ steps in total.  Of
these, he must choose a subset of $n$ to be North steps.  This gives
$\binom{2n}{n}$ different ways to reach $(n, n)$.}

\end{problemparts}



%% The Pig Principle
% outcomes 7, pigeonhole
% Yu-Han, Fall 2001



\problem {\bf The Pig Principle}

Having reached $(n,n)$ successfully but having been pooped on by a pigeon
along the way, Theory Pig now has a new beef.  He complains that the name
``Pigeonhole Principle'' is verbose and awkward and proposes the following
``Pig Principle'' that he finds much more relevant to his life:

Suppose that $m$ pigs are lined up, and each pig is given some number of
tasty treats.  Theory Pig asserts that there is always a sequence of one
or more consecutive pigs in the lineup who receive a total number of
treats which is a multiple of $m$.

For example, suppose there are $m = 5$ pigs, and that they
receive 1, 6, 2, 12, and 7 treats respectively.  Then the claim holds
in this case, because the second, third, and fourth pigs received $6 +
2 + 12 = 20$ treats altogether, and 20 is a multiple of 5.

Prove that Theory Pig's Pig Principle is correct.  In the process, you may
have to use the Pigeonhole Principle one last time.  \iffalse (Optionally,
you may want to think about whether the two principles are actually
equivalent, or whether Theory Pig has just proposed a weaker principle to
replace the Pigeonhole Principle.)\fi

\solnospace{Let $t_i$ be the total number of treats given out to the first
$i$ pigs in the lineup.  There are two cases.

In the first case, suppose that at least one of $t_1, t_2, \ldots, t_m$ is
congruent to 0 modulo $m$.  In particular, suppose that $t_j$ is congruent
to 0 modulo $m$.  This implies that the number of treats received by the
first $j$ pigs is a multiple of $m$, and so the claim holds.

In the second case, suppose that none of $t_1, t_2, \ldots, t_m$ is
congruent to 0 modulo $m$.  Then each of the $m$ terms $t_1, t_2, \ldots,
t_m$ is congruent to one of the $m-1$ values $1, 2, \ldots, m-1$ modulo
$m$.  By the Pigeonhole Principle, there are at least two terms $t_j$ and $t_k$
that are congruent to the same value modulo $m$.  Thus pigs $j+1, j+2,
\ldots, k$ received a total of $t_k - t_j$ treats, which is a multiple of
$m$.}

%% end Yu-Han's problems for Fall 2001



\end{problems}

\end{document}



