\documentclass[12pt]{article}
\textwidth = 6.7 in
\textheight = 9.2 in
\oddsidemargin = 0.0 in
\evensidemargin = 0.0 in
\topmargin = 0.2 in
\headheight = 0.0 in
\headsep = 0.0 in
\parskip = 0.2in
\parindent = 0.0in

\usepackage{amsmath,amssymb,enumerate,gastex}
%\def\rmdefault{bch} % Use Charter for main text font.

% =========================================================
\begin{document}

\begin{center}
{\LARGE
\textbf{CS 173: Discrete Structures, Fall 2009}
\\
\textbf{Homework 9}
\\[1ex]}
\end{center}

This homework contains 4 problems worth a total of 50 points.
It is due on Friday, November 13 at noon.   Put your homework in
the appropriate dropbox in the Siebel basement.


\begin{enumerate}

%----------------------------------------------------------------------
\item 
\textbf{Counting [18 points]}

Solve the following counting problems, providing brief explanations and/or
work to justify your answers.   
You do not need to multiply out factorials or trying to simplify formulas
to reach your final answer. 
For example, $\frac{10!}{6!}$ would be fine as an answer. 

\begin{enumerate}
\item Central Plains Pizza offers three choices for the diameter,
two choices for crust thickness, and 12 choices of topping.   Suppose
that you limit yourself to 5 or fewer toppings.   How many different
pizzas can you construct?

\item How many distinct strings can you make out of the characters
in the word ``potato-soup''?   (Include the hyphen as a character.)

\item You need to form a battle group of 11 made up of orcs, elves, and
goblins.   In how many ways can you choose the composition of your battle group?

\item You need to form a battle group consisting of an orc, an elf, and
a goblin whose total strength is 12.   
The strength of each creature is 
an integer between 1 and 10 and the strength of the group is the sum of the
individual strengths.  In how many ways can you construct your battle group?

\item You are out in the middle of the cornfields, where the (dirt) roads
all run north-south or east-west, evenly spaced at one road per mile.   
If you start
at a road intersection and wish to get to the intersection 5 miles to the
north and 7 miles east, how many different routes could you take?

\item Your latest cheapo cell phone keyboard only includes the uppercase
alphabet (26 characters total).  How many 12-character strings can you
type that start with ST and contain no more than three T's?

\end{enumerate}


%----------------------------------------------------------------------
\item 
\textbf{Combinatorial formula [8 points]}

Use induction and Pascal's identity to prove the following formula
holds for any positive integers $s$ and $n$:

$$\sum_{k=0}^{n} \binom{s+k-1}{k} = \binom{s+n}{n}$$

\newpage
%----------------------------------------------------------------------
\item 
\textbf{Structural induction [10 points]}

For any real numbers $a$ and $b$,
the set $S_{a,b}$ is defined recursively by

\begin{enumerate}[1:]
\item $(4,3) \in S_{a,b}$
\item If $(x,y) \in S_{a,b}$, then $(-x,-y) \in S_{a,b}$
\item If $(x,y) \in S_{a,b}$, then $(ax-by,ay+bx) \in S_{a,b}$
\end{enumerate}

Suppose that $a$ and $b$ are real numbers such that $a^2 + b^2 = 1$.   

\begin{enumerate}
\item Use structural induction to prove that
$x^2 + y^2 = 5$ for any element $(x,y)$ in $S$.
\item What familiar geometric figure is $S$ a subset of?
\item For some choices of $a$ and $b$, $S$ is a finite set.
What constraints must $a$ and $b$ satisfy for this to be true?
Informally explain why your answer is right.  
\end{enumerate}


%----------------------------------------------------------------------
\item 
\textbf{Tree induction [14 points]}

 
A binomial tree of order $k$ is defined recursively as follows:

\begin{itemize}
\item A single root node is a binomial tree of order 0.
\item A binomial tree of order $k$ consists of two 
binomial trees of order $k-1$, with the root of the first connected
as the rightmost child of the root of the second.
\end{itemize}

The following picture shows the binomial trees of order 1, 2, and 3.
The labels on the nodes show how the larger tree is divided into two
lower-order subtrees. 

    \begin{picture}(180,60)(0,-60)
        \gasset{AHnb=0}
        \node(nyr)(20.0,-10.0){A}
        \node(ny1)(20.0,-20.0){B}

        \node(nxr)(40.0,-10.0){A}
        \node(nx1)(40.0,-20.0){A}
        \node(nx0)(60.0,-20.0){B}
        \node(nx2)(60.0,-30.0){B}

        \node(nr)(80.0,-10.0){A}
        \node(n1)(80.0,-20.0){A}
        \node(n0)(100.0,-20.0){A}
        \node(n2)(100.0,-30.0){A}
        \node(n3)(120.0,-20.0){B}
        \node(n4)(120.0,-30.0){B}
        \node(n5)(140.0,-30.0){B}
        \node(n6)(140.0,-40.0){B}


    \drawedge(nyr,ny1){}

    \drawedge(nxr,nx1){}
    \drawedge(nxr,nx0){}
    \drawedge(nx0,nx2){}

    \drawedge(nr,n1){}
    \drawedge(nr,n0){}
    \drawedge(n0,n2){}
    \drawedge(nr,n3){}
    \drawedge(n3,n4){}
    \drawedge(n3,n5){}
    \drawedge(n5,n6){}

    \end{picture}
`
\begin{enumerate}
\item Use induction on the order of the tree 
to prove that a binomial tree of order $k$ has $2^k$ nodes.
\item Use induction (again on the order of the tree)
to prove that a binomial tree of order $k$ has exactly
$\binom{k}{i}$ nodes at level $i$.  
Hint:  use induction on the order of the
tree.   For some randomly chosen level $i$, sum the numbers of nodes in the
two trees.
\end{enumerate}

Warning: in your inductive step you {\bf must} divide the larger tree into
smaller subtrees by taking it apart at the root.   Do not try to graft things
onto the bottom of a small tree to make a big one.   

\end{enumerate}

\end{document}


