\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
%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 ps4

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

\problem {\bf (15 points)} Four people are interested in participating in
the VI-A program where each person ranks his top choices of companies
and the companies rank the students as well.  The people Albert, Ben,
Chris, and Doug are interested in companies AT\&T, Bellcore, Compaq,
and Draper Labs.  Below are the students' rankings of the companies
and the companies' rankings of the students.

\begin{center}
\begin{tabular}{c|c} 
Student & Companies \\ \hline
Albert:  & Compaq, Bellcore, AT\&T, Draper \\
Ben:     & AT\&T, Bellcore, Draper, Compaq \\
Chris:   & Compaq, Draper, AT\&T, Bellcore \\
Doug:    & Draper, AT\&T, Bellcore, Compaq 
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{c|c}
Company & Students \\ \hline
AT\&T:    & Doug, Albert, Chris, Ben \\
Bellcore: & Chris, Ben, Albert, Doug \\
Compaq:   & Doug, Chris, Albert, Ben \\
Draper:   & Ben, Doug, Chris, Albert
\end{tabular}
\end{center}

\begin{problemparts}
\problempart What is a student-optimal stable marriage set for
this problem?

\solution 

You were guaranteed to get a student-optimal stable marriage set if
you ran the stable marriage algorithm given in lecture, where Students
are Men and Companies are Women.  The result is the following assignment:

\begin{center}
\begin{tabular}{c|c|c} 
Student & Companies & Rank in the original list \\ \hline
Albert:  & Bellcore & 2\\
Ben:     & AT\&T & 1\\
Chris:   & Compaq & 1\\
Doug:    & Draper &1
\end{tabular}
\end{center}

\problempart What is a company-optimal stable marriage set for
this problem?

\solution

Similarly, you were guaranteed to get a company-optimal stable
marriage set if you ran the stable marriage algorithm given in
lecture, where Students are Women and Companies are Men.  The result
is the following assignment:

\begin{center}
\begin{tabular}{c|c|c}
Company & Students & Rank in the original list\\ \hline
AT\&T:    & Albert & 2\\
Bellcore: & Ben & 2\\
Compaq:   & Chris & 2\\
Draper:   & Doug & 2
\end{tabular}
\end{center}




\problempart Are there any other stable marriage sets possible?

\solution
We noted in lecture that the Gale-Shapley dating protocol yields a
(necessarily unique) man-optimal stable marriage assignment, and moreover
this assignment is also the unique women-pessimal one.  Therefore, from
parts (a) and (b) we know that in both student-optimal and
student-pessimal stable marriage sets, Chris is married to Compaq, and
Doug to Draper Labs.  So Chris can never do better or worse than Compaq in
any stable marriage set, viz., he is married to Compaq in all stable
marriage sets; likewise for Doug and Draper.  Hence the possibilities for
Albert and Ben are only AT\&T and Bellcore.  Since both these
possibilities are given in the two solutions above, there are no other
stable marriage sets possible.


\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)
%END   Ivan's problems

%BEGIN George's problems
%END   George's problems

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

%BEGIN Tina's problems
%END   Tina's problems


\end{problems}

\end{document}



