\documentclass[12pt,twoside]{article}   
\usepackage{latex-macros/course}% !! Use the macros

\renewcommand{\reading}{Notes for
\href{http://theory.csail.mit.edu/classes/6.042/spring06/ln3-tue.pdf}{Week3}}

\begin{document}
\problemset{2}                 % !! Start the problem set with its number

\begin{problem}
Consider the proper subset partial order, $\subset$, on the power set
$\power{\set{1,2,\dots 5}}$.

\bparts
\ppart What is the size of a maximal chain in this partial order?
Describe one.
\solution{Size 6, for example,
\[
\set{\emptyset, \set{1}, \set{1,2}, \set{1,2,3},\set{1,2,3,4},\set{1,2,3,4,5}}.
\]}

\ppart Describe the largest antichain you can find in this partial order.

\solution{
All the size 3 subsets of $\set{1,2,\dots 5}$ form an antichain of size 10.
This is actually the largest, though proving this is a challenge.
}

\ppart  What are the maximal and minimal elements?  Are they maximum and
minimum?

\solution{$\emptyset$ is minimum and $\set{1,2,\dots 5}$ is maximum.}

\ppart Answer the previous part for the $\subset$ partial order on the set
$\power{\set{1,2,\dots 5}} - \emptyset$.

\solution{Now the five size 1 subsets are minimal and there is no minimum.
$\set{1,2,\dots 5}$ is still maximum.}

\eparts
\end{problem}


\begin{problem}
\bparts

\ppart
Prove that a binary relation, $R$, on a set, $A$, is a strict partial
order iff it is transitive and irreflexive.

\solution{If $R$ is a strict p.o., then in particular, it is asymmetric.
So $aRa$ would imply $\neg(a R a)$, a contradiction.  It follows that
$aRa$ cannot hold, so $R$ is irreflexive.

Conversely, suppose $R$ is transitive and irreflexive.  We want to show
that $R$ is antisymmetric.  So suppose it wasn't.  Then there must be $a,b
\in A$ such that $aRb$ and $bRa$.  Now transitivity implies that $aRa$,
contradicting irreflexivity.  This contradiction shows that $R$ must be
antisymmetric.}

\ppart Prove the followng assertion claimed in Notes 3:

If $R$ is a weak partial order on a set,
$A$, then
\begin{equation}\label{rgb}
a\, R\, b  \qiff  R\set{a} \subseteq R\set{b}
\end{equation}
holds for all $a,b \in A$.

\solution{TBA}
\eparts
\end{problem}


\begin{problem}
Prove that in any sequence of $n$ different numbers
\[
a_1,a_2,\dots, a_n
\]
there is either an increasing subsequence of length greater than
$\sqrt{n}$ or a decreasing subsequence of length at least $\sqrt{n}$.

\begin{example}If $n=9$ and
\[
a_1,a_2,\dots, a_n = 6,4,7,9,1,2,5,3,8
\]
then $6,4,1$ is a decreasing subsequence of length $3=\sqrt{n}$, and
$1,2,3,8$ is an increasing subsequence of length $4 > \sqrt{n}$.
\end{example}

\hint Define a relation, $\prec$, on the set
$A \eqdef \set{a_1,\dots,a_n}$ by the rule:
\[
a_i \prec a_j \qiff  (a_i < a_j) \land (i < j).
\]
Verify that $\prec$ is a strict partial order, and apply
\href{http://theory.csail.mit.edu/classes/6.042/spring06/ln3.pdf#rule.Dilworth}
{Dilworth's Lemma}.
\solution{
\begin{proof}
The relation $\prec$ is transitive, because
\begin{align*}
(a_i \prec a_j) \land (a_j \prec a_k)
    &\implies (a_i < a_j \land i < j) \land (a_j < a_k \land j < k)
                        & \text{(def. of $\prec$)}\\
    &\iff  (a_i < a_j \land a_j < a_k) \land (i < j \land j < k)\\
    &\implies   a_i < a_k \land i < k
                        & (\text{since $<$ is transitive})\\
    &\iff a_i \prec a_k
                       & \text{(def. of $\prec$)}
\end{align*}
A similar (easier) proof shows that $\prec$ asymmetric, so $\prec$ is indeed
a strict partial order.

\iffalse
The relation $\prec$ is asymmetric, because
\begin{align*}
a_i \prec a_j &\implies i < j & \text{(def. of $\prec$)}\\\\
              &\implies \neg(j < i) & (\text{since $<$ is asymmetric})\\\\
              &\implies \neg(a_j \prec a_i) & \text{(def. of $\prec$)}\\
\end{align*}
\fi

Now given a $\prec$-chain, 
\[
a_{i_1} \prec a_{i_2} \prec \cdots \prec a_{i_k},
\]
we have $i_1 < i_2 <\cdots < i_k$ and $a_{i_1} < a_{i_2} < \cdots <
a_{i_k}$ by definition of $\prec$.  But this means precisely that
$a_{i_1}, a_{i_2}, \dots, a_{i_k}$ is an increasing subsequence of $a_{1},
a_{2},\dots a_{n}$.  So a \emph{chain} corresponds to an \emph{increasing}
subsequence.

But what does an antichain correspond to?   Suppose
$a_{i_1}, a_{i_2},\dots a_{i_k}$ is a $\prec$ antichain with the elements
arranged in decreasing order:
\[
a_{i_1} > a_{i_2} > \cdots > a_{i_k}.
\]
So for $j < m$, we have $a_{i_j} > a_{i_m}$, and since $a_{i_j}$ and
$a_{i_m}$ are $\prec$-incomparable, we must have $i_j < i_m$.  That is, an
\emph{antichain}, with its elements listed in decreasing order,
corresponds to a \emph{decreasing} subsequence of $a_{1}, a_{2},\dots
a_{n}$.

By Dilworth's Lemma, either a chain or an antichain must have size at
least $\sqrt{n}$, which means there is either an increasing or a
decreasing subsequence of this size.
\end{proof}
}

\end{problem}

% S02 ps2-4, F01 Q1
\begin{problem}
Before he was eaten by ravenous 6.042 students, Theory Pig, the former
6.042 mascot, made a startling discovery while playing with his prized
collection of unit squares over the weekend.  Here is what happened.

First, Theory Pig put his favorite unit square down on the floor as in
Figure~\ref{fig:squares}~(a).  He noted that the length of the periphery
of the resulting shape was 4, an even number.  Next, he put a second unit
square down next to the first so that the two squares shared an edge as in
Figure~\ref{fig:squares}~(b).  He noticed that the length of the periphery
of the resulting shape was now 6, which is also an even number.  (The
periphery of each shape in the figure is indicated by a thicker line.)
Theory Pig continued to place squares so that each new square shared an
edge with at least one previously-placed square and no squares overlapped.
Eventually, he arrived at the shape in Figure~\ref{fig:squares}~(c).  He
realized that the length of the periphery of this shape was 36, which is
again an even number.

Our plucky porcine pal is perplexed by this peculiar pattern.  Use
induction on the number of squares to prove that the length of the
periphery is always even, no matter how many squares Theory Pig places or
how he arranges them.

\begin{figure}[htbp]
\centering
\includegraphics[width=4in]{figures/f98ps2}
\caption{Some shapes that Theory Pig created.} \label{fig:squares}
\end{figure}

\solution{
The proof is by induction.  Let $P(n)$ be the proposition that the
periphery length is even after $n$ squares are placed.  In the base
case, $P(1)$ is true because the periphery of a single square has
length 4, which is even.

In the inductive step, assume that the periphery length is even after
$n$ squares are placed to prove that the periphery length is even
after $n+1$ squares are placed.  The $(n+1)$-th square could share 1,
2, 3, or 4 edges with previously-placed squares.

\begin{itemize}

\item If the new square shares 1 edge with a previously placed square,
then this one edge is removed from the periphery, but three edges of
the new square are added to the periphery.  Overall, the periphery
length increases by two and thus remains even.

\item If the new square shares 2 edges with previously placed squares,
then these two edges are removed from the periphery, but two edges of
the new square are added.  The periphery length is unchanged and thus
remains even.

\item If the new square shares 3 edges, then these three edges are removed
from the periphery, but one edge is added.  The periphery length
decreases by two and remains even.

\item If the new square shares 4 edges, then these four edges are removed
from the periphery and none are added.  The periphery length decreases
by four and remains even.

\end{itemize}

In all cases, the length of the periphery remains even.  Therefore,
for all $n \geq 1$, $P(n)$ implies $P(n+1)$ and the claim is proved by
induction.
}
\end{problem}

\iffalse

% source: S00 ps2, fall98
\begin{problem}  
Prove by induction on $n$ that for all $n \geq 0$, the inequality
\begin{equation}\label{xyn}
\card{x} + \card{y} \leq n
\end{equation}
has exactly $2 n^2 + 2n + 1$ solutions where $x$ and $y$
are integers.

\solution{ Let $P(n)$ be the proposition that there are $2 n^2 + 2n + 1$
  solutions to inequality~\eqref{xyn}, where $x$ and $y$ are integers.  We
  prove that $P(n)$ holds for all $n \geq 0$ by induction on~$n$.

  In the base case, $P(0)$ is true because $2 (0)^2 + 2 (0) + 1 = 1$ and
  there is one solution to the inequality~\eqref{xyn}, namely $x = y = 0$.
  \iffalse This is easily argued by contradiction.  Without loss of
  generality, suppose that $x$ is not zero.  Then, since $\card{z} \geq
  0$, for all $z$, and $\card{z} > 0$, for all $z \not = 0$, it follows
  that $\card{x} + \card{y} > 0$; a contradiction.  Thus, $x$ must be
  zero.\fi

  In the inductive step, assume $P(n)$ to prove $P(n+1)$.

  Now every integer solution to the inequality
\begin{equation}\label{n1}
\card{x} + \card{y} \leq n + 1.
\end{equation}
 is also either a solution to the inequality~\eqref{xyn} or else a solution
 to the equation
\begin{equation}\label{=n1}
\card{x} + \card{y} = n + 1.
\end{equation}
  Thus, the number of solutions to inequality~\eqref{n1} is equal to the
  number of integer solutions to inequality~\eqref{xyn} plus the number of
  integer solutions to equation~\eqref{=n1}.

  By the inductive hypothesis, there are $2 n^2 + 2n + 1$ solutions to
  inequality~\eqref{xyn}.

  To count integer solutions to equation~\eqref{=n1}, note that the value
  of  $x$  in any solution to~\eqref{=n1} must be in the range $-(n+1),
  \dots, n+1$.  If $x$ equals $-(n+1)$ or $n+1$,
  then there is a single solution, with $y = 0$.  If $x$ takes on one of
  the $2n+1$ values in the range $-n, \ldots, n$, then there are two
  solutions, one with $y = n + 1 - \card{x}$ and one with $y = -(n + 1 -
  \card{x})$.  Thus, there are $2 + 2 \cdot (2n + 1) = 4n + 4$ solutions
  to~\eqref{=n1}.

  So the number of integer solutions to inequality~\eqref{n1} is
  \[
  (2 n^2 + 2n + 1) +   4n + 4 = 2 (n+1)^2 + 2 (n + 1) + 1.
  \]
  which proves $P(n+1)$.  This concludes the inductive step.}
\end{problem}
\fi


%adapted from F01 PS2-3

\begin{problem}
Pinpoint, and illustrate with a counterexample, \emph{exactly} where the
following \emph{proof} goes awry.

\begin{lemma}
For any prime $p$ and positive integers $n, x_1, x_2,\ldots, x_n$, if
$p \divides x_1x_2\dots x_n$, then $p \divides x_i$ for some $1\leq i\leq n$.
\end{lemma}

\begin{falseproof}
Proof by strong induction on $n$.

\textbf{Base case} $n= 1$: When $n=1$, we have $p\divides x_1$, therefore
we can let $i=1$ and conclude $p\divides x_i$.

\textbf{Induction step}: Now assuming the claim holds for all $k\leq n$, we must
prove it for $n+1$.

So suppose $p\divides x_1x_2\ldots x_{n+1}$.  Let $y_n = x_n x_{n+1}$, so
$x_1x_2\ldots x_{n+1} = x_1x_2\ldots x_{n-1}y_n$.  Since the righthand
side of this equality is a product of $n$ terms, we have by induction that
$p$ divides one of them.  If $p\divides x_i$ for some $i < n$, then we have the
desired $i$.  Otherwise $p\divides y_n$.  But since $y_n$ is a product of the two
terms $x_n, x_{n+1}$, we have by strong induction that $p$ divides one of
them.  So in this case $p \divides  x_i$ for $i = n$ or $i = n+1$.
\end{falseproof}

\solution{Notice that nowhere in the proof is the fact that $p$ is prime
used.  So if this proof were correct, the Lemma would hold not just for
prime $p$, but for any positive integer $p$.  But of course, the Lemma is
false when $p$ is not prime, for example if $p=6$, $x_1=3$ and $x_2=4$, we
have $p\divides x_1x_2$ but $\neg(p \divides x_1)$ and $\neg(p \divides
x_2)$.  So there has to be something wrong somewhere.

The statement ``we have by strong induction that $p$ divides
one of them'' is the place where the proof breaks down: it appeals to
strong induction to justify applying the induction hypothesis for $2=k\leq
n$.  But the base case was $n=1$, so we can't assume $2 \leq n$.  Note
that the reasoning above is fine for every $n\geq 2$, so the whole proof
would be fine if we had an argument to prove the claim for $n+1=2$.

Now in fact, if a prime, $p$ divides $x_1x_2$, it must divide $x_1$ or
$x_2$; this follows by prime factorization of integers (and we'll show you
another proof later in the term).  But the proof never made use of this
fact.}

\end{problem}

\iffalse

\begin{problem}
%(* difficult) From F97 PS2 Problem 10, much revised by ARM

An $n$-player \emph{tournament} consists of some set of $n\geq 2$
\emph{players}, and has the property that for every two players, $p \neq
q$, either $p$ beat $q$ or $q$ beat $p$, but not both.  \iffalse That is,
player $p$ beats player $q$ iff $q$ does not beat $p$, for all players $p
\neq q$.\fi

A sequence of distinct players $p_1,p_2, \ldots, p_k$, such that each
player beats the next one (that is, $p_i$ beats player $p_{i+1}$ for $1
\leq i < k$) is called a {\em ranking} of these players.  If also player
$p_k$ beats player $p_1$, the ranking is called a $k$-\emph{cycle}.

\begin{problemparts}

\problempart Prove by induction that in every tournament, either there is a
``champion'' player that beats every other player, or there is a 3-cycle.

\solution{The induction hypothesis $P(n)$, is
``In an $n$-player tournament, either there is a player that
beats every other player, or there is a 3-cycle.''

\textbf{Base case} $n=2$: By definition of a 2-player tournament, one of the
players beats the only other player and therefore is the champion.

\textbf{Inductive step}:
Assume that $P(n)$ is true in order to show that $P(n+1)$ is true.

Consider an $n+1$-player tournament.  If there is a champion, we are done.
So we may assume that every player is beaten by some other player.  Now
remove any player, say player $p$, and treat the remaining $n$ players as an
$n$-player tournament.  There are two cases:

1) Every player in the $n$-player tournament is beaten by some other
player in the tournament.

2) There is some champion in the $n$-player tournament who beats every
other player in the $n$-player tournament.

In case (1), we have by induction hypothesis a 3-cycle of players in the
$n$-player tournament.  Since a 3-cycle in the $n$-player tournament will
also be a 3-cycle in the full $n+1$-player tournament, we are OK in this
case.

In case (2), there is some ``champion'', $q$, in the $n$-player
tournament.  Since everybody in the ($n+1$)-player tournament is beaten by
somebody, $q$ must be beaten by a player not in the $n$-player tournament,
namely, $p$ must beat $q$.  For the same reason, there is some player $r$
that beats $p$.  Since $r$ is in the $n$-player tournament, $r$ is beaten
by the champion $q$.  So we have found a 3-cycle $p,q,r$.}

\problempart A {\em consistent ranking} is a sequence $p_1,p_2, \ldots,
p_n$ of all $n$ players in the tournament such that each player beats all
the later players in the sequence (that is, $p_i$ beats $p_j$ iff $i < j$,
for $1 \leq i,j \leq n$).  Use the previous problem part and another
induction argument to prove that a tournament has no consistent ranking
iff some subset of three of its players has no consistent ranking.

\solution{The restriction of a tournament to any subset of two or more of
its players will also a (sub)tournament, by the definition of tournament.
Also any consistent ranking of a tournament remains consistent when
restricted to a subset of players.  So if some subset of three players has
no consistent ranking, then the whole tournament can't have a consistent
ranking either.

So we have only to prove the converse implication: if every three players
have a consistent ranking, then the tournament as a whole has one.  The
proof is by induction on $n$.

{\bf Base case $n=2$:} Every two player tournament obviously has a
consistent ranking.

{\bf Inductive step:} Suppose $n\geq 2$ and there is a consistent ranking
of any tournament of $n$ players whose three-player subsets have
consistent rankings.  Now consider any $n+1$ player tournament whose
three-player subsets have consistent rankings.

This $n+1$ tournament cannot have a 3-cycle, because there is no
consistent ranking for the players in the 3-cycle.  Hence, by the previous
problem part, the tournament has a champion.  The $n$-player tournament
obtained by ignoring the champion also has no 3-cycles, so by induction it
has a consistent ranking.  Then the champion followed by the ranking of
$n$-nonchampions is a consistent ranking of the whole tournament of $n+1$
players.}
\end{problemparts}


\end{problem}

\fi


%source: S02 ps2-3 and spring00 ps2
\begin{problem} 
6.042 has filled the TEAL room in terms gone by, and one plan considered
by the 6.042 staff at that time involved having students work in subgroups
of exactly 4 or exactly 7 students.  But TEAL tables hold up to 9
students, so this plan was abandoned plan when it was realized that
students at a table can be split this way only if there are 4, 7, or 8
students at the table.

\begin{problemparts} 

\problempart \label{k} What is the smallest number, $k$, such that all
tutorials of $k$ or more students can be split into teams of 4 and 7?
Prove that $k-1$ students \emph{cannot} be split in this way.

\solution{The smallest number $k$ such that all tutorials of $k$ or more
students \emph{can} be split into teams of 4 and 7 is $18$.

A tutorial of size $17$ \emph{cannot} be split into teams of 4 and 7.  In
particular, a tutorial of size $17$ can contain at most 2 groups of 7.
Consider the various possible splits of the tutorial:
\begin{enumerate}
\item no groups of 7:
the only other group size is 4.  We cannot split the tutorial of 17,
since it is not divisible by 4;
\item one group of 7: again, the remaining
number, 10, of students is not divisible by 4; 
\item two groups of 7: the
remaining 3 students are not a group of 4 or 7.
\item three or more groups of 7: clearly, this accounts for
  $21>17$ students and is inadmissible.
\end{enumerate}
}


\problempart Now complete the proof of your answer to part~\eqref{k}.
Namely, prove (by induction) that all tutorials of $k$ or more students
\emph{can} be split into teams of size 4 and 7.

\solution{
\begin{proof} (strong induction).  Define $P(n)$ to be the predicate that
a tutorial of size $n$ can be split into groups of size 4 and 7.  Being
``split'' really means that $n = 4x + 7y$ for some natural numbers $x,y$.
So we can give a completely precise definition:
\[
P(n) \eqdef\quad n \geq 18 \implies \exists x, y \in \naturals\ [n = 4x +
7y].
\]
We must show that $P(n)$ holds for all $n \in \naturals$.  By strong
induction, we consider $n \geq 18$ and assume the strong induction
hypothesis
\begin{equation}\label{SIH}
\forall m\ [18 \leq m < n \implies \exists x_m, y_m \in \naturals\ (m =
4x_m + 7y_m) ].
\end{equation}
in order to prove that $P(n)$ holds.

The proof divides into cases

\textbf{Case 0:} ($n < 18$) $P(n)$ holds trivially since the hypothesis $n
\geq 18$ is false.

\textbf{Case 1:} ($n=18$).  $18 = 4 \cdot 1 + 7 \cdot 2$, so $P(18)$ is
proved.

\textbf{Case 2:} ($n=19$).  $19 = 4 \cdot 3 + 7 \cdot 1$, so $P(19)$ is
proved.

\textbf{Case 3:} ($n=20$).  $20 = 4 \cdot 5 + 7 \cdot 0$, so $P(20)$ is
proved.

\textbf{Case 4:} ($n=21$).  $21 = 4 \cdot 0 + 7 \cdot 3$, so $P(21)$ is
proved.

Notice that we proved Cases 0--4, without needing to use the induction
hypothesis~(\ref{SIH}).

\textbf{Case 5:} ($n \geq 22$).  In this case, letting $m \eqdef n - 4$,
we have $18 \leq m < n$, so by induction hypothesis~(\ref{SIH}), we
conclude that there are natural numbers $x_m,y_m$ such that
\[
m = 4x_m + 7y_m.
\]
So
\begin{equation}\label{m}
n = m + 4 = 4(x_m+1) + 7y_m.
\end{equation}
Letting $x \eqdef x_m+1$ and $y \eqdef y_m$ in~(\ref{m}) implies
\[
n = 4x + 7y,
\]
which proves $P(n)$.
\end{proof}}

\end{problemparts}
\end{problem}

%excerpted from F05, ps2
\begin{problem}
Consider the following equivalent way of viewing the subset take-away game
from the Team problem last week: for a fixed, finite set, $A$,
let $\mathcal{S}$ initially be all the proper subsets of $A$.  Players
alternately choose a set $B \in \mathcal{S}$ and remove $B$ and all sets
that contain $B$ from $\mathcal{S}$; they then continue playing on the
updated $\mathcal{S}$.  The player that chooses the last set in
$\mathcal{S}$ wins.

Use the well-ordering property to show that, in any game, one of
the players must have a winning strategy.  \hint Consider games whose
initial set, $\mathcal{S}$, is an arbitrary collection of subsets of, $A$,
not necessarily all the proper subsets of $A$.  Reach a contradiction by
considering a minimum size game with no winning strategy for either
player.  What is a useful measure of size of a game?

\solution{
Let $S$ be the smallest collection such that neither player has a winning
strategy.  Consider the state after each possible first move by player 1.  
No such state can correspond to a winning position for player 1 since that
would mean a winning strategy for player 1 on $S$.  Nor can every such state
be a winning position for player 2 since that would mean player 2 has a 
winning strategy on $S$.  Hence, at least one such state must have no
winning strategies for both players.  But this state is a smaller collection
than $S$, contradiction.  Thus, by the W.O.P, some player must have a 
winning strategy for any collection $S$, and for the proper subsets of $A$ 
in particular. 
}
\end{problem}



\end{document}
