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

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip
                                % query 

\renewcommand{\reading}{Course notes on induction.}

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

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

\begin{problem}
Use induction to prove that the following inequality holds for all
integers $n \geq 1$.

\begin{eqnarray*}
% old
%\frac{1 \cdot 3 \cdot 5 \cdots (2n - 1)}{2 \cdot 4 \cdot 6 \cdots (2n)}
%& \geq & \frac{1}{2n}
\frac{1 \cdot 3 \cdot 5 \cdots (2n + 1)}{2 \cdot 4 \cdot 6 \cdots (2n+2)}
& \geq & \frac{1}{2n+2}
\end{eqnarray*}

\solution{We use induction.  Let $P(n)$ be the proposition that:

\begin{eqnarray*}
%old
%\frac{1 \cdot 3 \cdot 5 \cdots (2n - 1)}{2 \cdot 4 \cdot 6 \cdots (2n)}
%& \geq & \frac{1}{2n}
\frac{1 \cdot 3 \cdot 5 \cdots (2n + 1)}{2 \cdot 4 \cdot 6 \cdots (2n+2)}
& \geq & \frac{1}{2n+2}
\end{eqnarray*}

First, we prove $P(0)$.  In this case, both side of the inequality are
equal to $1/2$, and so the inequality holds.  Next, for each $n \geq
0$, we must show that $P(n)$ implies $P(n+1)$.  Assume that $P(n)$ is
true.  Then we can reason as follows:

\begin{eqnarray*}
%\frac{1 \cdot 3 \cdot 5 \cdots (2n - 1) (2n + 1)}
%{2 \cdot 4 \cdot 6 \cdots (2n) \cdot (2n + 2)}
%& \geq & \frac{1}{2n} \cdot \frac{2n+1}{2n+2} \\
%& > & \frac{1}{2(n+1)}
\frac{1 \cdot 3 \cdot 5 \cdots (2n + 1) (2n + 3)}
{2 \cdot 4 \cdot 6 \cdots (2n+2)(2n + 4)}
& \geq & \frac{1}{2n+2} \cdot \frac{2n+3}{2n+4} \\
& > & \frac{1}{2n+4}
\end{eqnarray*}

\noindent The first step uses the induction hypothesis, $P(n)$.  The
second step uses the fact that $(2n+3) / (2n+2) > 1$ for all $n \geq 1$.
Therefore, by induction, the proposition $P(n)$ is true for all $n
\geq 1$, and the claim is proved.
}

\end{problem}

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

\begin{problem}
This term in 6.042, we're constantly trying to divide a class of $n$
students into groups of either 4 or 5 students.  

\bparts

\ppart Let's try to use strong induction prove that a class with $n
\geq 8$ students can be divided into groups of 4 or 5.

\begin{proof}
The proof is by strong induction.  Let $P(n)$ be the proposition that
a recitation with $n$ students can be divided into teams of 4 or 5.

First, we prove that $P(n)$ is true for $n = 8$, 9, or 10 by showing
how to break classes of these sizes into groups of 4 or 5 students:

\begin{eqnarray*}
8 & = & 4 + 4 \\
9 & = & 4 + 5 \\
10 & = & 5 + 5
\end{eqnarray*}

Next, we must show that $P(8), \ldots, P(n)$ imply $P(n + 1)$ for all
$n \geq 10$.  Thus, we assume that $P(8), \ldots, P(n)$ are all true
and show how to divide up a class of $n + 1$ students into groups of 4
or 5.  We first form one group of 4 students.  Then we can divide the
remaining $n - 3$ students into groups of 4 or 5 by the assumption
$P(n - 3)$.  This proves $P(n + 1)$, and so the claim holds by
induction.
\end{proof}

This proof contains a critical logical error.  (In fact, the claim is
false!)  Identify the first sentence in the proof that does not follow
and explain what went wrong.

\solution{The first error is in the sentence:

\begin{quotation}
\noindent Then we can divide the remaining $n - 3$ students into
groups of 4 or 5 by the assumption $P(n - 3)$.
\end{quotation}

If $n = 10$, then $P(n - 3) = P(7)$, which is not among our
assumptions $P(8), \ldots, P(n)$.  In this case, $P(n + 1) = P(11)$ is
actually false.}

\ppart Provide a correct strong induction proof that a class with $n
\geq 12$ students can be divided into groups of 4 or 5.

\solution{The proof is by strong induction.  Let $P(n)$ be the
proposition that a recitation with $n$ students can be divided into
teams of 4 or 5.

First, we prove that $P(n)$ is true for $n = 12$, 13, 14, and 15 by
showing how to break classes of these sizes into groups of 4 or 5
students:

\begin{eqnarray*}
12 & = & 4 + 4 + 4 \\
13 & = & 4 + 4 + 5 \\
14 & = & 4 + 5 + 5 \\
15 & = & 5 + 5 + 5
\end{eqnarray*}

Next, we must show that $P(12), \ldots, P(n)$ imply $P(n + 1)$ for all
$n \geq 15$.  Thus, we assume that $P(12), \ldots, P(n)$ are all true
and show how to divide up a class of $n + 1$ students.  We first form
one group of 4 students.  Then we can divide the remaining $n - 3$
students into groups of 4 or 5 by the assumption $P(n - 3)$.  (Note
that $n \geq 15$ and so $n - 3 \geq 12$; thus, $P(n - 3)$ is among our
assumptions $P(12), \ldots, P(n)$.)  This proves $P(n + 1)$, and so the
claim holds by induction.}

\eparts

\end{problem}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{problem}
The game of \emph{Mini-nim} is defined as follows: Some positive number of
sticks are placed on the ground.  Two players take turns removing one,
two, or three sticks.  The player to remove the last one loses.

Use strong induction to show that:

{\em The second player has a winning strategy if the number of sticks,
equals $4k+1$ for some $k \in \naturals$; otherwise, the first player has
a winning strategy.}

\solution{
The induction hypothesis, $P(n)$, is:
\begin{quote}
If $n=4k+1$, for some $k \in \naturals$, then the second player has a
winning strategy; otherwise, the first player has a winning strategy.
\end{quote}

We proceed by strong induction, starting from~$1$.

\textbf{Base case}: $n = 1$.
The first player has no choice but to remove $1$ stick and lose, which
is what the theorem says for this case.

\textbf{Strong inductive step}:
Suppose the theorem is true for numbers $1$ through $n$ and show that it
is true for $n+1$.
For the inductive step, there are four cases:
\begin{itemize}
\item
$n+1=4k+1$: show that the first player loses.  We've already handled
the base case ($1$) so we can assume $n+1 \geq 5$.  Consider what the
first player might do to win: he can choose to remove 1, 2 or 3 sticks.
If he removes one stick, the remaining number of sticks is $n = 4k$.  By
strong induction, the player who plays at this point has a winning
strategy.  So the player who played first will lose.

Similarly, if the first player removes two sticks, the remaining number is
$4(k-1)+3$.  Again, he loses, by the same reasoning.  Similarly, by
removing $3$ sticks, he loses.  So, however the first player moves, he
loses.

\item
$n+1 = 4k$: show that the first player can win.

Have the first player remove 3 sticks: the second player then sees
$4(k-1)+1$ sticks, and loses, by the strong inductive hypothesis.

\item
$n+1 = 4k+2$: show that the first player can win.

Have the first player remove 1 stick: the second player then sees
$4k + 1$ sticks, and loses as in the previous case.

\item
$n+1 = 4k+3$: show that the first player can win.

Have the first player remove 2 sticks: again, the second player sees
$4k + 1$ sticks and loses.
\end{itemize}

So in any case, $P(n+1)$ is true, and by strong induction, we conclude
that $P(n)$ holds for all $n \geq 1$.
}

\end{problem}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{problem}
Consider the following equivalent way of viewing the subset take-away game
from the in-class problem on Friday, Week 2: 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.

\bparts

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

\ppart If the whole set $A$ is a possible move in a game, explain why the
1st player must have a winning strategy.

\solution{We reason by cases to show that player 1 has a winning strategy.
Suppose game $G$ includes $A$ as a possible move.  Let $G'$ be the same
game as $G$ except that $A$ is removed from the set of possible moves.

\textbf{Case 1}: Player 1 has a winning strategy in the game $G'$.  Then
the first move of Player 1's winning strategy will also be a legal move in
game $G$.  Moreover, after this move in game $G$, the set $A$ will no
longer be a possible move, so the move will lead to the same winning
situation for Player 1 as in game $G'$.  So Player 1 has a winning
strategy in this case.

\textbf{Case 2}: Player 2 has a winning strategy in game $G'$.  Then
player 1 should choose $A$ as his first move in game $G$.  This puts him
in the position of the Player 2 in game $G'$, and so Player 1 will have a
winning strategy in this case as well.

So in any case, we conclude that Player 1 has a winning strategy ---even
though we don't have a clue what it is.}

\eparts

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{problem}
%A set, which 
%which comes with
%an ordering relation $<$,
%is {\em well ordered} 
%if every nonempty set has a least element.
%Consider the set $\cal S$ of ordered pairs $(x,y)$
%for $x,y \in \naturals$ with the ordering relation
%$<$ defined by $(x,y) < (w,z)$ 
%if $(x<w)$ or if $(x=w)$ and $(y<z)$.

%Given that $\naturals$ is well ordered,
%show that $\cal S$ is well ordered.
%
%\solution{
%Let $R$ be a nonempty subset of ordered pairs $(q,r)$ in $\cal S$.
%By the well ordering of $\naturals$, we know that some nonempty set, $T$, 
%of elements in $R$ must have the smallest $q$, which we will
%call $q_{min}$.   
%All elements in $T$ are of the form $(q_{min},r)$.
%Again by the well ordering of $\naturals$, we know that
%some element in $T$ has the smallest
%$r$.  Call this element, $(q_{min},r_{min})$.  
%For any $(w,v)$ in $R$,
%either (1) $q_{min}<w$ so that 
%$(q_{min},r_{min}) < (w,v)$,  
%(2) $q_{min}=w$ and $r_{min} < v$,  so that 
%$(q_{min},r_{min}) < (w,v)$, or 
%(3) $q_{min}=w$ and $r_{min} = v$,  so that 
%$(q_{min},r_{min}) = (w,v)$.
%Thus $(q_{min},r_{min})$ is the least element of $R$. 
%}



%\end{problem}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\begin{problem}
%When you use long division to divide an integer $n$ by a positive
%integer $d$, you get a quotient $q$ and a small remainder $r$.  The
%theorem below states this formally:
%
%\begin{theorem}[Division Algorithm]
%Let $n$ be an integer, and let $d$ be a positive integer.  Then there
%exist integers $q$ and $r$ such that
%
%\begin{eqnarray*}
%n & = & q \cdot d + r
%\end{eqnarray*}
%
%\noindent where $0 \leq r < d$.
%\end{theorem}
%
%Really, this is a theorem {\em about} long division, but traditionally
%the theorem itself is called the {\em division algorithm}.  The
%division algorithm is usually proved using the least-number principle.
%Can you devise such a proof?

%\solution{Let $S$ be the set of all ordered pairs $(q, r)$ such that
%%$r \geq 0$ which satisfy the equation above. Assume the set is
%nonempty (we show this below).  By the least-number principle, we know
%some element in this set must have the smallest $r$. For this element
%$(q,r)$, we must have $0 \leq r < d$; otherwise, $(q + 1, r - d)$
%would be an element as well.
%
%To show the set is $S$ nonempty, consider the following cases. If $n
%\geq 0$, $(0,n)$ is an element. If $n < 0$, then $(nd, -n(d-1))$ is an
%element.  Note that because $n < 0$ and $d > 1$, the quantity $-n(d-1)
%\geq 0$.}
%
%\end{problem}

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

\end{document}
