Problem 1 (Based on ``An Impossible Counting Problem'' from ln11.pdf)

Let $a_n$ be the number of ways to fill a box with $n$ doughnuts subject to
the following constraints: 

\begin{itemize}
\item The number of glazed doughnuts must be odd.
\item The number of chocolate doughtnuts must be a multiple of 4.
\item The number of plain doughnuts is 0 or 2.
\item The number of sugar doughnuts is at most 1.
\end{itemize}

(a)  Write a generating function for each of the four doughnut types:

$G(x) = $

$C(x) = $

$P(x) = $

$S(x) = $

(b)  Determine a closed formula for $a_n$.  Express your answer in the form
$\lceil f(n) \rceil$ for some simple function $f(n)$.  

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

Solution Sketch:

(a)

$G(x) = \frac{x}{1-x^2}$

$C(x) = \frac{1}{1-x^4}$

$P(x) = 1+x^2$

$S(x) = 1+x$

(b) We have

\begin{eqnarray*}
A(x) &=& \frac{x}{(1+x)(1-x)^2} \\
     &=& \frac{-1/4}{1+x} 
         + \frac{-1/4}{1-x}
         + \frac{1/2}{(1-x)^2}
\end{eqnarray*}

by partial fractions.  This gives $a_n = \lceil n/2 \rceil$.

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

Problem 2

Consider the following random walk on $\mathbb{Z}$:  
start at the origin (0), and at each step, increase by 1 with probability
1/2 and decrease by 1 with probability 1/2.  

Prove that the random walk will reach a point $x$ with $|x| \geq n$ with
probability 1.  

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

Solution 

The probability of a sequence with $2n$ consecutive ``up''s is finite.  So
the probability it never happens is 0.  (sorry for the imprecision)

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