\documentstyle[psfig,11pt]{article}


\newcounter{problem}

\newenvironment{problems}{\begin{enumerate}\setcounter{enumi}{\theproblem}}{\setcounter{problem}{\theenumi}\end{enumerate}}
%\newenvironment{problems}{\begin{enumerate}}{\end{enumerate}}

\pagestyle{empty}

\textheight 9.4in
\addtolength{\oddsidemargin}{-0.7in}
\addtolength{\textwidth}{1.2in}
\topmargin -0.3in
\headheight 0.1in
\headsep 0.1in

\begin{document}
{\large
\fbox{\parbox{6.1in}{
\hbox to \hsize{\ \ \ 10 Powerful Ideas  \hfil 
Bruce Maggs}
\vskip 0.1in
\hbox to \hsize{\ \ \ Quiz 1 Review Exercises \hfil Quiz 1: {\bf Monday, February 23, 1998}}
}}}
\vskip 0.1in

% magic for a Postscript figure:
%
%\begin{figure}[h]
%\centerline{\psfig{file=,width=}}
%\caption{}
%\end{figure}
 

% Topics
% - induction
% - asymptotic complexity: $O$, $\omega$, $\theta$
% - Fibonacci numbers and the golden ratio $\Phi$
% - recurrence relations
% - groups
% - counting

Solutions to these problems will be available on the course Web site
by Saturday.

\section*{Dating}

\begin{problems}

\item
Show a set of bisexual dating preferences where there is no possible stable
pairing among the people.

\end{problems}


\section*{Induction}

\begin{problems}
\item Show {\bf by induction} that for all
integer $n\geq 1$, $\phi^n = F_n \phi + F_{n-1}$,
where $\phi$ is the golden ratio and $F_n$ is the $n$th Fibonacci
number.

\item Let's call a positive integer
{\em purple} if it is the sum of consecutive positive integers all of
which are less than itself.  For example, $9 = 2 + 3 + 4$ is a purple
number. Prove ({\bf not} by induction!) that a positive integer is purple if
and only if it is not a power of two. (Remember that the {\em if and
only if} means that you have two statements to prove.)

\item 
A limo is two car lengths long and a car is a single car length
long. Let $T(n)$ be the number of distinct possible ways of parking
cars and limos along a curb that is $n$ car lengths long. Order
matters, but any two cars and any two limos are considered identical.
If the curb is 4 car lengths long, then the distinct possible parking
patterns are LL, LCC, CLC, CCL, and CCCC. Thus, $T(4) = 5$. Derive a
recurrence relation for $T$ that completely determines it, and justify
your answer.

\end{problems}

% asymptotic complexity
\section*{Growth Rates}

\begin{problems}
\item
Prove that big-$O$ is transitive: $f(n)=O(g(n))$ and $g(n)=O(h(n))$ implies
$f(n)=O(h(n))$.

\item
Find the flaw in the following inductive proof:\\
{\bf Prove:} $n^2 = O(n)$ \\
{\bf Base case:} for $n=1$, $1^2 = O(1)$. \\
{\bf Inductive step:} Suppose $(n-1)^2 = O(n-1)$.  
Since $n^2 = O((n-1)^2)$, and $n-1 = O(n)$, then by
transitivity of big-$O$ we have $n^2 = O(n)$.

\item
Show that $\log n! = \Theta (n \log n)$.

\end{problems}

% recurrence relations
\section*{Recurrences}

Find closed form solutions to the following recurrence relations.

\begin{problems}

\item
\begin{eqnarray*}
T(n) & = & T(n-1) + 2T(n-2) \mbox{ for }n > 1 \\
T(1) & = & 1 \\
T(0) & = & 0
\end{eqnarray*}

\item
\begin{eqnarray*}
S(n) & = & S(n-1) + n\mbox{ for }n > 0 \\
S(0) & = & 1
\end{eqnarray*}

\item
\begin{eqnarray*}
T(n) & = & 2 T(n-1) +1 \mbox{ for } n>0\\
T(0) & = & 0
\end{eqnarray*} 

\item
\begin{eqnarray*}
Q(n) & = & {1 + Q(n-1) \over Q(n-2)} \mbox{ for }n>1 \\
Q(1) & = & \beta \\
Q(0) & = & \alpha
\end{eqnarray*}

\item
Every node of a ternary tree has $3$ children (except for the leaf
nodes, which have no children).  If a one-level ternary tree contains
1 node, give a closed form solution for the number of nodes in an
$n$-level ternary tree have.

\end{problems}

% groups
\section*{Groups}

\begin{problems}

\item
List all subgroups of $Z_4=\{0,1,2,3\}$ with the operation $+$ mod $4$.  Now
list all subsets of $\{0,1,2,3\}$. Does the null set (denoted
$\emptyset$) belong to either list?

\item 
The group $S_n$, called the {\em symmetric group}, is the group of
permutations of $n$ elements, using composition as its operation.  For
instance, $\{1,4,3,2\}$ is one member of $S_4$.
\begin{enumerate}
\item Assuming $S_n$ is indeed a group, what would its identity element be?
\item What is $\mid S_n \mid$, the size of the group?
\item Prove that $S_n$ is indeed a group for any $n$.
\item Does $S_n$ have any subgroups?
\end{enumerate}

\item
Given any group $(G,\star)$ and any non-empty subset $H$ of $G$ such
that $a,b \in H$ implies $a^{-1} \star b \in H$, show that $(H,\star)$
is a subgroup.


\end{problems}

% counting and probability
\section*{Counting}

\begin{problems}

\item
Give a closed form solution to $3+6+9+\ldots + 3n$.

\item
What is the formula for the power series expansion of ${(x+y)}^n$?

\item
How many subsets can be formed from the elements of an $n$ element set?

\item
How many r-bit binary sequences have an odd number of 1s?

\item
How many ways are there to rearrange the letters in the word EFFORTLESS?

\item
Show that when $n \geq m$
\[{m \choose m}+{m+1 \choose m}+\cdots+{n \choose m} = {n+1 \choose m+1}\]

\item
What is the coefficient of $a^4b^6$ in $(a^2+b)^8$?

\item
How many integer solutions to the following equations?
\[ X_1 + X_2 + X_3 + X_4 + X_5 = 50,\ \  X_i \geq 0  \]

\item
An $n$-input, $m$-output boolean function is a function from ${0,1}^n$
to ${0,1}^m$.  (Think of a circuit with $n$ inputs and $m$ outputs.)
How many $n$-input, 1-output boolean functions are there?  How many
$n$-input, $m$-output boolean functions are there?

\item
How many ways can three distinct numbers be chosen from the set
${1,2,\ldots,100}$ such that their sum is even?

\item
How many ways are there to seat 5 children in a row of 12 chairs?

\item
A {\em chord} is a line segment connecting two points on a circle.
Suppose you are given $n$ points on a circle such that no three of
the chords connecting them intersect in the same point.  Into how 
many line segments are the chords divided by their intersections?

\item
How many ways can 3 exams be scheduled in a 5-day period such that no
two exams are held the same day?

\item
A palindrome is a word that reads the same forwards and backwards.
How many seven-letter palindromes can be made from the English
alphabet?

\item
Show that the product of any $k$ consecutive integers is divisible by
$k!$

\item
How many ways are there to place $r$ red balls and $w$ white balls
into $n$ distinct boxes such that each box contains at least one ball
of each color?

\item
Imagine a town with East-West streets numbered 1 through n, and
North-South avenues numbered 1 through m. A taxi cab picks up a passenger at the
corner of 1st street and 1st avenue. The passenger wishes to be delivered to
nth street and mth avenue. It is quite clear that the passenger will be
angry if the cab chooses a route longer than $(n-1)+(m-1)$ blocks, so we won't
allow the cabby to take a route longer than this. In other words, the cabby
must always be increasing his street number or his avenue number.
Suppose that there is an accident at ith street and
jth avenue. How many routes can the cabby take that avoid the
intersection with the accident?

\end{problems}

% hard problems
\section*{Toughies}

\begin{problems}

\item
Suppose there are $2n$ people in a circle.  The first $n$ people are
``good guys,'' and the last $n$ are ``bad guys.''  Show that there is
always an integer $m$ (depending on $n$) such that, if we go around
the circle executing every $m$th person, all the bad guys are executed
first.  (For example, when $n=3$, we can take $m=5$; when $n=4$ we can
take $m=30$.)

\end{problems}

\section*{More Practice}

These books are all available in the Engineering \& Science Library in
Wean Hall.

{\small
\begin{enumerate}
\item
{\em Elements of Discrete Mathematics}, by C.L. Liu.

\item
{\em Discrete Mathematics}, by N.L. Biggs.

\item
{\em Combinatorics: An Invitation}, by H.J. Straight.

\item
{\em Concrete Mathematics: a foundation for computer science}, by
R. Graham, D. Knuth, O. Patashnik.
\end{enumerate}

\end{document}

