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

\usepackage{tikz}
\newcommand*\circled[1]{\tikz[baseline=(char.base)]{
            \node[shape=circle,draw,inner sep=2pt] (char) {#1};}}
\input{preamble.tex}

\begin{document}

\homework{1: Basic Counting}{Due Friday, Week 2}

\section{Homework Problems}
Solve the following five problems!
\begin{enumerate}
\item 
Take the Towers of Hanoi problem from class before:
\begin{itemize}
\item Start with $3$ rods $A,B,C$.
\item On one rod, place $n$ disks with radii $1, 2, \ldots n$, so that the disk with radius $n$ is on the bottom, the disk with radius $n-1$ is on top of that disk, and so on/so forth.
\item Your goal is to move all of the disks from the far-left rod $A$ to the far-right rod $C$, subject to the following rules:
\begin{itemize}
\item You can move only one disk at a time.
\item Each move consists of taking the top disk off of some rod and placing it on another rod.
\item You cannot place a disk $D_i$  on top of any other disk $D_j$ with radius smaller than $D_i$.
\end{itemize}
\end{itemize}
Add in the following \textbf{new} rule, which was not present in our class discussion:
\begin{itemize}
\item When moving a disk, you may only move it to an adjacent rod.  That is, you cannot move a disk directly from $A$ to $C$ or vice-versa:\ the only legal moves are $A \leftrightarrow B$ or $B \leftrightarrow C$.
\end{itemize}
\begin{enumerate}


\item 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 Under the same restrictions, suppose that you want to move all of the plates from the left peg to the right peg in the \textbf{largest} number of moves possible without repeating any previously-visited configuration.  What is this largest possible number of moves?
\end{enumerate}
\item The Josephus problem has a rather violent history behind it.  Per Wikipedia:
\begin{quote}
The problem is named after Flavius Josephus, a Jewish historian living in the 1st century. According to Josephus' account of the siege of Yodfat, he and his 40 soldiers were trapped in a cave, the exit of which was blocked by Romans. They chose suicide over capture and decided that they would form a circle and start killing themselves using a step of three. Josephus states that by luck or possibly by the hand of God, he and another man remained the last and gave up to the Romans.
\end{quote}
In class, we studied a variant on this problem, where there were $n$ elements in a circle and we eliminated every second element until only one was left (the ``survivor,'' or Josephus's number.)  The history of this problem motivates a natural question; given that Josephus and the other man both survived, we would want to know a formula for the second-to-last element eliminated as well!  Call this value $I(n)$; to give a few small values, you can easily check that $I(2) = 2, I(3) = 1,$,  $I(4) = 3,$ and $I(5) = 5$.

Create a closed formula for $I(n)$.

\item Prove that the Fibonacci sequence $\{f_n\}_{n=0}^\infty$ as defined in class satisfies the following recurrence relation:
\begin{align*}
f_{2n+1} = f_{n+1}^2 + f_n^2.
\end{align*}

(Hint: you may want to prove the more general formula $f_{m+n+1} = f_{m+1}f_{n+1} + f_mf_n$ instead!)

\item Prove that the Fibonacci sequence $\{f_n\}_{n=0}^\infty$ as defined in class satisfies the following identity:
\begin{align*}
f_n = \sum_{k=0}^{\lfloor\frac{n-1}{2}\rfloor} \tbinom {n-k-1} k
\end{align*}

(Hint: in the lecture notes online, you can find a proof of the following useful combinatorial fact: $ \binom{n-1}{k} + \binom{n-1}{k-1} = \binom{n}{k}$.  You may find this observation useful here!)

\item Find simple, compact expressions (i.e. without indexed sums or ellipses or other such things) for the following two expressions:
\begin{enumerate}
\item $\displaystyle \sum_{k=1}^n k \cdot \binom{n}{k}$.
\item $\displaystyle \sum_{k=1}^n \frac{1}{k+1} \cdot \binom{n}{k}$.
\end{enumerate}
\end{enumerate}



\section{Extra Credit}
Solve the following problem if you're curious!
\begin{enumerate}
\item Suppose that the soldiers in the Josephus problem are suspicious of Josephus, and make him stand at the top of the circle; i.e. he cannot choose where he stands in the circle. In exchange, however, they let him pick the interval that they choose people by:\ i.e.\ Josephus can choose to eliminate every second person, or every third person, or every $k$-th person for any $k \geq 2$.

Can Josephus still survive?
\item As above, but Josephus and all of the soldiers are now cats, each with $d$ lives for some fixed natural number $d$ that is the same for everyone.  (I.e. when people are eliminated in the circle, they have a set number of lives, and stay in the circle as long as they each have at least one life.)

Can Josephus still survive?
\end{enumerate}

\end{document}