\documentclass[11pt]{article}
\usepackage{jeffe,handout,multicol,tikz,kgm}

\newcommand{\kgmcomment}[1]{}

\begin{document}
\headers{Math571}{Homework 3}{Due February 25, 2013}

%\makeatletter
%\def\@oddfoot{\hfill \tikz \node[draw] {over} ; }
%\makeatother

\makeatletter
\def\@oddfoot{}
\makeatother

\noindent
\textbf{Directions:} Solve 5 of the following 6 problems.  Students seeking higher than 500 level credit must complete all 6 problems.  See the course syllabus and the Homework Webpage on the course website for general directions and guidelines that apply to all homeworks.

\begin{enumerate}

\item{}[CM 1.3.20] A \emph{cyclic shift} of a $p$-tuple $(x_0,\ldots,x_{p-1})$ is a $p$-tuple of the form $(x_{k},x_{k+1},\ldots,x_{k+p-1})$, where all indices are taken modulo $p$.  For all non-negative integers $a$, show that $p$ divides $a^p - a$ using cyclic shifts when $p$ is prime.  (Comment: this yields a combinatorial proof of Fermat's Little Theorem.)

\item{}[CM 1.3.\{27,30\}]
Using direct bijections, prove that the following equal the number of ballot lists of length $2n$.  (Of course, these bijections show that the number of each is the $n$th Catalan number $\frac{1}{n+1}\binom{2n}{n}$.)
\begin{enumerate}
\item The number of ordered trees with $n$ edges.  (An ordered tree is a rooted tree in which the children of each vertex are ordered.)
\item The number of ways to pair $2n$ points on a circle with noncrossing chords.
\end{enumerate}
\vspace{-0.5cm}
\begin{center}
\setlength{\tabcolsep}{0.6cm}
\begin{tabular}{c|c}
\begin{tikzpicture}[yscale=0.5,xscale=0.75]
	\begin{scope}[every node/.style={vertex}]
		\begin{scope}[shift={(0.5,1)}]
			\foreach \y in {1, ..., 4}
			{
				\node (A\y) at (0,-\y)  {} ;
			}

			\draw (A1) -- (A2) -- (A3) -- (A4) ;
		\end{scope}

		\begin{scope}[shift={(2,0)}]
			\foreach \n/\x/\y in {1/0/0, 2/0/-1, 3/-0.5/-2, 4/0.5/-2}
			{
				\node (B\n) at (\x,\y) {} ;
			}
			\draw (B1) -- (B2) -- (B3) (B2) -- (B4) ;
		\end{scope}

		\foreach \scale/\shift/\name in {1/4/C, -1/6/D}
		{
			\begin{scope}[shift={(\shift,0)},xscale=\scale]
				\foreach \n/\x/\y in {1/0/0, 2/-0.5/-1, 3/0.5/-1, 4/-0.5/-2}
				{
					\node (\name\n) at (\x,\y) {} ;
				}
				\draw (\name1) -- (\name2) -- (\name4) (\name1) -- (\name3) ;
			\end{scope}
		}

		\begin{scope}[shift={(8,0)}]
			\foreach \n/\x/\y in {1/0/0, 2/-0.5/-1, 3/0/-1, 4/0.5/-1}
			{
				\node (E\n) at (\x,\y) {} ;
			}
			\draw (E1) -- (E2) (E1) -- (E3) (E1) -- (E4) ;
		\end{scope}
	\end{scope}
\end{tikzpicture}
 
&

\begin{tikzpicture}[scale=0.40,baseline=-1cm]
	\foreach \n/\a/\b/\c/\d/\e/\f in {1/1/2/3/4/5/6,
					  2/2/3/4/5/6/1,
					  3/1/4/2/3/5/6,
					  4/2/5/3/4/1/6,
					  5/3/6/4/5/1/2}
	{
		\pgfmathparse{2*\n}
		\begin{scope}[every node/.style={vertex}, xshift=4*\n cm]
			\foreach \i in {1, ..., 6}
			{
				\node (V\n\i) at (60*\i:1cm) {} ;
			}
			
			\draw (V\n\a) -- (V\n\b) ;
			\draw (V\n\c) -- (V\n\d) ;
			\draw (V\n\e) -- (V\n\f) ;
		\end{scope}
	}
\end{tikzpicture}\\
(a) Ordered trees with $3$ edges &
(b) Noncrossing pairings on $6$ points\\
\end{tabular}
\end{center}

\item{}[CM 2.1.18] Let $a_n$ be the number of compositions of $n$ using only odd parts.  Let $b_n$ be the number of compositions of $n$ using parts that are at least $2$.  Use recurrences to determine $\left<a\right>$ and $\left<b\right>$.

\newcommand{\FF}{\hat F}
\item{}[CM 2.1.19] Give inductive \emph{and} combinatorial proofs that $\FF_n^2 = \FF_{n-1}\FF_{n+1} + (-1)^n$ for $n\ge 1$.  Manipulate the identity to explain why Lewis Carroll's ``proof'' below that $64 = 65$ (and larger analogues) seems reasonable.
\begin{center}
\begin{tikzpicture}[scale=0.33]
	\begin{scope}[shift={(-10,-4)}]
		\draw (0,0) grid (8,8) ;

		\begin{scope}[every path/.style={ultra thick}]
			\draw (0,0) rectangle (8,8) ;
			\draw (5,0) -- (5,8) (5,0) -- (8,8) (0,5) -- (5,3) ;
		\end{scope}
	\end{scope}

	\begin{scope}[shift={(2,-2.5)}]
		\draw (0,0) grid (13,5) ;

		\begin{scope}[every path/.style={ultra thick}]
			\draw (0,0) rectangle (13,5) ;
			\draw (0,0) -- (13,5) (8,0) -- (8,3) (5,5) -- (5,2) ;
		\end{scope}
	\end{scope}
\end{tikzpicture}
\end{center}

\item{}[CM 2.1.58] Let $a_n$ be the number of domino tilings of a $(2\times n)$-rectangle, let $b_n$ be the number of domino tilings of a $(3\times 2n)$-rectangle, and let $c_n$ be the number of domino tilings of a $(4\times n)$-rectangle.  Obtain a bounded order recurrences for $\left<a\right>$, $\left<b\right>$, and $\left<c\right>$.

\item{}[CM 2.1.65] The gambler and a casino play a game with $n$ blue balls and $n+1$ red balls.  The gambler starts with one unit of money (infinitely divisible).  At each round, the gambler bets part of his money (possibly 0), and the casino selects a ball (knowing the amount of the gambler's bet).  If the ball is blue, then the gambler loses the bet; if it is red, then the gambler gains that amount.  The selected ball is discarded.  The gambler wants to maximize his money after all the balls are used, while the casino wants to minimize that.  If both play optimally, how much does the gambler have at the end?  (Hint: Try small cases.  Solve a more general problem.)
\end{enumerate}
\end{document}
