\documentclass[10pt]{article}
\usepackage{fullpage}
\usepackage{amsmath}
\usepackage{graphics}
\usepackage{psfig}

\input{../handouts/macros-course}

\setlength{\parindent}{0em}
\setlength{\parskip}{1em}

%\newcommand{\problem}{\newpage\textbf{Problem.\ }}
%\newcommand{\bparts}{}
%\newcommand{\eparts}{}
%\newcommand{\ppart}{\textbf{Part.\ }}
%\newcommand{\solution}[1]{\textbf{Solution.\ } #1}
\newcommand{\ksource}[1]{\textsc{Source: #1}\par}
\newcommand{\ktopics}[1]{\textbf{Topics: #1}\par}
\newcommand{\kparen}[1]{\ensuremath{\left( #1 \right)}}
\newcommand{\kbrack}[1]{\ensuremath{\left[ #1 \right]}}
%\newcommand{\floor}[1]{\ensuremath{\left\lfloor #1\right\rfloor}}
\newcommand{\kth}{\ensuremath{^{\textrm{th}}}}
\newcommand{\pts}[1]{\ensuremath{[#1\mathrm{\ points}]}}

\renewcommand{\hint}[1]{\par\textbf{Hint:} #1}

%\newcommand{\set}[1]{\ensuremath{\{#1\}}}

\newcommand{\kproblem}[1]{\newpage [#1]\problem}

\newcommand{\mathify}[1]{\ifmmode{#1}\else\mbox{$#1$}\fi}
\newcommand{\mquote}[1]{\mathify{\textrm{``$#1$''}}}
\newcommand{\mdash}{\mathify{\textrm{-}}}
\newcommand{\where}{{\ \mid \ }}
\newcommand{\size}[1]{\mathify{\left| #1 \right|}}
\newcommand{\equivalent}{\mathify{\ \Longleftrightarrow \ }}
\newcommand{\ifandonlyif}{\equivalent}
\renewcommand{\prob}[1]{\mathify{\textrm{Pr}\left[\, #1 \,\right]}}
\newcommand{\compliment}[1]{\overline{#1}}
\newcommand{\Ex}{\text{Ex}}




\begin{document}

\askaboutsolutions

\begin{problems}

% Logic
\kproblem{logic1}
\pts{12}
\ksource{victor}
\ktopics{Logic}
Transcribe the following arguments into logic, 
and for each argument, 
show that it is valid, 
or give a counterexample. 
State clearly what your propositions and/or predicates are.

\bparts

\ppart
\pts{3}
Either Jane or Bob ate the cheesecake. 
Neither Bob nor David drank the soda. 
If Bob ate the cheesecake, he also drank the soda. 
So Jane ate the cheesecake. 

\ppart
\pts{3}
Unless we get up early, 
we won't make it to the game on time. 
If we go to sleep early then we will get up early. 
Therefore, if we go to sleep, we will get to the game on time. 

\ppart
\pts{3}
Suppose all circles are round, 
no squares are round, 
and some triangles are round. 
Then some circles are triangles. 

\eparts

%% More logic: proofs of logical equivalence
\kproblem{logic2}
\ksource{victor}
\ktopics{Logic}
Prove which of the following statements imply which other statements. 
(This includes showing that a statement does not imply another.)
\begin{enumerate}

\item
$\forall x (P(x) \implies Q(x))$ 

\item
$\exists x Q(x) \implies \forall x P(x)$ 

\item
$\exists x Q(x) \implies \exists x P(x)$ 

\item
$\exists x (Q(x) \implies P(x))$ 

\item
$\forall x \neg P(x) \lor \exists x Q(x)$ 

\item 
$\exists x P(x) \lor \forall x \neg Q(x)$ 

\end{enumerate}


%%% induction %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\kproblem{induction1}\ksource{David Gries' book}\ktopics{Induction, trees} A full
binary tree is a binary tree in which each node has either 0 children
or 2 children.  Prove \textit{by induction} that all non-empty full
binary trees have an odd number of nodes.

\solution{Base case: 1 node, odd.
  
  Induction: Assume all full binary trees of height $\leq n$ have an
  odd number of nodes.  Now, consider a full binary tree of height
  $n+1$.  Since the height is greater than $0$, the root node must
  have two children, $A$ and $B$, which must themselves be full binary
  trees of height $\leq n$.  The whole tree has $1+|A|+|B|$ nodes
  which, by the induction hypothesis, is odd+odd+odd=odd.  This proves
  the theorem.}


%%%%%%%%%% PROBLEM %%%%%%%%%
% Source: pset3/spring99sol.tex
% Topic: Graphs, Recursive Definitions

\kproblem{induction2} 
\pts{12}
\ksource{s99 ps3}
\ktopics{Induction, Graphs, Recursive Definitions}
This problem concerns Hamiltonian circuits
in $n$-cubes.  A {\em Hamiltonian circuit} in a graph is a circuit
traversing every vertex in the graph exactly once.  The $n$-cube is
defined on page 448 of Rosen (p. 441 in ed. 3).  (Rosen also uses the
name $Q_n$ for an $n$-cube.)  However, the following recursive
definition of an $n$-cube is equivalent to the one given in Rosen, but
may simplify your solutions.  A 0-cube is a single vertex.  An
$(n+1)$-cube consists of two $n$-cubes with corresponding vertices
joined by edges.  For example, a cube is two squares with
corresponding corners joined.

\begin{problemparts}
\ppart Draw a 4-cube.
\pts{2}

\solution{
\bigskip
%\centerline{\resizebox{!}{2.0in}{\includegraphics{fourcube.eps}}}
\bigskip
}

\ppart In your drawing, highlight a Hamiltonian circuit.
\pts{2}

\solution{
The dotted edges in the diagram above form a Hamiltonian
circuit.
}

\ppart Use induction on $n$ to prove that an $n$-cube has a
Hamiltonian circuit for all $n \geq 2$.
\pts{8}

\solution{
The proof is by induction.  Let $P(n)$ be the proposition
that an $n$-cube has a Hamiltonian circuit.  In the base case, $P(2)$
is true, because a 2-cube is itself a cycle.

In the inductive step, assume that an $n$-cube has a Hamiltonian
circuit to prove that an $(n+1)$-cube has a Hamiltonian circuit.
Regard an $(n+1)$-cube as two $n$-cubes with corresponding vertices
joined.  The first $n$-cube has a Hamiltonian circuit $H$ by
induction, and there is a matching Hamiltonian circuit $H'$ in the
second $n$-cube.

Take an edge $(u, v) \in H$ and the corresponding edge $(u', v') \in
H'$.  We can construct a Hamiltonian circuit in the $(n+1)$-cube by
starting at vertex $u$, traversing the circuit $H$ all through the first
$n$-cube until reaching vertex $v$, crossing the edge $(v, v')$,
traversing the circuit $H'$ all through the second $n$-cube until
reaching vertex $u'$, and then crossing the edge $(u', u)$.
}
\end{problemparts}


%%%%%%%%%% PROBLEM %%%%%%%%%
% Source: pset3/spring97sol.tex
% Topic: Structural Induction, Recursive Definition (Binary Trees)

\kproblem{induction3}
\ksource{s97 ps3}
\ktopics{Structural Induction, Recursive Definition (Binary Trees)}
Recall that we defined binary trees in class as either 
\begin{itemize}
\item A {\em node} with no children.
\item A node with a left child that is a binary tree, and no right child.
\item A node with a right child that is a binary tree, and no left child.
\item A node with left and right binary-tree children.
\end{itemize}
Consider the following recursive definition of the {\em height} of a
binary tree:
\begin{itemize}
\item The height of a node with no children is 0
\item The height of a tree on a node with children is one more than the maximum
  of its children's heights.
\end{itemize}
Prove that a tree of height $h$ contains at most $2^{h+1}-1$ nodes.

\solution{
The proof is by structural induction on the definition of binary tree.

{\sc Base Case:}
A tree consisting of one node with no children 
has height $h=0$.  So $1\leq 2^{h+1}-1 = 1$. 

{\sc Inductive Steps:} We have three cases 
corresponding to the three cases of the definition:
\begin{itemize}
 \item If the tree $T$ is a node with a left child but no right child,
  let $L$ be the left child binary tree and let $h$ be its height.
  By inductive hypothesis, the tree $L$ has at most 
  $2^{h+1}-1$ nodes. 
  The height of tree $T$ is $h+1$, and the number of nodes in $T$
  is at most $1+2^{h+1}-1 = 2^{h+1} <2^{h+2}-1$.
 \item If the tree $T$ is a node with a right child but no left child,
  it is analogous to the previous case.
 \item If the tree $T$ is a node with both a left and right 
  child $L$ and $R$, then let $h_1$ and $h_2$ be the 
  heights of the trees $L$ and $R$ respectively.
  Let also $h$ be the maximum of $h_1$ and $h_2$.
  By inductive hypothesis the trees $L$ and $R$
  have at most $2^{h_1+1}-1\leq 2^{h+1}-1$
  and $2^{h_2+1}-1 \leq 2^{h+1}-1$ nodes.
  So, the number of nodes in $T$ is at most 
  $1+(2^{h+1}-1)+(2^{h+1}-1) = 2^{h+2}-1 = 2^{h'+1}-1$ nodes, 
  where $h' = h+1$ is the height of $T$.
\end{itemize}
}

%%%%%%%%%% PROBLEM %%%%%%%%%
% Source: pset3/fall94.tex
% Topic: Structural Induction (Binary Tree)

\kproblem{induction4}
\ksource{f94 ps3}
\ktopics{Structural Induction (Binary Tree)}
Let us associate a ``weight'' $w(x)=2^{-d}$ with each leaf of
depth $d$ in a binary tree~$T$.  Use the structural induction
definition of a binary tree {\bf on page 94 of Handout clrchap5} to
prove the \defn{Kraft Inequality}: $\sum_x w(x) \leq 1$, where the sum
is taken over all leaves $x$ in~$T$.  (Beware of ``build-up error''
[MR, p.~173].)

\solution{
{\bf not done yet.}
}

%%%%%%%%%% PROBLEM %%%%%%%%%
% Source: ? pset3/spring97.tex
% Topic: Fibonnacci Numbers, Strong Induction

\kproblem{induction5}
\pts{10}
\ksource{s97 ps3}
\ktopics{Fibonnacci Numbers, Strong Induction}
Show that the Fibonnacci number $f_n$ satisfy $f_n \leq 2^n$
  using strong induction.

[[[Nancy additions:
I suggest this problem as a candidate for a structured proof problem, where
we provide the proof and they fill in the reasons, line by line (or, some
selected reasons).

E.g.:
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXX\=    \kill
Let $P(n) = F_n \leq 2^n$
Prove: $\forall n \geq 0 (P(n))$\\
1. (Base) $P(0)$
\> \> \> \> \>  $F_0 = 0 \leq 2^0$ \\ %[[[students can do this]]]
2. (Base) $P(1)$ 
\> \> \> \> \>  $F_1 = 1 \leq 2^1$ \\ %[[[students]]]
3. (Inductive step) $\forall n \geq 1 [(\forall  i, 0 \leq i \leq n (P(i))) \Rightarrow P(n+1)]$\\
\> 1. Fix $n \geq 1$ \\
\> 2. $(\forall  i, 0 \leq i \leq n (P(i))) \Rightarrow P(n+1)$ \\
\> \> 1. Assume $\forall  i, 0 \leq i \leq n (P(i))$ \\
\> \> 2. $P(n+1)$
\> \> \> 1. $F_n \leq 2^n$
         \> \> Inductive hypothesis 3.2.1 \\ %[[[students]]]
\> \> \> 2. $F_{n-1} \leq 2^{n-1}$
         \> \> Inductive hypothesis 3.2.1 \\ %[[[students]]]
\> \> \> 3. $F_{n+1} = F_n + F_{n-1}$
         \> \> Definition of Fibonacci numbers \\ %[[[students]]]
\> \> \> 4. $F_{n+1}\leq 2^n + 2^{n-1}$ 
         \> \> Plug the inequalities into the equation \\ %[[[students]]]
\> \> \> 5. $F_{n+1} \leq 2^{n+1}$ \\
\> \> \> \> 1. $2^{n-1} \leq 2^n$
            \> Algebra \\ 
\> \> \> \> 2. $2^n + 2^{n-1} \leq 2^{n+1}$
            \> Algebra \\ 
\> \> \> \> 3. QED 
            \> Algebra (3.3.4 and 3.3.5.2) \\ %[[[students]]]
\> \> \> 6. QED
         \> \> Definition of $P(n+1)$ \\ 
\> \> 3. QED
       \> \> \> Implication \\ %[[[students]]]
\> 3. QED
    \> \> \> \> UG \\ %[[[students]]]
4. QED
\> \> \> \> \> Strong induction %[[[students]]]
\end{tabbing}
]]]

\solution{
{\bf not done yet.}
}


%%%%%%%%%% PROBLEM %%%%%%%%%
% Source: pset3/spring97.tex
% Topic: Fibonnacci Numbers, Well Ordering, Strong Induction

\kproblem{induction6}
\ksource{s97 ps3}
\ktopics{Fibonnacci Numbers, Well Ordering, Strong Induction}
What quantities of money can be formed from just dimes and
quarters? \newline
\solution{
{\bf: Answer A.}
The answer is $10$ and all multiples of five greater then 
or equal to $20$.

We can prove this by strong induction on $n$ where $n=5k$ for $k=2$ and 
$k \geq 4$.

{\bf: Answer B.}
  First of all notice that if we can make $n$ cents using dimes 
  and quarters then $n=10a+25b = 5(2a+5b)$ for some $a$ and $b$,
  and therefore $n$ must be a multiple of $5$.
  We can make $10$ cents using one dime, and we cannot make 
  neither $5$ nor $15$ cents.
  We claim that we can make any other quantities $n$ 
  such that $n\geq 20$ and $5|n$.
  In other words, we can make $20+5k$ cents for all $k\geq 0$.
  We will prove this statement first by strong induction 
  and then by well-ordering.
}
\begin{problemparts}
\ppart Prove by strong induction that these and no other
quantities can be formed.  
\newline
\solution{
{\bf: Answer A.}
{\sc Base Cases:} As  base cases we take all $n \leq 25$.
Clearly, if $n \leq 25$ then  we  can make $10$ from one dime,
$20$ from two dimes, and $25$ from one quarter.

{\sc Inductive Step:} Let $n\geq 25$ and assume that for 
all $25<m<n$ we can make $m$ cents out of dimes and quarters.
Show that we can make $n$ cents out of dimes and quarters.

If $n > 25$ then we know that $n-10 > 15$ and by the base cases and 
the inductive hypothesis, we know that we can make $n-10$ cents using only
dimes or quarters.  we can therefore make $n$ cents by adding
a dime, so we can make $n$ cents out of dimes and quarters.

This completes the inductive step, so we know we can make $n$ cents
out of dimes and quarters where $n=10$ or $n \geq 20$ and $n$ is a multiple 
of 5.

Now, we need to show that we cannot make any other amounts using only
dimes or quarters.  Take first the case of $5$ cents:  We clearly cannot
make $5$ cents because dimes and quarters are both larger than $5$ cents.
We also cannot make $15$ cents, by inspection.

We cannot make amounts that are not divisible by $5$ because any 
combination of dimes, $d$, and quarters, $q$, will give us 
$c=10d+25q =5(2d+5q)$, which is clearly a multiple of $5$ when 
d and q are natural numbers.

{\bf: Answer B.}
  We prove that we can make $20+5k$ cents 
  using dimes and quarters by strong induction on $k$.
  
  {\sc Base cases ($k=0,1$)} We can make $20$ and $25$ cents
  using two dimes and using one quarter respectively.

  {\sc Inductive Step ($k\geq 2$):}
  Assume we can make $20+5h$ cents for all $h<k$.
  In particular we can make $20+5(k-2)$ cents using 
  dimes and quarters. 
  Using one more dime, we can also make 
  $20+5(k-2) + 10=20+5k$ cents, 
  completing the induction proof.
}
\ppart Prove the same thing by well ordering
\newline
\solution{
{\bf: Answer A.}
Let's now prove the same thing using well-ordering. 

To make the statement of the problem clearer we introduce some 
notation.
Let $P(n)$ be the predicate ``$(n=10)\vee (5|n \wedge n\geq 20)''$,
and let $Q(n)$ be the predicate ``we can make $n$ cents using 
dimes and quarters''.

We claim that for all $n$, $P(n)\leftrightarrow Q(n)$,
i.e., we can make $n$ cents if and only if $n$
is $10$ or a multiple of $5$ not smaller then $20$.

This time we will prove 
$\forall n. P(n) \rightarrow Q(n)$
and $\forall n. Q(n) \rightarrow P(n)$ separately.

We first prove that $\forall n. P(n) \rightarrow Q(n)$.
Let $S$ be the set of all $n$ such that 
$P(n)$ and $\neg Q(n)$. 
We will show that $S$ is empty.
Assume for contradiction that $S$ is not empty.
By the well-ordering axiom, $S$ has a minimum element $m$.
Since $P(m)$ is true, $m$ is a multiple of $5$,
but we cannot make $m$ cents using dimes and quarters.
Notice that $m$ must be greater then or equal to $30$
because $10,20$ and $25$ cents can be made using 
respectively $1,2$ dimes or a quarter.
Let $n=m-10$.
We cannot make $n$ cents using dimes and quarters 
because otherwise we could also make $m=n+10$ cents
using one more dime. So, $Q(n)$ is false.
Moreover, $m\geq 30$ and therefore $n\geq 20$.
Since $n$ is a multiple of $5$,
$P(n)$ is true and $n$ is in the set $S$ contradicting 
the fact that $m$ was the minimum element.

We now prove that $\forall n. Q(n) \rightarrow P(n)$.
Let $T$ be the set of all $n$ such that 
$Q(n)$ and $\neg P(n)$. 
We will show that $T$ is empty.
Assume for contradiction that $T$ is not empty.
By the well-ordering axiom, $T$ has a minimum element $m$.
We have $Q(m)$, so we can make $m$ cents using dimes and quarters.
We distinguish two cases:
\begin{itemize}
\item if we used at least one dime to make $m$, 
 then we can also make $n=m-10$ cents using one less dime, 
 i.e., $Q(n)$.
 Moreover, $\neg P(n)$ because otherwise 
 also $m=n+10$ satisfies $\neq P(m)$ (if we add $10$ to a multiple of 
 $5$ it will still be a multiple of $5$).
 So, $n\in T$ contradicting that $m$ is minimum.
\item if we didn't use any dime to make $m$,
 then $m=25h$ and $P(m)$ which contradicts $m\in T$.
\end{itemize}

{\bf: Answer B.}
  We prove that we can make $20+5k$ cents 
  using dimes and quarters by well-ordering.
  Let $S$ be the set of all $k$ such that 
  we cannot make $20+5k$ cents using dimes and quarters
  and assume for contradiction that $S$ is not empty.
  By well-ordering, $S$ has a minimum element $m$.
  $m$ cannot be $0$ or $1$ because we can make 
  $20$ and $25$ cents. Therefore, $m\geq 2$
  and $m-2\geq 0$.
  We claim that $m-2$ is in $S$.
  To prove this, notice that if we could make $20+5(m-2) = 20+5m -10$
  cents using dimes and quarters, then we could make also 
  $20+5m$ cents using one more dime.
  But, this is impossible because $m\in S$.
  So, $m-2\in S$ and $m$ is not the minimum.
}
\end{problemparts}

%%%%%%%%%% PROBLEM %%%%%%%%%
% Source: pset3/spring97.tex, pset3/spring97sol.tex
% Topic: False Proofs, Well Ordering, Induction, 

\kproblem{induction7}
\pts{12}
\ksource{s97 ps3}
\ktopics{False Proofs, Well Ordering, Induction}
Find the flaws in  the following ``proofs.'' 

\begin{problemparts}

\ppart
CLAIM: $a^n = 1$ for all nonnegative
integers $n$, whenever $a$ is a nonzero real number. 

BASIS STEP: $a^0 = 1$ is true by the definition of $a^0$.

INDUCTIVE STEP: Assume that $a^k = 1$ for all nonnegative integers k with 
$ k \leq n$.  Then note that 
\( a^{n+1} = \frac{a^n \cdot a^n}{a^{n-1}} = \frac{1 \cdot 1}{1} = 1.
\)

\solution{
The flaw is that we should prove both $n=0$ and $n=1$ 
as bases cases because the inductive step uses the 
previous two values of $n$.
Clearly $a^1=1$ is not true, unless $a=1$,
and therefore the proof is wrong.
}

\ppart CLAIM: $\sqrt{2}$ is rational.

PROOF: Well-ordering.  Let $S$ be the set of all rational numbers
greater than or equal to $\sqrt{2}$.  This set contains a least
element $r$ by well-ordering.  If this element is not $\sqrt{2}$, then
there is another rational element between $\sqrt{2}$ and $r$ (by
denseness of the rationals), implying $r$ is not the smallest, a
contradiction.  Thus we must have $r=\sqrt{2}$.

\solution{
The flaw is that the well-ordering principle does not 
hold for the rationals, so we cannot use it to conclude 
that the above set has a minimum.
}

\ppart CLAIM: every number can be described in a phrase of less
than eighty characters.  

PROOF: Well-ordering.  Let $S$ be the set of numbers that
cannot be described in a phrase of less than eighty characters.  If it
is nonempty, it contains a smallest element.  This is ``The smallest
number that cannot be described in less than eighty chracters.''  This
is a description of that number in less than eighty characters, a
contradiction.  Since the assumption that $S$ was nonempty yields a
contradiction, $S$ must be empty and the claim is proved.

\solution{
The flaw in the above proof is that the set of numbers that 
can be described in less than eighty characters, 
is not a well-defined set.
}

\end{problemparts}

%%%%%%%%%% PROBLEM %%%%%%%%%
% Source: pset4/fall99.tex, pset4/fall99sol.tex
% Topic: Posets, Well Ordering

\kproblem{induction8}
\ksource{f99 ps4}
\ktopics{Posets, well ordering}
Let $R$ be the lexicographic ordering of strings of symbols
from a totally ordered alphabet as defined in Rosen p. 417.

\begin{problemparts}

\ppart Prove that $R$ is a total order.

\solution{
We first show that $R$ is a partial order.
Reflexivity is clear from the definition. To show antisymmetry,
suppose that $a_1\ldots a_m<b_1\ldots b_n$, and let $t=\min(m,n)$. This
means that either $a_1\ldots a_t = b_1\ldots b_t$ and $m<n$, so that
$b_1\ldots b_n \not <a_1\ldots a_m$, or else $a_1\ldots a_t<b_1\ldots b_t$,
so that $b_1\ldots b_t \not < a_1\ldots a_t$ and hence again 
$b_1\ldots b_n\not < a_1\ldots a_m$. Finally for transitivity, suppose that
$a_1\ldots a_m<b_1\ldots b_n<c_1\ldots c_p$
. Let $t=\min(m,n)$, $r=\min(n,p)$,
$s=\min(m,p)$, and $l=\min(m,n,p)$. Now if 
$a_1\ldots a_l<b_1\ldots b_l<c_1\ldots c_l$
then clearly $a_1\ldots a_m<c_1\ldots c_p$. Otherwise, without loss
of generality we may assume that $a_1\ldots a_l=b_1\ldots b_l$. If $l=t$
then $m<n$ and $m\le p$. Furthermore, either $b_1\ldots b_r<c_1\ldots c_r$
or $b_1\ldots b_r=c_1\ldots c_r$ and $n<p$. In the former case, if 
$r>l$, then since $p>m$ we have $a_1\ldots a_m<c_1\ldots c_p$, whereas if 
$r=l$ then $a_1\ldots a_l<c_1\ldots c_l$. In the latter case, 
$a_1\ldots a_s=c_1\ldots c_s$ and $m<p$, so again 
$a_1\ldots a_m<c_1\ldots c_p$. If $l<t$, then we must have 
$b_1\ldots b_l<c_1\ldots c_l$, whence $a_1\ldots a_l<c_1\ldots c_l$.
Finally, the fact that $R$ is a total order follows trivially from the 
definition of a lexicographic order and noticing
that the strings of symbols are taken from a totally ordered alphabet.
}

\ppart Prove that neither $R$ nor $R^{-1}$ is a well-ordering.

\solution{
Consider the alphabet $\{a,b\}$ with $a\preceq b$. Then $R$ is not
a well ordering since $\{b,ab,aab,aaab,aaaab,\ldots\}$ has no least element.
Moreover, $R^{-1}$ is not a well-ordering since $\{a,aa,aaa,aaaa,\ldots\}$
has no least element. 
%Consider the alphabet 
%$\{\ldots,a_{-2},a_{-1},a_0,a_1,a_2,\ldots\}$, 
%with the ordering 
%$\ldots\preceq a_{-1}\preceq a_0\preceq a_1\preceq\ldots$. 
%Then $R$ is not a well-ordering, since the set of strings, 
%$\{a_{-1},a_{-2},a_{-3},\ldots\}$ does not have a least element.
%Moreover, the set of strings $\{a_0,a_1,a_2,\ldots\}$ 
%does not have a least element under the ordering $R^{-1}$, and
%therefore $R^{-1}$ is not a well-ordering either.
}
\end{problemparts}

%\endinput

%%%%%%%%%% PROBLEM %%%%%%%%%
% Source: pset3/fall95.tex, pset3/fall95sol.tex
% Topic: Well Ordering (gcd, lcm)

\kproblem{wellordering1}
\ksource{f95 ps3}
\ktopics{Well Ordering (gcd, lcm)}
The least common multiple of two natural numbers, $m$ and $n$
is defined to be the smallest natural number $k$ such that $m|k$ and
$n|k$. It is denoted by $lcm(m,n)$.  Prove that every pair of natural
numbers has a least common multiple.  Using unique factorization, show
that $a\cdot b=gcd(a,b)\cdot lcm(a,b)$.

% kdmc: Should we include a definition of gcd here?  I don't think so.

\solution{
Let $m$ and $n$ be any two natural numbers.  Let $M$ be the set of
multiples of $m$ and $N$ the multiples of $n$. Consider $M \cap N$.
It is nonempty since it contains $mn$. By the well-ordering principle
it contains a least element which is the least common multiple of $m$
and $n$. Hence every pair of natural numbers has a least common multiple.

Let $a = {\displaystyle \prod}_i p_i^{\alpha_i}$ and $b =
{\displaystyle \prod}_i p_i^{\beta_i}$ where $p_1, p_2 \ldots$ are the
primes in increasing order. Following Theorem 7.12 in Handout 13, Notes 4, it was shown that $gcd(a,b) =  {\displaystyle \prod}_i p_i^{\min(\alpha_i,\beta_i)}$. By an identical argument it can be seen that $lcm(a,b) =  {\displaystyle \prod}_i p_i^{\max(\alpha_i,\beta_i)}$. Now, from the fact that for any $\alpha$ and $\beta$, $\alpha + \beta = \max(\alpha,\beta) +  \min(\alpha,\beta)$, it follows that  $a\cdot b=gcd(a,b)\cdot lcm(a,b)$.
}


%%%%%%%%%% PROBLEM %%%%%%%%%
% Source: pset3/fall94.tex
% Topic: Graphs, Well Ordering

\kproblem{wellordering2}
\ksource{f94 ps3}
\ktopics{Graphs, Well Ordering}
Prove that the vertices of an undirected graph can be colored
either red or blue such that at least half of the neighbors of every
red vertex are blue and at least half of the neighbors of every blue
vertex are red.  (\hint Associate a value with each coloring, and use
well ordering on the set of possible values.)

[[[I can't figure this one out after 5 minutes...]]]

%%%%%%%%%% PROBLEM %%%%%%%%%
% Source: pset3/fall94.tex
% Topic: Recursive Definitions, Strong Induction, Well Ordering, Weak Induction

\kproblem{wellordering3}
\ksource{f94 ps3}
\ktopics{Recursive Definitions, Strong Induction, Well Ordering, Weak Induction}
Define $u_n$ recursively by 
\[
u_0 = 2, \hspace*{.5in}
u_1 = 3, \hspace*{.5in}
u_n = 3u_{n-1} - 2u_{n-2} \mbox{ for } n\geq 2\ .
\]
Prove that $u_n = 2^n + 1$ using
\begin{problemparts}
\ppart
strong induction,
\ppart
well ordering,
\ppart
weak induction.
\end{problemparts}
Of course, the algebra in each of these three proofs will be similar, 
but the logic will differ.  Do not use the fact that these three induction
methods are equivalent.

%%%%%%%%%% PROBLEM %%%%%%%%%
% Source: pset3/spring98.tex, pset3/spring98sol.tex (Problem 5)
% Topic: Simple Graphs, Induction, Well Ordering, Graph Coloring

\kproblem{wellordering4}
\ksource{s98 ps3}
\ktopics{Simple Graphs, Induction, Well Ordering, Graph Coloring}

{\bf Definition}:
A simple graph, $G$, has {\em inherited degree $d \geq 0$ }
if and only if\\
(i) every vertex of $G$ has degree $\leq d$, or\\
(ii) there is a vertex $v \in G$ of degree $\leq d$, and the subgraph of
$G$ obtained by removing $v$ has inherited degree $\leq d$.

\bparts
\ppart
Prove that $W_n$ has inherited degree 3.

\solution{%
We use the induction on $n$.
Let $P(n)$::= $W_n$ has inherited degree 3.

{\bf Base Case:} $W_3$ has four vertices of degree 3 and it has 
inherited degree 3 by definition (i).

{\bf Inductive Step:} Assume $P(n)$ is true, we need to prove $P(n+1)$.
$W_{n+1}$ has $n+1$ vertices of degree $3$ and $1$ vertex of degree $n+1$.
The graph $G$ obtained by removing a vertex of degree $3$ has $n-2$ vertices
of degree $3$, $2$ vertices of degree $2$ and $1$ vertex of degree $n$.
We can also obtain $G$ by removing a edge between two vertices of degree $3$
in $W_n$. Since $W_n$ has inherited degree 3 by inductive hypothesis and removing an edge
does not increase the degree of vertices, $G$ has inherited degree 3.
Then, by definition (ii), $W_{n+1}$ has inherited degree 3.

Therefore, we prove that $W_n$ has inherited degree 3 for $\forall n \geq 3$.
}

%Since this single vertex graph has
%{\em inherited degree 3}, the graph right before (two verticies)
% has {\em inherited degree 3}. Therefore, by building back the
%$W_n$ up, we conclude that it has {\em inherited degree 3}.\\

%So, the point is that if you can keep removing a vertex with
%degree $\leq d$ until every vertex in the subgraph has 
%degree $\leq d$ then the original graph before the vertices are removed
%has {\em inherited degree d}.\\

\ppart
Prove that a tree has inherited degree 1.

We use the definition of tree in
Rosen, 8.1: a tree is a connected undirected graph with no simple
circuits.  Also, we only consider trees with a finite number of
vertices.

\solution{
We need to prove two facts here. First we have to prove that every tree 
with at least two vertices has a leaf (a leaf is a vertex of degree one). 
Then we need to show that the subgraph
constructed by removing one leaf is still a tree.

First, let's prove that every tree with at least two vertices has a leaf.
Let $T$ be a tree, and let $P$ be a longest simple path in $T$. 
In a finite graph, a path of length greater than or equal to 
the the number of vertices must visit some vertex more than once.  
So a \emph{simple} path must be shorter than the
number of vertices.  Therefore in any finite graph there must be longest
simple path.  (We're using the Well-ordering principle here, taking the
least element of $\set{\card{V}-k : k \mbox{ is the length of a simple
path}}$.)

Suppose $P = (v_1, v_2 \ldots, v_k)$, we claim that $v_1$ is a leaf.  
For if not, there will be an edge $\{v,v_1\}$ in $T$ where $v \neq v_2$. 
The vertex $v$ cannot occur in $P$, for otherwise this creates a cycle, which 
contradicts that the graph is a tree.
Therefore, $P'=(v, v_1, v_2 \ldots, v_k)$ is also a simple path in the tree 
and $P'$ is longer than $P$. But this is a contradiction  
because we have assumed that  $P$ is the longest path in the tree. 
As a result, a tree with 2 or more vertices has to have a leaf. 

Second, let's prove that the subgraph constructed by removing one leaf
is still a tree. 
From the definition given in the
book (cf. Rosen p531), a tree is a connected undirected graph with no simple
circuits. Removing a leaf from a tree does not create any 
circuit. Also, since the leaf has degree 1, it is not connecting any 
other two vertices in the tree. Therefore, after removing the leaf, no vertices 
get disconnected. In other words, the subgraph is still connected.
%removed is adjacent to only one vertex and
%that leaf can only be connected to the graph via the adjacent vertex, 
%the subgraph is still connected. 
Since the subgraph is a connected undirected 
graph with no simple circuits, it is also a tree.

Since every tree has a leaf(vertex with degree 1) and the subgraph
is still a tree after removing a leaf, we can apply the same
method in the previous part to show that a tree has inherited degree 1.
}

\ppart
Prove that if a graph has inherited degree $d$, then it is
$(d+1)$-colorable.

\solution{
We use induction on the number of
vertices in a graph to prove this fact. 

Let $P(n)$::= ``$\forall d>0$, any $n$-vertex graphs with inherited degree $d$ is $(d+1)$ colorable.''  

{\bf Base Case}: $n=1$. There is only one 1-vertex graph. And it is obviously
$(d+1)$ colorable ($\forall d>0$).

{\bf Inductive Step:} Assume that $P(n)$ is true, we need to 
prove $P(n+1)$ is true. Given any $(n+1)$-vertex graph $G$ with inherited degree $d$ for any $d>0$, 
there are 2 possible cases: 
\begin{enumerate}
\item All vertices in $G$ has degree $\leq d$. Then it is $(d+1)$-colorable,
as proved in the lecture.
\item There is a vertex $v\in G$ of degree $\leq d$, and the subgraph
$G'$ obtained by removing $v$ has inherited degree $d$. Since $G'$
has $n$ nodes and has inherited degree $d$, by inductive hypothesis $G'$ is 
$(d+1)$ colorable. Now consider the vertex $v$. Since it has degree $\leq d$,
it has at most $d$ neighbors and therefore it can be colored with the $(d+1)^{st}$ color 
which is different from all of its neighbors.
\end{enumerate}

Therefore, by induction, every graph with inherited degree $d$ is $(d+1)$-colorable.

%following method to color a graph with inherited degree $d$.
%Let's remove a vertex with degree $\leq d$ until we have every 
%vertices have the degrees $\leq d$.
%Then, we can easily show that every graph with all the vertices with
%degree $\leq d$ can be colored with $d+1$ colors by induction.\\
%The base case is a graph with one vertex. It is true since only one
%color is needed. For induction step, 
%let's consider a graph $G_{n+1}$ with $n+1$ vertices of degree $\leq d$.
%Let's remove a vertex from $G$ and let say the remaining graph is $G_n$.
%Since we are not increasing the degree of any vertex by removing a vertex,
%all the vertices in $G_n$ have the degrees $\leq d$. So, by inductive
%hypothesis, we can color $G_n$ with $d+1$ colors. Now, let's put the
%vertex we took out back to the graph. Since that vertex can be adjacent
%to at most $d$ other vertices, we can color it with one remaining color.
%Therefore, we proved that every graph with all the vertices with degree
%$\leq d$ can be colored with $d+1$.\\
%
%Then,  we can keep adding a vertex with degree $\leq d$ to build back 
%the original graph with inherited degree $d$, since we can always 
%assign a (n+1)th color to the added vertex. Therefore,
%Any graph with inherited degree $d$ is (d+1) colorable.\\
}

\ppart
For every $n>0$, describe an example of a graph which does not have
inherited degree n, but which is 2-colorable.

\solution{
An example would be $K_{n+1, n+1}$. Every vertex in $K_{n+1, n+1}$ has
degree $n+1$. Therefore, it does not have inherited degree $n$.
However, it is $2$-colorable since every complete bipartite graph is $2$-colorable.
}

\eparts


%%% pigeonhole principle %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\kproblem{pigeonhole1}
\pts{10}
\ksource{Kyle's brain, inspired by a trip to the
  Galleria}\ktopics{Pigeonhole principle} For their annual convention,
the members of the MIT Antisocial League rent out the cafeteria at the
CambridgeSide Galleria.  The cafeteria is an $n\times n$ grid, with
exactly one table and a \textit{single} associated chair at each
point.  A chair can be positioned around its table to face in one of
four directions, corresponding to the axes of the grid.

Due to space considerations, every attendee must sit at a chair.  But,
since this is the Antisocial League, no seated person can directly
face another occupied table (i.e., there can be no one sitting at a
table in a person's direct line of sight).  Prove that this must occur
if $4n+1$ members attend.

\solution{We use the pigeonhole principle to prove the theorem.
  Orient a representation of the grid in some canonical way with one
  axis pointing left-right, and the other pointing up-down.
  
  There are four directions in which people can face.  As a result, by
  the generalized pigeonhole principle, at least $n+1$ people must be
  facing in some direction.  Without loss of generality, assume this
  is downwards.
  
  Create $n$ pigeonholes from the columns of the grid.  By the PP, if
  there are $n+1$ attendees facing downwards, at least two must be in
  the same column, so clearly one must be directly facing another
  occupied table.
  
  It is likely that equality is not achieved (which would be proved by
  demonstrating an arrangement of $4n$ people in which no one directly
  faced another occupied table).  This suggests a stronger theorem can
  be proven.  The best we can do so far is $4n-4$; try to figure out
  such a solution.}

[[[Students can get stuck on the problem above if they don't see the trick.
It would be nice to at least tell them to use pigeonhole.
But then they can still get stuck if they don't think of first using the 4 
directions as the holes (I tried to use the rows or columns).  
Wouldn't it be nice to give out hints in return for points...]]]

\kproblem{counting1}
\ksource{Nancy/Carl/Victor}
\ktopics{Counting, Injections, Surjections}
Which of the following is the cardinality of the set of all
surjections from a set $A$, where $|A|=n$, and $B$, where $|B|=m$.
\begin{description}\itemsep 0\baselineskip
\item[(a)] $m^n$
\item[(b)] $\frac{m!}{(m-n)!}$
\item[(c)] ${n \choose m} m^{n-m} m!$
\item[(d)] None of the above.
\end{description}

\solution{%
  (d) None of the above.}

\kproblem{counting2}
\ksource{Nancy/Carl}
\ktopics{Counting}
Suppose you have a collection of 41 balls, of which you know that 40
have normal weight and one is abnormal~---~either heavy or light, but
you don't know which.

Is there a way to determine which ball is abnormal with 4 weighings?
If so, demonstrate the approach, otherwise prove that it is
impossible.

\solution{%
  No.  The 4 weighings can only generate 81 distinct outcomes.
  However, any of the 41 balls can be the abnormal one and the
  abnormal one can be either light or heavy, i.e., 82 distinct
  outcomes.}

%%% summations, asymptotics %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\kproblem{summations1}\ksource{Kyle's brain, modified from PS6
  n4}\ktopics{Summations, asymptotics} Prove that the ``average''
number of perfect square\footnote{$x$ is a perfect square if there is
  some natural number $y$ such that $y^2=x$.} divisors of a number of
size $n$ is bounded from above by a constant.  More formally, let
$t(n)$ be the number of divisors of the number $n$ that are themselves
perfect squares, and let \[ T(n)=\frac{1}{n}\sum_{j=1}^n t(j) \] be
the average number of perfect square divisors of all numbers less than
or equal to $n$.  Show that there exists a constant $c$ such that for
all $n$, $T(n)\leq c$.  \hint{Let the function $f(i,j)=1$ if $i^2$ is
  a divisor of $j$, and 0 otherwise.  What do the row and column sums
  of $f(i,j)$ mean?}

\solution{Consider the image of the function $f(i,j)$ as a matrix
  whose rows and columns correspond to values of $i$ and $j$
  respectively; that is, element $(i,j)$ of the matrix denotes whether
  or not $i^2$ divides $j$.
  \[
  \begin{array}{cc|ccccccccccccccccc}
    &&&&&&&&&&& j\\
    &f(i,j) & 1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16\\ \hline
    &1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1\\
    i&2&0&0&0&1&0&0&0&1&0&0&0&1&0&0&0&1&\cdots\\
    &3&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0\\
    &4&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1\\
    &\vdots &&&&&&&&&& \vdots
  \end{array}
  \]
  Notice that the sum of each column $j$ corresponds to the number of
  perfect square divisors of the number $j$ and the sum of each row
  $i$ corresponds to the number of multiples of the number $i^2$.  As
  a result, the number of multiples of $i^2$ between $1$ and $n$ can
  be compactly represented as $\lfloor n/i^2\rfloor$.
  
  It follows that
  \begin{eqnarray*}
    T(n)
    &=&\frac{1}{n}\sum_{j=1}^n t(j) \\
    &=&\frac{1}{n}\sum_{i=1}^{\floor{\sqrt{n}}} \sum_{j=1}^n f(i,j) \\
    &=&\frac{1}{n}\sum_{i=1}^{\floor{\sqrt{n}}} \floor{\frac{n}{i^2}}
  \end{eqnarray*}
  $T(n)$ can then be bounded from above as follows:
  \begin{eqnarray*}
    T(n)
    &\leq&\frac{1}{n}\sum_{i=1}^{\floor{\sqrt{n}}}\frac{n}{i^2} \\
    &=&\sum_{i=1}^{\floor{\sqrt{n}}}\frac{1}{i^2} \\
    &\leq&1+\int_{1}^{\sqrt{n}}\frac{1}{x^2}dx \\
    &=&1+\frac{\sqrt{n}-1}{\sqrt{n}}\leq 2
  \end{eqnarray*}
  }


\kproblem{recurrences1}
\ksource{Carl...}
\ktopics{Recurrences and summations}
\ppart Solve the following homogeneous recurrence, assuming that
$T(0)=1$ and $T(1)=1$.

$$T(n) = T(n-1) - \frac{1}{4} T(n-2)$$

\solution{
  I think the answer here is:

  $$T(n) = (1/2)^n + n \cdot (1/2)^n$$
}

\ppart Find a closed-form solution for the infinite sum:

$$\sum_{n = 0 }^{\infty} T(n)$$

\solution{
  we just sum the terms and get 4.
}


\kproblem{recurrences2}
\pts{12}
\ksource{Kyle}
\ktopics{Recurrences}
\ppart 
\pts{3}
Iterate the following recurrence to find a pattern:
\[ T(n)=a_0 T(n/b_0) + a_1 T(n/b_1) + f(n) \]
where $T(n/(b_0^i b_1^{m-i}))=c$ for all $i\in\set{1,\ldots,m}$ with
$a_{\set{0,1}}$, $b_{\set{0,1}}$, and $c$ all constant.  Demonstrate a
non-recurrent formula that \textit{may} have summations in it.

\solution{Denote $g(x)=T(n/x)$, so $g(b_0^i b_1^{m-i})=c$.  Then:
\begin{eqnarray*}
T(n)
&=& a_0 g(b_0) + a_1 g(b_1) + f(n) \\
%
&=& a_0^2 g(b_0^2) + 2a_0 a_1 g(b_0 b_1) + a_1^2 g(b_1^2) \\
&& + f(n) + \kbrack{a_0 f(n/b_0) + a_1 f(n/b_1)} \\
%
&=& a_0^3 g(b_0^3) + 3a_0^2 a_1 g(b_0^2 b_1) + 3a_0 a_1^2 g(b_0 b_1^2)
 + a_1^3 g(b_1^3) \\
&& + f(n) + \kbrack{a_0 f(n/b_0) + a_1 f(n/b_1)} + \kbrack{a_0^2
f(n/a_0^2) + 2a_0 a_1 
f(n/(b_0b_1)) + a_1^2 f(n/a_1^2)} \\
%
&\vdots& \\
%
&=& \sum_{i=0}^m \kparen{\binom{m}{i} a_0^i a_1^{m-i} g(b_0^i
b_1^{m-i})} \\
%
&& + \sum_{j=0}^m \sum_{i=0}^j \kparen{\binom{j}{i} a_0^i a_1^{j-i}
f(n/(b_0^i b_1^{j-i}))} \\
%
&=& c(a_0+a_1)^m \\
&& + \sum_{j=0}^m \sum_{i=0}^j \kparen{\binom{j}{i} a_0^i a_1^{j-i}
f(n/(b_0^i b_1^{j-i}))}
%
\end{eqnarray*}}

\ppart 
\pts{3}
Find asymptotically tight bounds for the following recurrence:
\[ T(n)=8T(n/2) + n^3\left(\log n\right)^2 \]
given that $T(1)=1$.  You may assume $n$ is a power of 2.  Note that
the master theorem \textit{does not apply} to this recurrence.

\solution{Use the first part, with $a_0=4$, $a_1=4$, $b_0=b_1=2$,
  $m=\log n$, $c=1$, and $f(n)=n^3\log^2 n$.  (Note that we can't take
  $a_0=0$ or $a_1=0$, since $0^0$ is indeterminate; we could, however,
  have used any other $a_0$ and $a_1$ such that $a_0+a_1=8$.)
  
  Plugging and chugging:
  \begin{eqnarray*}
    T(n)
    &=& 4T(n/2) + 4T(n/2) + n^3\log^2 n \\
    &=& 1(4+4)^{\log n} + \sum_{j=0}^{\log n} \sum_{i=0}^j \kparen{\binom{j}{i}
      4^j (n/2^j)^3\log^2 (n/2^j)} \\
    &=& n^3 + \sum_{j=0}^{\log n} \kparen{8^j (n/2^j)^3\log^2 (n/2^j)} \\
    &=& n^3 + n^3\sum_{j=0}^{\log n} \kparen{\log^2 (n/2^j)} \\
    &=& n^3 + n^3\sum_{j=0}^{\log n} \kparen{\log^2 n-2j\log n+j^2} \\
    &=& n^3 + n^3\kparen{\log^3 n+ \log^2 n} - 2n^3\log n\sum_{j=0}^{\log n} j
    + n^3 \sum_{j=0}^{\log n} j^2 \\
    &=& n^3 + n^3\kparen{\log^3 n+ \log^2 n} - n^3\kparen{\log^3 n+\log^2 n}
    + n^3 \sum_{j=0}^{\log n} j^2 \\
    &=& n^3 + n^3 \sum_{j=0}^{\log n} j^2 \\
  \end{eqnarray*}
  We must bound the last term, $\sum_{x=0}^n x^2$, by the integral method:
  \begin{eqnarray*}
    \sum_{x=0}^Y x^2
    &\leq& \int_0^Y (x+1)^2 dx \\
    &=& \frac{1}{3}(x+1)^3 \Big|_0^Y \\
    &=& \frac{1}{3}(Y+1)^3-\frac{1}{3}
  \end{eqnarray*}
  and
  \begin{eqnarray*}
    \sum_{x=0}^Y x^2
    &\geq& \int_0^Y x^2 dx \\
    &=& \frac{1}{3}x^3\Big|_0^Y \\
    &=& \frac{1}{3}Y^3
  \end{eqnarray*}
  so the last term is asymptotally bounded by $n^3\log^3 n$; thus, the
  entire summation is $\Theta(n^3\log^3 n)$.

  }

\ppart Find a good lower bound for the following recurrence:
\[ T(n)=2T(n/2)+3T(n/4)+\log n \]
in terms of $m$ and $n$, given that $T(n/(2^i 4^{m-i}))=T(n/(2^{2m-i}))=1$.
\hint{Recall that $\sum_{i=0}^n ix^i = (x-(n+1)x^{n+1} +
  nx^{n+2})/(1-x)^2$.}

\solution{We use the first part, with $c=1$, $a_0=2$, $a_1=3$,
  $b_0=2$, and $b_1=4$.
                                %
  \begin{eqnarray*}
    T(n)
    &=& 5^m + \sum_{j=0}^m \sum_{i=0}^j \kparen{\binom{j}{i} 2^i 3^{j-i}
      \log(n/(2^i 4^{j-i}))} \\
                                %
    &=& 5^m + \sum_{j=0}^m \sum_{i=0}^j \kparen{\binom{j}{i} 2^i 3^{j-i}
      \kparen{\log n - \log \kparen{2^j 2^{j-i}} }} \\
                                %
    &=& 5^m + \sum_{j=0}^m \kparen{
      5^j \log n
      - \sum_{i=0}^j \kparen{\binom{j}{i} 2^i 3^{j-i}
        \kparen{j + j-i} }} \\
                                %
    &\geq & 5^m + \sum_{j=0}^m \kparen{
      5^j \log n
      - \sum_{i=0}^j \kparen{\binom{j}{i} 2^i 3^{j-i}
        \cdot 2j}} \\
                                %
    &=& 5^m + \sum_{j=0}^m \kparen{
      5^j \log n
      - 5^j\cdot 2j} \\
                                %
    &=& 5^m + \frac{5^{m+1}-1}{4}\log n
    -2\cdot\frac{5-(m+1)5^{m+1}+m\cdot 5^{m+2}}{16}
  \end{eqnarray*}
  }

\ppart From the first part, extrapolate a formula (not necessarily a
closed form) for the following recurrence:
\[ T(n)=a_0 T(n/b_0) + a_1 T(n/b_1) + \cdots + a_k T(n/b_k) + f(n) \]
where $T(n/(b_0^{i_0} b_1^{i_1}\cdots b_k^{i_k}))=c$ for all
$\sum_{j=0}^{k} i_j=m$ with $a_{\set{0,1,\ldots,k}}$,
$b_{\set{0,1,\ldots,k}}$, and $c$ all constant.


\kproblem{recurrences3}
\pts{14}
\ksource{Kyle}
\ktopics{Homogeneous/inhomogeneous LDE}
%[[[This is really funny.]]]

One of the top \textit{ore-cum-food} firms, Amalgamated Steel and
Spice, has been receiving complaints based on the spreading rumor that
one of its products---Happy-O's with Nuts---actually has rusting iron
filings instead of pecan shavings.

During the time in which the X-Files were closed, Mulder and Scully
were sent in to investigate.  With the help of (the suave) Langley and
(the mighty) Frohike, they were able to gather enormous amounts of
data concerning a conspiracy against the American people to hide the
Truth behind this supposed ``mistake.''

\bparts

\ppart\pts{2} Our heroes find that a new complaint on any particular
day generates one new complaint on the following day and six new
complaints on the day after that.  Write a recurrence $T(n)$ that
represents the number of new complaints on day $n$.

\solution{$T(n)=T(n-1)+6T(n-2)$}

\ppart\pts{6} On day $1$, 0 complaints are generated; on day $2$, 30
complaints are generated (i.e., $T(1)=0$ and $T(2)=30$).  Find a
closed form for the recurrence in the previous part.

\solution{The characteristic equation is $x^2-x-6=0$, whose roots are
  $3$ and $-2$.  The general solution is then of the form
  $T(n)=A3^n+B(-2)^n$.  Now we solve for the constants by plugging in
  the initial conditions: $0=3A-2B$ and $30=9A+4B$ imply that $A=2$ and
  $B=3$.  So, the final solution is $T(n)=2\cdot 3^n+3(-2)^n$.}

\ppart\pts{6} Scully does some more digging and notices that $6n$ new
complaints are filed spontaneously on day $n$ for $n\geq 1$.  Find new
initial conditions based on this new information, show an
inhomogeneous recurrence, and find a closed-form solution to it.

\solution{The general solution to the inhomogeneous part remains as
  before; now, however, we have the initial conditions $T(1)=6$ and
  $T(2)=42$, and an inhomogeneous part $n$.  We guess a linear
  solution $an+b$, and plug in the initial conditions:
  \begin{eqnarray*}
    an+b
    &=&an+b+6(an+b)+6n  \\
    0
    &=&(6a+6)n+6b
  \end{eqnarray*}
  So $6a+1=0\Rightarrow a=-1$ and $6b=0\Rightarrow b=0$ for our
  particular solution $-n$.  So, we plug in and solve for the
  constants:
  \begin{eqnarray*}
    T(1) = 6 &=& 3A - 2B - 1 \\
    T(2) = 42 &=& 9A + 4B - 2
  \end{eqnarray*}
  The solutions to this system are $A=58/15$ and $B=23/10$.  So, our
  complete solution is $T(n)=(58/15)3^n + (23/10)(-2)^n - n$.}

\eparts


%%%%%%%%%% PROBLEM %%%%%%%%%
% Source: kdmc
% Topic: Relations
\kproblem{relations1}
\ksource{kdmc}
\ktopics{Relations}
Let the relations $R$ and $S$ be binary relations on the set $\naturals$ of 
natural numbers.  Define $R$ as follows: 
$\forall (a, b) \in \naturals \times \naturals (a, b) \in R iff a \text{mod} 4 = b \text{mod} 4$.
Define $S$ as follows: 
$\forall (a, b) \in \naturals \times \naturals (a, b) \in R iff 2^{a} = b \land b \leq 15$.

\begin{problemparts}
\ppart
Prove that $R$ is $transitive$.
\newline
\solution{
$\forall $
{\bf not done yet}
}
\ppart
Prove that $R$ is $symmetric$.
\newline
\solution{
$\forall a \in \naturals$ we have that $a mod 4 = a mod 4$, as modulo is a 
defined to be a function (same input yields same output).  Thus, 
$\forall a \in \naturals (a, a) \in R$.
}
\ppart
Suppose $T = R \intersect S$.  Fully define the relation $T$.
\newline
\solution{
$T = R \intersect S = \forall (a, b) \in \naturals \times \naturals (a, b) \in T iff a \text{mod} 4 = b \text{mod} 4 = 0 \land b \leq 15$.
}
\ppart
Let $W = S \composition R$.  Prove that $W$ is antisymmetric.
\newline
\solution{
We know that $\forall (a, c) \in W c \leq 15$.  Thus, we can define a set 
$B = \{1, 2, 4, 8\}$ where 
$\forall b \in \naturals b \in B iff b \leq 15 \land b = 2 for some n \in \naturals$.
We can now say that 
$W \subseteq \naturals \times B \subseteq \naturals \times \naturals$.  Thus, 
$\forall x \in \naturals \forall y \in \naturals xWy \land yWx iff x \in B \land y \in B$.  But there is no such $(x, y)$ pair in $W$.  The statement 
$\forall x \in \naturals \forall y \in \naturals \not (xWy \land yWx)$, so the
requirement for antisymmetry is vacuously true.
}
\problempart
Find $R \composition S$.
\newline
\solution{
Let us define the set $M_i \subseteq \naturals$ as $\{x | x mod 4 = i\}$.  
Then, clearly there are 4 such sets, namely $M_0$, $M_1$, $M_2$, and $M_3$.  
Let $(x, y) \in Z = R \composition S iff (x = 0 \land y \in M_1) \lor (x = 1 \land y \in M_2) \lor (x = 2 \lor x = 3) \land y \in M_0$
}
\end{problemparts}

%%%%%%%%%% PROBLEM %%%%%%%%%
% Source: pset3/spring98sol.tex, original source Rosen 7.3-32
% Topic: Relations, Adjacency Matrix, Recursive Definitions

\kproblem{relations2}
\ksource{s98 ps3}
\ktopics{Relations, Adjacency Matrix, Recursive Definitions}
The graphs  $C_n$, $Q_n$, $W_n$, and $K_{n,m}$ are defined in Rosen 7.2.

\bparts

\ppart Describe the adjacency matrix for $C_n$.

For $C_n$, we label the vertices so that the cycle goes 
$v_1,v_2,\ldots,v_n,v_1$.  Then the matrix has 1's on the diagonals just 
above and below the main diagonal and in positions $(1,n)$ and $(n,1)$,
and 0's everywhere else. 

\begin{gather*}
\begin{pmatrix}
0 & 1 & 0 & 0 &\ldots & 0 & 1\\
1 & 0 & 1 & 0 &\ldots & 0 & 0\\
0 & 1 & 0 & 1 &\ldots & 0 & 0\\
0 & 0 & 1 & 0 &\ldots & 0 & 0\\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\
0 & 0 & 0 & 0 &\ldots & 0 & 1\\
1 & 0 & 0 & 0 &\ldots & 1 & 0\\
\end{pmatrix}
\end{gather*}


\ppart Describe the adjacency matrix for $K_{n,m}$.


Vertices of $K_{n,m}$ are partitioned into a group of $n$
vertices and a group of $m$ vertices. In this graph, an edge is
present between two vertices if and only if the two vertices are from 
different groups.
Therefore, the adjacency matrix of $K_{n,m}$ consists of
four sub-matrices. The top left and the bottom right matrices
consist of 0's with size $n * n$ and $m * m$ respectively.
The top right and the bottom left matrices consist of 1's
with size of $n * m$ and $m * n$ respectively.
 
 
\begin{gather*}
\begin{pmatrix}
0 & \ldots & 0 & 1 & \ldots & 1\\
\vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\
0 & \ldots & 0 & 1 & \ldots & 1\\
1 & \ldots & 1 & 0 & \ldots & 0\\
\vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\
1 & \ldots & 1 & 0 & \ldots & 0\\
\end{pmatrix}
\end{gather*}


\ppart Give a simple recursive definition of the adjacency matrix for the
graph $Q_{n+1}$.  \hint Use the matrix of $Q_n$ and suitable identity
matrices.

The base case is,
 
\begin{gather*}
Q_1 =  
\begin{pmatrix}
0 & 1\\
1 & 0\\
\end{pmatrix}
\end{gather*}
 
Then, every $Q_{n+1}$ ($n \geq 1$) is defined inductively. 
The size of $Q_{n+1}$ is
$2^{n+1} * 2^{n+1}$ and the left top and right bottom quarter of the matrix
are $Q_n$, which correspond to the two subgraphs $Q_n$ in $Q_{n+1}$. The right top and left bottom quarter of the matrix
are identity matrices of size $2^n*2^n$($I_{2^n}$), which correspond to the 
edges connecting vertices $k$ and $k+2^n$ for $0\leq k<2^n$, which differ by the most 
significant bit only.

\begin{gather*}
Q_{n+1} =
\begin{pmatrix}
Q_n & I_{2^n} \\
I_{2^n} & Q_n \\
\end{pmatrix}
\end{gather*}

\eparts

%%%%%%%%%% PROBLEM %%%%%%%%%
% Source: from H10-tut3.tex, not used this year.
% Topic: Relations and Closures

\kproblem{relations3}
\ksource{H10-tut3, not used}
\ktopics{Relations and Closures}
Let $R$ be any relation.  Prove that any relation that
contains $R$ and is reflexive (resp. symmetric, transitive) contains the
reflexive (resp. symmetric, transitive) closure of $R$.   This means
the closure is the "smallest" containing set that has the property.

\solution{
}

% kdmc: NEED MORE RELATIONS/POSETS/EQUIVALENCE RELATIONS

%%%%%%%%%% PROBLEM %%%%%%%%%
% Source: pset3/fall96.tex, Rosen 6.5, Problem 32
% Topic: Equivalence Relations

\kproblem{relations4}
\pts{10}
\ksource{f96 ps3}
\ktopics{Equivalence Relations}
Each bead on a bracelet with three beads is either red, white, or
blue as illustrated in the example shown. Define the relation {\em R}
between bracelets as follows: $(B_1,B_2)$, where $B_1$ and $B_2$ are
bracelets, belongs to $R$ if and only if $B_2$ can be obtained from
$B_1$ by rotating it or rotating it and then reflecting it.

%\begin{figure}[h]
%\centerline{\psfig{figure=bead.ps,height=1in}}
%\end{figure}

\begin{itemize}
\item Show that $R$ is an equivalence relation.

\item What are the equivalence classes of $R$?
\end{itemize}

%%%%%%%%%% PROBLEM %%%%%%%%%
% Source: pset3/fall97sol.tex, Problem 10
% Topic: Equivalence Relations, Equivalence Classes

\kproblem{relations5}
\ksource{f97 ps3}
\ktopics{Equivalence Relations, Equivalence Classes}
% kdmc: should we give them the definition of equivalence relation?
{\em Definition:}
Let $S$ be a set.  Let $R$ be a subset of $S \times S$.
$R$ is an {\em equivalence relation} if it satisfies the following properties

\begin{enumerate}
\item $\forall a \in S, (a,a) \in R$ (reflexivity).
\item If $(a,b) \in R$, then $(b,a) \in R$ (symmetry).
\item If $(a,b) \in R$ and $(b,c) \in R$, then $(a,c) \in R$ (transitivity).
\end{enumerate}

{\em Definition:}
Let $R$ be an equivalence relation on $S$.  For $a \in S$, we define the
{\em equivalence class} of $a$ to be the set
$[a]_R = \{ b \in S | (a,b) \in R \}$.

For example, the relation $R$ defined by
$(a,b) \in R$ if $a \equiv b \text{ mod } 4$ is an equivalence
relation on $\integers$.  There are four equivalence classes for this relation,
namely:

\begin{itemize}

\item $[0]_R = \{ z \in \integers | z \equiv 0  \text{ mod } 4 \}$
\item $[1]_R = \{ z \in \integers | z \equiv 1  \text{ mod } 4 \}$
\item $[2]_R = \{ z \in \integers | z \equiv 2  \text{ mod } 4 \}$
\item $[3]_R = \{ z \in \integers | z \equiv 3  \text{ mod } 4 \}$

\end{itemize}

\bparts

\ppart Let $G$ be a simple graph.  Define a relation $R$ on the set of vertices $V$
of $G$ by $(v,u) \in R$, if there is a path connecting $u$ to $v$.

Verify that $R$ is an equivalence relation.

\solution{
\begin{itemize}

\item Reflexivity:

$R$ is reflexive because trivially every vertex is connected to itself.

\item Symmetry:

Suppose there is a path $(u,x_1), (x_1,x_2), \ldots, (x_n,v)$ connecting 
$u$ to $v$.
Then, the path $(v,x_n), \ldots, (x_1,u)$ connects $v$ to $u$. 
Therefore, $R$ is symmetric.

\item Transitivity:

Let the path $(u,x_1), (x_1,x_2), \ldots, (x_n,v)$ connect $u$ to $v$, and
the path \\
$(v,y_1), (y_1,y_2), \ldots, (y_m,w)$ connect $v$ to $w$.

Then the path $(u,x_1), \ldots, (x_n,v), (v,y_1), \ldots ,(y_m,w)$
connects $u$ to $v$.\\
Therefore $R$ is transitive.

\end{itemize}
}

\ppart What are the equivalence classes of $R$?

\solution{
The equivalence classes of $R$ are the connected components of $G$.
}
\eparts

%%%%%%%%%% PROBLEM %%%%%%%%%
% Source: pset3/fall98sol.tex
% Topic: Relations, Basic Properties

\kproblem{relations6}
\ksource{f98 ps3}
\ktopics{Relations, Basic Properties}
A relation $R$ on a set $A$ is {\em weakly
transitive} if for all $a, b, c, d \in A$, the relations $aRb$, $bRc$,
and $cRd$ imply the relation $aRd$.

Prove or disprove the following statements.

\begin{problemparts}

\ppart Every symmetric, weakly transitive relation is transitive.

\solution{
The claim is false.  The diagram below shows a counterexample.

%\begin{figure}[h!]
%\centerline{\resizebox{!}{1.0in}{\includegraphics{ps3-relation-cx.eps}}}
%\end{figure}
}

\ppart Every reflexive, symmetric, weakly transitive relation
is an equivalence relation.

\solution{
\begin{proof}
The relation $R$ is an equivalence relation if it is reflexive,
symmetric, and transitive.  The first two properties hold by
assumption; all that remains is to show that $R$ is a transitive
relation.  Suppose that the relations $aRb$ and $bRc$ hold.  Because
$R$ is reflexive, the relation $aRa$ also holds.  Because $R$ is
weakly transtive, the relations $aRa$, $aRb$, and $bRc$ imply the
relation $aRc$.  Therefore, $R$ is transitive.
\end{proof}
}

\end{problemparts}

\kproblem{statemachines1}
\pts{15}
\ksource{nancy}
\ktopics{state machines}
Consider a state machine whose state is a digraph with the 5-element vertex set 
$V = \{ 1,2,3,4,5 \}$,
initially the "linear graph" as depicted below: \\
\\
1 ---> 2 ---> 3 ---> 4 ---> 5 \\
\\
The transitions allowed by the state machine are the following: \\

-- remove(a,b):
   Can occur if there is an edge from a to b.
   Effect is to remove the edge. 

-- add-out(a,b) (distinct): 
   Can occur if a has no incoming edges.
   Effect is to add the edge a ---> b.

-- add-in(a,b): 
   Can occur if a has no outgoing edges.
   Effect is to add the edge b ---> a.

-- reverse(a):
   Can occur if either all edges incident upon a are incoming, or all are outgoing.
   Effect is to reverse the direction of all edges incident on a.

-- trans(a,b,c) (all three distinct): 
   Can occur if a ---> b and b ---> c.
   Effect is to add the edge a ---> c.

Say whether each of the following digraphs is reachable.
If it is, then describe an execution that reaches it.  
If not, then state an invariant that can be used to show that the state cannot 
be reached.
Your invariant must be provable by induction (or the Invariant Theorem).

(a) The graph that is the same as the line graph above but with
the additional edge 5 ---> 1. 

Ans:  Not reachable.
Invariant is that the graph in the state is always acyclic.

(b) The line graph in the opposite direction:

1 <--- 2 <--- 3 <--- 4 <--- 5

Ans:  Reachable.
Can do, e.g., by 
reverse(1)
reverse(2)
reverse(1)
reverse(3)
reverse(2)
reverse(1)
reverse(4)
reverse(3)
reverse(2)
reverse(1)

(Potential here for wasting too much time if they don't see the trick??)

Now suppose we have the same state machine, but without the remove and reverse
transitions.
We want to prove that eventually, a transitively closed graph is produced.
Assume that we are considering a "live" execution, that doesn't stop 
as long as any transition is enabled. 

(c)
Define a termination function that can be used to prove this eventuality property.
Argue the key properties

(It should have a natural number value, and decrease with every transition.  
Also, when no step is enabled, the graph should be transitively closed.)

Ans:  n(n-1) minus number of edges should work.  Each transition decreases this
because it adds an edge.
When no step is enabled, the graph must be transitively closed, because we have
an explicit transitive closure step.

Actually, I was playing with a more interesting version of the problem, where
the reverse isn't disabled.
We're still guaranteed to eventually end up with a transitively closed graph,
but we must assume a stronger kind of liveness.  That is, we need to ensure
that the aggregate of add and trans steps gets to keep taking steps as long
as anything is enabled, regardless of what removes occur.
But I can't think of a way to say this simply.


%%%%%%%%%% PROBLEM %%%%%%%%%
% Source: kdmc
% Topic: Relations

\kproblem{relations7}
\ksource{kdmc}
\ktopics{Relations}
Let the relations $R$ and $S$ be binary relations on the set $\naturals$ of 
natural numbers.  Define $R$ as follows: 
$\forall (a, b) \in \naturals \times \naturals (a, b) \in R iff a \text{mod} 4 = b \text{mod} 4$.
Define $S$ as follows: 
$\forall (a, b) \in \naturals \times \naturals (a, b) \in R iff 2^{a} = b$.

\begin{problemparts}
\ppart
Prove that $R$ is $transitive$.
\ppart
Prove that $R$ is $symmetric$.
\ppart
Find $R \intersect S$.
\ppart
Let $T = S \composition R$.
\end{problemparts}



\newcommand{\transto}[2]{#1\ensuremath{\longrightarrow} #2}
\newcommand{\transfrom}[2]{#1\ensuremath{\longleftarrow} #2}
\kproblem{statemachines1}
\ksource{Nancy}
\ktopics{State machines, graphs}
\pts{15} Consider a state machine whose state is a directed graph with
the 5-element vertex set $V=\set{1,2,3,4,5}$.  Initially, the state is
that of the ``linear graph'' ($1\longrightarrow 2\longrightarrow
3\longrightarrow 4\longrightarrow 5$).  The transitions allowed by the
state machine are the following:
%
\begin{itemize}
\item remove(a,b):\par Can occur if there is an edge from a to b.\par
  Effect is to remove the edge.
\item add-out(a,b) (a,b distinct):\par Can occur if a has no incoming
  edges.\par Effect is to add the edge \transto{a}{b}.
\item add-in(a,b):\par Can occur if a has no outgoing edges.\par
  Effect is to add the edge \transto{b}{a}.
\item reverse(a):\par Can occur if either all the edges incident
  upon a are incoming, or all are outgoing.\par Effect is to reverse
  the direction of all edges incident on a.
\item trans(a,b,c) (a,b,c distinct):\par Can occur if there is an edge
  from a to b.\par Effect is to remove the edge.
\end{itemize}
%
State whether each of the following digraphs is reachable.  If it is,
then describe an execution that reaches it; otherwise, state an
invariant that can be used to show that the state cannot be reached.
Such an invariant must be provable by induction (or the Invariant
Theorem).  Instead of giving a proof of the invariant, just state key
reasons.

\ppart The graph that is the same as the line graph above, but with
the additional edge \transto{5}{1}.

\solution{Not reachable.  The invariant is that the graph in the state
  is always acyclic.}

\ppart The line graph in the opposite direction ($1\longleftarrow
2\longleftarrow 3\longleftarrow 4\longleftarrow 5$).

\solution{Reachable: reverse(1), reverse(2), reverse(1), reverse(3),
  reverse(2), reverse(1), reverse(4), reverse(3), reverse(2),
  reverse(1).}

\ppart Now suppose we have the same state machine, but without the
remove and reverse transitions. We want to prove that, eventually, a
transitively closed graph is produced.  Assume that we are considering
a ``live'' execution, i.e. one that does not stop as long as any
transition is possible.

Define a termination function that can be used to prove this
eventuality property.  Argue that it satisfies the properties of a
termination function.

\solution{$f(n)=n(n-1)-\#\textrm{edges}$ is such a termination
  function.  Without remove and reverse, every transition adds an edge
  to the graph, decreasing this function.  When no transition is
  possible, the graph must be transitively closed, because we have an
  explicit transitive-closure step.}

%%% combinatorics %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \kproblem{combinatorics1}
\pts{10}
\ksource{Nancy's brain}\ktopics{Combinatorics} Prove
  combinatorially that the number of even-sized subsets of a set
  $S\not=\emptyset$ is equal to the number of odd-sized subsets.
  Formally, denoting by $E$ the even-sized subsets of $S$ and by $O$
  the odd-sized subsets of $S$, construct a bijection between $E$ and
  $O$.  \hint{Although there is a natural bijection that works for all
    $S$, you may find it clearer to divide the bijection into one that
    works for even-sized $S$ and one that works for odd-sized $S$.}

\solution{Our mapping $f:E\rightarrow O$ complements the presence of
  some arbitrary element in the input set; i.e., choose some element
  $e\in S$ so that $f(X)=X\cup\set{e}$ if $e\not\in X$, or
  $f(X)=X-\set{e}$ if $e\in X$.  We must prove the function is defined
  on its domain, is one-to-one, and is onto.
  
  \textit{$|X|$ even-sized $\Rightarrow |f(X)|$ odd-sized.}  Clearly
  $|f(X)|=|X|\pm 1$, so if $X$ is even-sized, then $f(X)$ is
  odd-sized.
  
  \textit{$f$ one-to-one.}  Assume $f(X)=f(Y)$.  If $e\not\in f(X)$
  and $e\not\in f(Y)$, then $X=f(X)\cup\set{e}$ and
  $Y=f(Y)\cup\set{e}$, so $X=Y$; otherwise, if $e\in f(X)$ and $e\in
  f(Y)$, then $X=f(X)-\set{e}$ and $Y=f(Y)-\set{e}$, so again $X=Y$.
  
  \textit{$f$ onto.}  Consider an odd-sized set $Y$: if $e\not\in
  Y$, then $|Y\cup\set{e}|$ is even-sized, so $f(Y\cup\set{e})=Y$;
  otherwise, if $e\in Y$, then $|Y-\set{e}|$ is even-sized, so
  $f(Y-\set{e})=Y$.}

%%% combinatorics %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\kproblem{combinatorics2}\ksource{David Gries' book, Eg. 16.36}\ktopics{Combinatorics,
  permutations w/limited repetition of a multiset} Let $n=2k$, for
some $k\geq 0$.

\bparts

\ppart Prove \textit{combinatorially} that $n!/2^k$ is an integer.

\solution{Consider a multiset with two of each of $k$ distinct
  elements.  The number of permutations with limited repetition of
  this set is $n!/(\underbrace{2!2!\cdots 2!}_{k})=n!/2^k$, which must
  be an integer.}

\ppart Prove the same theorem algebraically.

\solution{$n!=(2k)!=(\underbrace{2k}_{\mathrm{even}})
  (\underbrace{2k-1}_{\mathrm{odd}})
  (\underbrace{2k-2}_{\mathrm{even}})
  (\underbrace{2k-3}_{\mathrm{odd}}) \cdots (2)(1)$. There are $k$
  even factors, so $2^k|n!$.}

\eparts

%%% combinatorics %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\kproblem{combinatorics3}\ksource{Kyle's brain}\ktopics{Combinatorics, binomials,
  product rule} \textbf{Theorem.}
\[ 2^{n-3}\prod_{i=1}^{n-3} 2^i = 2^{\binom{n}{2}-n} \]

\bparts

\ppart Give a combinatorial proof of the theorem. \hint{Consider a
  graph represented by a circle of $n$ nodes where there are no edges
  between directly adjacent nodes.}

\solution{Consider the RHS: there are $\binom{n}{2}$ edges between
  nodes in a complete graph, but only $\binom{n}{2}-n$ when the edges
  forming the outside of the circle are not considered.  Thus, there
  are $2^{\binom{n}{2}-n}$ such possible graphs on $n$ nodes.
  
  Now, consider the LHS: number the nodes in some way, and start with
  the first two.  Each has $n-3$ possible edges to other nodes: not to
  itself, and not to either of its two neighbors.  So, there are
  $2^{n-3}$ possible subsets of the edges from each of these two
  nodes.  The third node has $n-4$ edges that don't intersect with the
  first two sets: not to itself, not to either of its two neighbors,
  and not to the first node; thus, there are $2^{n-4}$ possible edge
  subsets.  The fourth node has $n-5$ edges that don't intersect with
  the first three sets: not to itself, not to either of its two
  neighbors, not to the first node, and not to the second node; so
  $2^{n-5}$ possible edge subsets.  And so on.

  By the product rule, this is $2^{n-3}\cdot 2^{n-3}2^{n-4}2^{n-5}\cdots=
  2^{n-3}\prod_{i=1}^{n-3} 2^i$.}

\ppart Give an algebraic proof of the theorem.

\solution{\begin{eqnarray*}
    2^{n-3}\prod_{i=1}^{n-3} 2^i
    &=& 2^{n-3 + \sum_{i=1}^{n-3} i} \\
    &=& 2^{n-3 + (n-3)(n-2)/2} \\
    &=& 2^{(2n-6+n^2-5n+6)/2} \\
    &=& 2^{(n^2-3n)/2} \\
    &=& 2^{(n(n-1))/2 - n} \\
    &=& 2^{\binom{n}{2} - n}
  \end{eqnarray*}}

\eparts

%%% combinatorics %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\kproblem{combinatorics4}
\pts{14}
\ksource{Kyle's brain}\ktopics{Combinatorics, basic
  probability, product rule} \textbf{Theorem.}  Let $0\leq p_i\leq 1$
for all $i\in\set{1,\ldots, n}$.  Then,
\[ \sum_{S\subseteq \set{1,\ldots,n}} \kparen{\kparen{\prod_{j\in S}
    p_j}\kparen{\prod_{j\not\in S} (1-p_j)}} = 1 \] Note that
$\sum_{S\subseteq T}$ means to sum over all possible subsets $S$ of
$T$.

\bparts

\ppart 
\pts{6}
Give a combinatorial proof of the theorem.  \hint{Consider
  choosing an element from $\set{a_1,b_1}\times \set{a_2,b_2}\times
  \set{a_3,b_3}\times\cdots\times \set{a_n,b_n}$ where we have a
  probability $p_i$ of choosing $a_i$ for the $i\kth$ element of the
  tuple.}

\solution{Use the hint given.  For a given subset $S$ of the indices
  $\set{1,\ldots,n}$, the summand is the probability of choosing $a_i$
  for the indices in $S$ and $b_i$ for the indices not in $S$.  Since
  this covers exactly the possible ways of choosing a tuple given
  these probabilities, the total probability must be 1.}

\ppart 
\pts{8}
Give an algebraic proof of the theorem.  \hint{Use induction.}

\solution{Base case: When $n=1$, we have
  \[ p_i+(1-p_i) = 1 \]
  
  Inductive case: Assume the theorem for all $n\leq N$.  Now we must
  prove it for $N+1$.
  %
  \begin{eqnarray*}
    \sum_{S\subseteq\set{1,\ldots, N+1}} \kparen{\kparen{\prod_{j\in S}
        p_j}\kparen{\prod_{j\not\in S} (1-p_j)}}
    &=& \sum_{S\subseteq\set{1,\ldots, N}}
    \kparen{\kparen{p_{N+1}\prod_{j\in S} 
        p_j}\kparen{\prod_{j\not\in S} (1-p_j)}} \\
    && +
    \sum_{S\subseteq\set{1,\ldots, N}} \kparen{\kparen{\prod_{j\in
          S} p_j}\kparen{(1-p_{N+1})\prod_{j\not\in S} (1-p_j)}} \\
    &=& p_{N+1}\sum_{S\subseteq\set{1,\ldots, N}}
    \kparen{\kparen{\prod_{j\in S} 
        p_j}\kparen{\prod_{j\not\in S} (1-p_j)}} \\
    && +
    (1-p_{N+1})\sum_{S\subseteq\set{1,\ldots, N}} \kparen{\kparen{\prod_{j\in
          S} p_j}\kparen{\prod_{j\not\in S} (1-p_j)}} \\
    &=& p_{N+1}\cdot 1 +
    (1-p_{N+1})\cdot 1 \\
    &=& 1
  \end{eqnarray*}}

\kproblem{combinatorics5}
\ksource{nancy}
The following is a true identity for binomial coefficients:
\\
$\Sigma_{k=1}^n k \binom{n}{k} = n 2^{n-2}$. \\

\textbf{kyle says we've already used this one.  maybe just give part (c), then}

(a) Give a combinatorial proof of this identity.

Ans:  Committee of any size plus a chairman.

(b) Give an analytical proof.

Ans:  Starting with the sum, expand the binomial coefficient factor, pull out the
n from the sum, and re-express the sum as

$\Sigma_{k=1}^n \binom{n-1}{k-1}$.

This is the same as

$\Sigma_{k=0}^n-1 \binom{n-1}{k}$.

Binomial theorem says that's just $2^{n-1}$.


(c) 
Using an extension of your combinatorial reasoning in (a), can you give
a closed-form expression for 

$\Sigma_{k=1}^n k^2 \binom{n}{k}$ ?

Ans:  Think of this as the number of different committees (of any size) 
with two distinguished members (president and vp), but where both offices
can be held by the same person.

Can break this down into two terms:
the number of such configurations having both officers the same:
  $n 2^{n-1}$ (same as above).
plus
the number of such configurations having different officers:
  $n(n-1)2^{n-2}$


%%% expectation %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\kproblem{expectation1}\pts{12}\ksource{Nancy's brain}\ktopics{Expectation, linearity
    of expectation, expected number of events that occur, binomial
    distribution, counting permutations}
 
  Each of 5 students in 6.042 chooses a natural number in the range
  $[1,\ldots,5]$, randomly and independently, using the uniform
  distribution on $[1,\ldots,5]$.
  
  \ppart\pts{3} What is the expected number of people who choose the
  number that gives their position in alphabetical order?
 
  \solution{$1$}
 
  \ppart\pts{3} Give an expression representing the probability that
  exactly the expected number of people (as given by your answer to
  the previous part) choose their correct positions.

  \solution{$\underbrace{\binom{5}{1}\frac{1}{5}}_{\mathrm{Winner}}
    \underbrace{\left(\frac{4}{5}\right)^4}_{\mathrm{Losers}}$}
  
  Now suppose the 5 students are all assigned numbers in the range
  $[1,\ldots,5]$ by a course TA, who chooses randomly from the uniform
  distribution on permutations of $[1,\ldots,5]$.
 
  \ppart\pts{3} Now what is the expected number of people who are
  assigned the number that gives their position in alphabetical order?
 
  \solution{$1$}
 
  \ppart\pts{3} Give an expression for the probability that exactly
  the expected number of people (as given by your answer to the
  previous part) are assigned their correct positions.
 
  \solution{This is more complicated, and a little too ad hoc for my
    taste.  Maybe need hints?
 
    I calculate that there are 45 5-permutations in which exactly one
    guy is a "fixed point", which gives a probability of $45/120$, or
    $3/8$.  To get the 45, I figure 5 choices for the fixed point, then
    9 4-perms with no fixed point.  But, to figure out that there are
    exactly 9 4-perms with no fixed point, I used slightly ad hoc
    arguments: 3 possibilities for who gets the number 1; then for
    each of these, say the guy with rank $i$, three possibilities for
    who gets the number $i$; after these two are assigned, it turns out
    that the final assignments have only one possibility.
 
    In trying to generalize this, I got a somewhat messy recurrence.
    So I'm inclined just to leave it as an ad hoc calculation.  OK
    since the numbers are very small.  Or, we can give them the 9 as a
    hint.
 
    I was hoping to get a comparison between these two experiments,
    but don't see anything nice here.  Is it clear which of the two
    kinds of experiments should yield the higher probability of
    getting exactly one fixed point?  Here, the probability is higher
    in the case of the first experiment ($.4096$ vs. $.375$).  In
    general?}

\eparts

%%% expectation %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\kproblem{expectation2}\pts{10}\ksource{Nancy}\ktopics{Expectation}
100 students enter a cafeteria with very large tables, one at a time.
As each students enters, he or she looks around to see if any of his
friends are already there.  If so, he/she joins one of his friends'
tables.  If not, he/she starts a new table.

Assume that, for each pair of students, the probability that they are
friends is $p$.  Moreover, all these pair probabilities are
independent.

\ppart For the $i\kth$ person to enter the cafeteria, what is the
probability he/she starts a new table?

\solution{$(1-p)^{i-1}$}

\ppart What is the expected number of occupied tables after everyone
has entered? 

\solution{Add this from $i = 1$ to $n$.}

\kproblem{expectation3}
\ksource{David R's Brain}
\ktopics{Expectation, product rule}
There is a casino in St. Petersburg
where you have the choice of betting any portion of your wealth on
either of two games: in the first game, you either receive 3 times
what you bet or lose it all with equal probability.  In the second
game the casino gives you 1.4 times what you bet with probability 1
(this casino is understandably very popular).  Each trial of the two
games are played simultaneously.

\bparts

\ppart Call $S_1$ and $S_2$ the fraction of your wealth you bet on the
two games (notice $S_1+S_2\leq 1$).  What values of $S_1$ and $S_2$
maximize the expected value of your wealth after 1 trial?  What is the
maximum expected value of your wealth?
\solution{$S_1=1$, max is 1.5}

\ppart What strategy maximizes your expected wealth after $n$ trials?
\solution{Always have $S_1=1$}

\ppart Using that strategy, what is the probability that after 10 trials, you have more money than you started with?
\solution{$1-2^{-10}$}

\ppart After $2n$ trials, what is the {\em most likely} number of
trials in game one that are wins.  And what is the probability that
this occurs?
\solution{$n$, $f_{2n,0.5}(n)\approx $}

\ppart What fraction of your wealth should you bet on each trial of
the two games, if you want to maximize your wealth after $2n$ trials
in the most likely case that you found above? (i.e. suppose that there
are that number of wins over the course of the $2n$ trials).  Assume
that it is in your interest to have $S_1+S_2=1$.
\solution{Maximize $(1.4+1.6S_1)^{0.5}(1.4-1.4S_1)^{0.5}$ over $S_1$.  $S_1=0.0625$.}
\eparts


%%% wald's theorem %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\kproblem{expectation4}\pts{10}\ksource{Nancy}\ktopics{Wald thm.} The number of
students that will enter LaVerde's to buy junk food on Tuesday night
of finals week is a random variable taking on an integer value from
$\set{0,\ldots,100}$ uniformly.  Each student who enters picks at
least one kind of junk food.  After choosing each kind of junk food, a
student is equally likely to continue choosing more kinds of junk food
or to quit and go pay at the checkout register.  Students' decisions
to continue buying are mutually independent.

The checkout clerk throws a fair die for each item and then charges
the number of dollars that shows up.

What is the expected number of dollars spent by students on junk food
at LaVerde's on Tuesday night?

%% Wald's Theorem
% From Fall98 sample problems
\kproblem{wald1}
\ksource{victor}
\ktopics{Wald's theorem}
A miner, lost in some abandoned mine, finds himself in a room 
containing three doors.  Door 1 leads him to freedom after two 
hours travel; door 2 returns him to the same room after four hours travel, and 
door 3 returns him to the room after eight hours travel.
Each time he finds himself in the room, 
the miner picks a door with equal probability.  
Let $T$ denote the time until he finds the exit. \\

\bparts

\ppart Define a sequence of iid random variables $X_i$ and a stopping rule 
$N$ such that
% Have we defined stopping rule?
\[T = \sum_{i=1}^{N}{X_i}\]


\solution{
We view this as an experiment where at each step we make a choice between
three equiprobable outcomes.

Let $X_i$ = number of hours to return to room on $i$th step.

Let $N$ = number of steps until good door is selected.

Then $N$ is geometrically distributed with probability $1/3$.
}

\ppart Use Wald's Identity to find $\Ex[T]$

\solution{
$\Pr(X_i = 2) = 1/3$

$\Pr(X_i = 4) = 1/3$

$\Pr(X_i = 8) = 1/3$

$\Ex[X_i] = 14/3$

$\Ex[N] = 3$

By Wald's Identity

\[
\Ex[\sum_{i=1}^N X_i] = 14
\]
}

\eparts   


%%% markov and chebyshev bounds %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\kproblem{markov1}\pts{16}\ksource{Nancy}\ktopics{Markov and Chebyshev Bounds}
The average IQ of all MIT faculty is known to be exactly $150$.

\ppart Give a tight upper bound on the probability that a random MIT
faculty member's IQ is $175$ or more.

\solution{Use Markov, get $\leq 150/175 = 6/7$}

\ppart Give an example distribution of weights showing that your bound
in the first part is tight.

\solution{6 faculty members with IQ 175, one with IQ 0.}

Now assume also that the standard deviation of IQs of MIT
faculty members is 25.

\ppart Give a tight upper bound on the probability that a random MIT faculty 
member's IQ is 175 or more, taking this new information into account.

\solution{Use one-sided Chebyshev}

\ppart Give an example distribution of weights showing that your bound
in the previous part is tight.

\solution{LTTR}

%% Bounding deviation from the mean
\kproblem{markov2}
\ksource{victor}
\ktopics{Markov and Chebyshev bounds}
There are sixty people in a basketball league. 
No one is shorter than 5'6'', nor is anyone taller than 6'6''. 
The average height is 5'10''. 

\bparts

\ppart
Without any other information, 
what is the best possible upper bound 
for the number of people taller than 6'4''? 

\solution{Use Markov's bound.  The answer is 40\%, I believe, 
so twenty-four people.}

\ppart
Without any other information, 
what is the best possible upper bound 
for the number of people who are 5'6''?

\solution{Markov again, this time flipping the variable. 
I believe the answer is $8/12 = 2/3$, 
so forty people.} 

\ppart
You are now told that the standard deviation 
of the heights of these sixty people is 2''.
What is the best upper bound you can give now 
for the two previous parts?

\solution{Use one-sided Chebyshev inequality: 
$\Pr(H - 5'10'' > 6'') \leq \frac{\variance{H}}{\variance{H} + 6^2}
                        = 2/38 = 1/19$. 
So at most $\floor{60/19} = 3$ people who are at least 6'4''. 

$\Pr(5'10 - H > 4'') \leq \frac{\variance{H}}{\variance{H} + 4^2}
                        = 2/18 = 1/9$. 
So at most $\floor{60/9} = 6$ people who are 5'6''.
%Can we do better because we can bound the deviation from 
% the mean?
}

\eparts


\kproblem{pmethod1}
\pts{12}
\ksource{Nancy}
\ktopics{Probabilistic Method}
Consider n players in a round-robin tournament.  We are going to
consider the question of whether there exists a possible tournament
outcome (that is, a tournament digraph) in which every player wins at
least two matches (that is, every node in the digraph has at least two
outgoing edges).  We would like you to use the probabilistic method to
show that such an outcome exists, for certain values of $n$.  

\bparts

\ppart Say a match between two players---$a$ and $b$---is won by $a$
with probability $1/2$ and by $b$ with probability $1/2$.  What is the
probability that a particular player wins no more than one game?

\solution{$\frac{n}{2^{n-1}}$, since there are $n$ ways to win no more
  than one game---$1$ way to win zero, $n-1$ ways to win 1 versus
  $n-1$ opponents---out of $2^{n-1}$ possible ways to win/lose $n-1$
  games.}

%Ans:  I get (n+1) over 2^{n-1}.  Check me. 

\ppart Now, upper bound the probability that \textit{some} player wins
no more than one game.

\solution{By the union bound, this is just $\frac{n^2}{2^{n-1}}$.}

\ppart Lower bound the probability that \textit{all} players win at
least two games.

\solution{This is just the complement of the previous part, so
  $1-\frac{n^2}{2^{n-1}}$.}

\ppart Show a condition implying a positive probability of
\textit{all} players winning at least two games.

\solution{$1-\frac{n^2}{2^{n-1}} > 0$.}

\ppart Explain \textit{briefly} why your condition implies the
existence of such a tournament.

\solution{If there is a non-zero probability of such an event
  occuring, then there must be a configuration in which that event
  occurs.}

\eparts

\end{problems}  


\end{document}

