\documentclass[11pt]{article}
\usepackage{macros-course-lectures}
\begin{document}

\subsection{Nim}

The game of Nim is played 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 stick loses. \\
\\
Play, starting with 21.

\begin{theorem}
Player 2 has a winning strategy if the number of sticks is $4k+1$ for
some $k$.
Player 1 has a winning strategy otherwise. 
\end{theorem}

Formally: \\
A strategy is a function that says how many to remove, based on the
number that are left. \\
\\
$P(n)$: \\
1. If $n = 4k+1$ for some $k$ then the second player has a winning
strategy. \\
2. If $n = 4k+2$, $4k+3$, or $4k$ for some $k$, then the first player
has a winning strategy. \\
\\
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq 1 (P(n))$ \\
1. (Base) $P(1)$ \\
\> \> \> \> \> $n$ is of the form $4k+1$, and player 1 loses. \\
2. (Inductive step) 
$\forall n \geq 1 [(\forall i, 1 \leq i \leq n (P(n))) \Rightarrow P(n+1)]$ \\
\> 1. Fix $n \geq 1$ \\
\> 2. Assume $\forall  i, 1 \leq i \leq n (P(i))$ \\
\> 3. $P(n+1)$ \\
\> \> 1. $(\exists k (n = 4k)) \Rightarrow P(n+1)$. \\
\> \> 2. $(\exists k (n = 4k+1)) \Rightarrow P(n+1)$. \\
\> \> 3. $(\exists k (n = 4k+2)) \Rightarrow P(n+1)$. \\
\> \> 4. $(\exists k (n = 4k+3)) \Rightarrow P(n+1)$. \\
\> \> 5. QED 
      \> \> \> Cases (these are all the possibilities). \\
\> 4. QED
    \> \> \> \> Implication, UG \\
3. QED                        
\> \> \> \> \> Strong induction 
\end{tabbing}
So now we consider the four cases one at a time. \\
The hardest case is where $n=4k$, which means that $n+1 = 4k+1$. \\
We have to show that Player 2 has a winning strategy in the $n+1$-game.
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
\> \> 1. $(\exists k (n = 4k)) \Rightarrow P(n+1)$. \\
\> \> \> 1. Assume $\exists k (n = 4k)$ \\
\> \> \> 2. Choose $k (n = 4k)$ \\
\> \> \> 3. $k \geq 1$ 
         \> \> Because $n \geq 1$ \\
\> \> \> 4. $P(n+1)$, that is, Player 2 has a winning strategy in the $n+1$-game.\\
\> \> \> \> 1. If Player 1 first removes $1$, then Player 2 has a
winning strategy. \\
\> \> \> \> \> $4k$ remains, use inductive hypothesis. \\
\> \> \> \> 2. If Player 1 first removes $2$, then Player 2 has a
winning strategy. \\
\> \> \> \> \> $4(k-1)+3$ remains, use inductive hypothesis. \\
\> \> \> \> 3. If Player 1 first removes $3$, then Player 2 has a
winning strategy. \\
\> \> \> \> \> $4(k-1)+2$ remains, use inductive hypothesis. \\
\> \> \> \> 4. QED 
            \> Cases \\          
\> \> \> 5. QED 
         \> \> Implication
\end{tabbing}

The next case is where $n = 4k+1$, which means that $n+1 = 4k+2$. \\
Now we must show that Player 1 has a winning strategy in the
$n+1$-game. \\
The other two cases are similar. 
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
\> \> 2. $(\exists k (n = 4k+1)) \Rightarrow P(n+1)$. \\
\> \> \> 1. Assume $\exists k (n = 4k+1)$ \\
\> \> \> 2. Choose $k (n = 4k+1)$ \\
\> \> \> 3. $P(n+1)$, that is, Player 1 has a winning strategy in the
$n+1$-game. \\
\> \> \> \> \> First removes $1$, leaving Player $2$ with $4k+1$.  Use
         inductive hypothesis. \\
\> \> \> 4. QED \\
\> \> 3. $(\exists k (n = 4k+2)) \Rightarrow P(n+1)$. \\
\> \> \> \> \> Similar, first removing $2$. \\
\> \> 4. $(\exists k (n = 4k+3)) \Rightarrow P(n+1)$. \\
\> \> \> \> \> Similar, first removing $3$. \\
\end{tabbing}

\end{document}
