\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{multicol}
\usepackage{latexsym}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\input{preamble.tex}

\begin{document}

\homework{3: Recursion!}{Due Friday, Week 2}

Do \textbf{three} of the \textbf{six} problems below!   Prove all of your claims.  If you've seen some of these problems before, try the ones you have not seen first.


\begin{enumerate}
\item Return to our Tower of Hanoi problem, and add the following second condition: when we transfer disks from peg to peg in our system below, we can never send a disk directly from $A$ to $C$ or vice-versa: in other words, each move must be to or from the middle peg. 
\begin{center}
\includegraphics[width=3.5in]{hanoi1.pdf}
\end{center}
Show that it is still possible to move all of the plates from the left peg to the right peg.  What is the smallest number of moves that are needed to do this?

\item Show that when we run the algorithm that solves problem 1 above, we will actually encounter every single possible way to stack $n$ disks on three poles.

\item  Draw $n$ lines in the plane.  As we noticed in class, this divides the plane up into distinct regions.  Some of these regions are \textbf{unbounded}, meaning they take up an infinite amount of area, while others can be \textbf{bounded}, in that they take up only a finite amount of area.

What is the maximum possible number of bounded regions?

\item Draw $n$ circles with positive radius in the plane.  Again, this divides the plane up into various regions.  What is the maximum number of possible regions that we can create?

 \item Recall from class that $J(n)$ is the Josephus number for $n$.  Define
\begin{align*}
H(n) = J(n+1) - J(n).
\end{align*}
In class, we proved that $J(2n) = 2J(n) - 1$ and that $J(2n+1) = 2J(n) +1$, for $n \geq 1$; consequently, we have
\begin{align*}
 H(2n) &= J(2n+1) - J(2n) \\
&= (2J(n) + 1) - (2(J(n) - 1) \\
&= 2, \textrm{ and}\\
H(2n+1) &= J(2n+2) - J(2n+1) \\
&= (2(J(n+1) - 1) - (2(J(n) + 1)\\
& = 2(J(n+1) - J(n)) - 2 \\
&= 2H(n) - 2.
\end{align*}
Therefore, it would seem possible that we could prove that $H(n) = 2$ for all $n$ by induction; for any even $n$ we have that our claim holds, and for any odd $n$ we can use induction to see that if $H(n) = 2$, then $H(2n+1) = 2 \cdot H(n) - 2 = 2 \cdot 2 - 2 = 2$.

But: this cannot be true, as (for example) $H(7) = J(8) - J(7) = 1 - 7 = -6.$  What's wrong with our proof by induction above?

\item Take $n$ coins $C_1, C_2, \ldots C_n$.  Suppose that for each $k$, the coin $C_k$ has a $\frac{1}{2k+1}$ chance that it comes up heads when flipped, and otherwise comes up tails.

Take each of our coins and flip them.  What are the chances that the total number of heads is odd?  (Hint: set up a recurrence relation for $p_n$, the probability that the number of heads is odd when $n$ coins are flipped.)
\end{enumerate}










\end{document}