%% Note to Reader:  The questions in this file are divided into 2 parts:
%% problems that are `READY FOR SUBMISSION' or `STILL IN PROGRESS'.  You can 
%% grep for the terms in quotes to find the beginning of each section.

%% I would want to modify each of these problems and reduce the set size
%% by choosing the best ones.

%% done?
%%  **  RECURSIVE DEFINITIONS %%
%%  **  STRUCTURAL INDUCTION %%
%%  **  WELL-ORDERING %%
%%  **  RELATIONS/POSETS/EQUIVALENCE RELATIONS %%
%%  **  GRAPHS %%
%%  **  STARS AND BARS %%
%%  **  COMBINATIONS WITH REPITION %%
%%  **  BINOMIAL COEFFICIENTS %%
%%    INFINITY %%

\documentclass[11pt, twoside]{article}

\usepackage{graphics}
\usepackage{psfig}

\input{macros-course}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Printing the page layout parameters

\printlayout

\askaboutsolutions

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


\ifshowsolutions
  \newcommand{\reading}[1]{}
%
  \newcommand{\handoutlabel}{sol10}
  \newcommand{\handouttitle}{Ken Sol}
  \newcommand{\handoutdate}{\today}
  \newcommand{\collaboration}{}
  \newcommand{\titlebar}{\handout{\handoutlabel}{\handouttitle}{\handoutdate}}
%
\else
  \newcommand{\reading}[1]{%
%    \mbox{}\\ %
    \hrule\mbox{} \\ %\bigskip %
    #1%
%    \mbox{} \\ %\bigskip %
    \hrule %
    %\vfill\mbox{}\newpage%
    }
%
  \newcommand{\handoutlabel}{ps10}
  \newcommand{\handouttitle}{Ken}
  \newcommand{\handoutdate}{\today}
  \newcommand{\duedate}{May 2, 2000}
  \newcommand{\collaboration}{\collaborationnote}
  \newcommand{\titlebar}{%
    \handout{\handoutlabel}{\handouttitle}{\handoutdate}
    \centerline{{\bf Due  Date: \duedate.}}
    \vspace*{\baselineskip}}
%
\fi


\renewcommand{\solution}[1]{%
  \ifshowsolutions %
  \medskip
  \textbf{Solution.} \par %
  #1
%  \mbox{} \\
%  \mbox{}\hrulefill\hspace*{1ex}\ignorespaces%
%  \raisebox{-0.25\baselineskip}{$\square$}%
%  \hspace*{1ex}\ignorespaces\hrulefill%
%  \nopagebreak%
  \fi}


%\newcommand{\solutionname}{Solution}
%\renewenvironment{solution}[1][\solutionname]{%
%  \par
%  \normalfont
%  \topsep6\p@\@plus6\p@ \trivlist
%  \item[\hskip\labelsep\bfseries
%    #1\@addpunct{.}]~~\ignorespaces
%}{%
%\mbox{} \\
%\mbox{}\hrulefill\hspace*{1ex}\ignorespaces%
%\raisebox{-0.25\baselineskip}{$\square$}%
%\hspace*{1ex}\ignorespaces\hrulefill%
%\nopagebreak%
%}

%\renewcommand{\solution}[1]{%
%  %\begin{solution}
%    #1
%  %\end{solution}
%  }

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


\begin{document}

\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}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% READY FOR SUBMISSION %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%

\begin{problems}

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

% kdmc: Should this be modified?
% use
\problem 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/spring97.tex (modified by kdmc)
% Topic: Fibonnacci Numbers, Well Ordering, Strong Induction

% use
\problem 
Back in 1996, a group of young Harvard graduates founded the 
startup NewMoney.com in anticipation of the need for a new currency upon 
the colonization of Mars in the year 2001.  The proposed form of
currency, the \emph{Gork}, was originally printed only as a \$6-Gork coin 
and a \$15-Gork paper bill.
What quantities of money (in Gorks) can be formed from just this currency? 
\newline
\solution{
{\bf: Answer A.}
The answer is $6$ and all multiples of three greater then 
or equal to $15$.

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

{\bf: Answer B.}
  First of all notice that if we can make $n$ Gorks using only coins
  and bills then $n=6a+15b = 3(2a+5b)$ for some $a$ and $b$,
  and therefore $n$ must be a multiple of $3$.
  We can make $6$ Gorks using one coin, and we can make 
  neither $3$ nor $9$ Gorks.
  We claim that we can make any other quantities $n$ 
  such that $n\geq 12$ and $3|n$.
  In other words, we can make $12+3k$ Gorks 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 15$.
Clearly, if $n \leq 15$ then  we  can make $6$ from one coin,
$12$ from two coins, and $15$ from one bill.

{\sc Inductive Step:} Let $n\geq 15$ and assume that for 
all $15<m<n$ we can make $m$ Gorks out of coins and bills.
Show that we can make $n$ Gorks out of coins and bills.

If $n > 15$ then we know that $n-6 > 9$ and by the base cases and 
the inductive hypothesis, we know that we can make $n-6$ Gorks using only
coins or bills.  We can therefore make $n$ Gorks by adding
a coin, so we can make $n$ Gorks out of coins and bills.

This completes the inductive step, so we know we can make $n$ Gorks
out of coins and bills where $n=6$ or $n \geq 12$ and $n$ is a multiple 
of 3.

Now, we need to show that we cannot make any other amounts using only
coins and bills.  Take first the case of $3$ Gorks:  We clearly cannot
make $3$ Gorks because coins and bills are both larger than $3$ Gorks.
We also cannot make $9$ Gorks, by inspection.

We cannot make amounts that are not divisible by $3$ because any 
combination of coins, $c$, and bills, $b$, will give us 
$d=6c+15b =3(2c+5b)$, which is clearly a multiple of $3$ when 
c and b are natural numbers.

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

  {\sc Inductive Step ($k\geq 2$):}
  Assume we can make $12+3h$ Gorks for all $h<k$.
  In particular we can make $12+3(k-2)$ Gorks using 
  coins and bills. 
  Using one more coin, we can also make 
  $12+3(k-2) + 6=12+3k$ Gorks, 
  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 (3|n \wedge n\geq 20)''$,
and let $Q(n)$ be the predicate ``we can make $n$ Gorks using 
coins and bills''.

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

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 $3$,
but we cannot make $m$ Gorks using coins and bills.
Notice that $m$ must be greater then or equal to $18$
because $6,12$ and $15$ Gorks can be made using 
respectively $1,2$ coins or a bill.
Let $n=m-6$.
We cannot make $n$ Gorks using coins and bills
because otherwise we could also make $m=n+6$ Gorks
using one more coin. So, $Q(n)$ is false.
Moreover, $m\geq 18$ and therefore $n\geq 12$.
Since $n$ is a multiple of $3$,
$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$ Gorks using coins and bills.
We distinguish two cases:
\begin{itemize}
\item if we used at least one dime to make $m$, 
 then we can also make $n=m-6$ cents using one less dime, 
 i.e., $Q(n)$.
 Moreover, $\neg P(n)$ because otherwise 
 also $m=n+6$ satisfies $\neq P(m)$ (if we add $6$ to a multiple of 
 $3$ it will still be a multiple of $3$).
 So, $n\in T$ contradicting that $m$ is minimum.
\item if we didn't use any coins to make $m$,
 then $m=15h$ and $P(m)$ which contradicts $m\in T$.
\end{itemize}

{\bf: Answer B.}
  We prove that we can make $12+3k$ cents 
  using coins and bills by well ordering.
  Let $S$ be the set of all $k$ such that 
  we cannot make $12+3k$ Gorks using coins and bills
  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 
  $12$ and $15$ Gorks. 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 $12+3(m-2) = 12+3m -6$
  Gorks using coins and bills, then we could make also 
  $12+3m$ Gorks using one more coin.
  But, this is impossible because $m\in S$.
  So, $m-2\in S$ and $m$ is not the minimum.
}
\end{problemparts}

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

% use
\problem
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)$.
\emph{not done yet}
}
\end{problemparts}

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

% use
\problem
Let $R$ be the lexicographic ordering of strings of symbols
from a totally ordered alphabet as defined in Rosen p. 417.

% kdmc: define lexicographic ordering from Rosen 417 in the problem

\begin{problemparts}

\problempart 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.
}

\problempart 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}

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

% use
\problem 
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}
\problempart
strong induction,
\solution{
}
\problempart
well ordering,
\solution{
}
\problempart
weak induction.
\solution{
}
\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/fall94.tex
% Topic: Graphs

% use
\problem 
Prove that in any undirected graph, the sum of the squares of
the vertex degrees is even, or provide a counterexample.
\solution{
Note that $\forall d \in range(degree) d \geq 0$.
We first prove that $\sum_{v \in V}{(degree(v))}^{2}$ is even iff 
$\sum_{v \in V}{degree(v)}$ is even.
We argue that $\forall x \in \naturals x^{2}$ is even iff $x$ is even.
Furthermore, we can show that for any sum of non-negative naturals that sum is
even iff there is an even number of odd terms in the sum.  Since we have 
shown that the number of odd terms has not changed from the former sum to the 
latter sum, the problem can be reduced to dealing with the latter sum 
(henceforth, the ``sum'').  We know that there is an integral number of edges 
in the graph.  For each edge, we count it twice in the sum.  Therefore,
$sum_{v \in V}{degree(v)} = 2 \abs{E}$, which is clearly even.  The sum of the
squares of the vertex degrees is even for any undirected graph.
}

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

% use
\problem 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.)
\solution{
\emph{not done yet}
}


%%%%%%%%%% PROBLEM %%%%%%%%%
% Source: kdmc
% Topic: Stars and Bars

% use
\problem
\begin{problemparts}
\problempart
In how many ways can fourteen {\em indistinguishable} balls in 
five {\em distinguishable} boxes given no restraints on capacity of the boxes.
\solution{
This is the normal stars and bars, for n bins (bars) r balls (stars).
${(n+r-1) \choose r}={(5+14-1) \choose 14}={18 \choose 14}={18 \choose 4}$
}
\problempart
Consider the case where you want to place fourteen {\em distinguishable} 
balls in five {\em distinguishable} boxes given no restraints on the capacity
of boxes.
\solution{
$\frac {factorial(18)}{factorial(4)}$
}
\problempart
Now count the number of ways to place fourteen {\em indistinguishable} balls 
in five {\em distinguishable} boxes given that each box contains at least one 
and at most five balls.
\solution{
You can first remove $5$ balls from the game since each box contains at least 
one ball, and the new requirements become boxes containing at least $0$ and 
at most $4$ balls.  We are now left with placing $9$ balls into $5$ boxes.
Let's ignore the capacity limit for the moment.  We have $5^{9}$.  Now we need
to subtract from that each of the cases where we have more than $4$ balls in 
a particular box.  There are ${4 \choose 1}$ combinations of boxes that could 
have more than $4$ balls at the same time, since at most one can have more 
than $4$.  Thus we want to subtract \emph{can't compile formula}
\[
{4 \choose 1}\ \sum_{i=0}^{4}{5^{i}}
\]
.
The total number of combinations is \emph{can't compile formula}
\[
5^{9} - 4 \sum_{i=0}^{4}{5^{i}}
\]
.
}
\end{problemparts}

%%%%%%%%%% PROBLEM %%%%%%%%%
% Source: kdmc
% Topic: Calculating Coefficients With the Binomial Theorem

% use
\problem
Find the coefficients of each of the following terms in the given polynomial
expansion that follows:
\begin{problemparts}
\problempart 
$x^4$ in $(2+x)^{13}$
\newline
\solution{
${13 \choose 4} 2^{4}$
}
\problempart 
$x^25$ in $(2x+3 \frac x)^{46}$
\newline
\solution{
${46\choose 28} 2^{28} 3^{46-28}$
}
\problempart 
$x^7y^12$ in $(4x+5y)^{19}$
\newline
\solution{
${19\choose 7}(4^{7})(5^{12})$
}
\problempart 
$x^3y^4$ in $(2x+4y^{2})^{5}$
\newline
\solution{
$2^{3} (4^{2}) {5\choose 3}$
}
\end{problemparts}

%%%%%%%%%% PROBLEM %%%%%%%%%
% source: fall94 ps7
% topic: Binomial Theorem

% use
\problem Let $n, r\in\naturals$.
Use the binomial theorem to evaluate the expressions in closed form
\begin{problemparts}
\problempart
\[
\sum_{k=0}^{n}{n \choose k}r^k  
\]
\newline
\solution{
Equivalent to 
\[
\sum_{k=0}^{n}{n \choose k} (r^{k}) (1^{n-k})= (1+r)^{n}
\]
}
\problempart
and 
\[
\sum_{k=0}^{n}{n\choose k}(-r)^k
\]
%       (\hint $(-1)^k = \pm (-1)^{n-k}$.)
\newline
\solution{
Again, as before, at the term $1^{n-k}$ to each term in the sum.
$(1-r)^{n}$
}
\problempart
Use your analysis to conclude that if $r$ is odd, then
\[\left. 2^{n-1} \;\right| \sum_{\stackrel{\scriptstyle k=0}{k {\mathrm{\ even}}}}^{n}{n\choose k}r^{k}\ .\]

Note that if $r=1$, this sum simply counts the number of even-sized
subsets of an $n$-set, which we know is exactly $2^{n-1}$.
\newline
\solution{
\emph{not done yet}
}
\end{problemparts}

%%%%%%%%%% PROBLEM %%%%%%%%%
% Source: kdmc
% Topic: Combinations with Repitition

% kdmc: Maybe this should be simplified a bit?

% use
\problem
Using recently acquired probability skills from 6.042, Theory Moose has been 
at the casino ever since he turned in his last problem set.  However, he feels
the dealers are on to him and he skips town to buy out a department store and 
a plane ticket to paradise (aka 6.046).  Theory Moose must act quickly to 
choose his new wardrobe from the department store, but before he can make a 
decision he stops to solve one more problem.
Theory Moose is taking 6 tshirts, 4 pairs of shorts, and, of course, a pair 
of shades.  How many different combinations of colors can he come up with 
given the following constraints:
\begin{description}\itemsep 0\baselineskip
\item \mbox{} The department store has the following colors available for \\
each of the eleven items, with replacement: red, green, white, and black.
\item \mbox{} If he takes black-frame shades, at least $2$ of the shorts he \\
takes must be white.
\item \mbox{} If he is taking more than $3$ red tshirts he won't take any \\
green with him at all.
\end{description}
\solution{
There are four colors from which to choose for items.  If Theory Moose chooses
enough red tshirts, his choices are constrained to not be green.  There are 
$4^{6}$ combinations of tshirts if they can be any combination at all of the 
four colors.  Suppose Theory Moose chooses all his red tshirts first.  If he 
has more than $3$ red tshirts the rest can't be green.  We say we are 
``uncounting'' when Theory Moose has at least $4$ red tshirts.  The number of
valid tshirt combinations given that we are ``uncounting'' is $6$.  The 
number of invalid tshirt combinations given that we are ``uncounting'' is 
$4$.  The total number of tshirt combinations for which we are ``uncounting'' 
is $6+4=10$.

Let us consider the special situation where we are ``uncounting''.  If he has
black shades, the number of combinations of shorts left is $3^{2}$.  If he has
shades of the remaining $2$ colors, the number of combinations of shorts left 
is $3^{4}$.  Thus, the total number of combinations of shorts-and-shades 
choices when we are ``uncounting'' is $3^{2} +2(3^{4})=171$.  The total number
of choices we want to keep even though we are ``uncounting'' is thus 
$3^2(171)=1539$.

Now let us consider the situation where we are not ``uncounting''.  In this 
case we have no restraints on the shorts-and-shades combinations other than 
those imposed on themselves.  If Theory Moose takes black shades, the number 
of combinations of shorts left is $4^{2}$.  If Theory Moose takes one of the 
other $3$ colors of shades, the number of combinations of shorts is $4^{4}$.  
Thus the total number of combinations of shorts-and-shades choices when we are
not ``uncounting'' is $4^{2} +3(4^{4})=784$.  The total number of choices we 
should count when we are not ``uncounting'' is thus 
$(4^{6} -10) 784=3203424$.

Therefore, the total number of outfits Theory Moose can wear to Paradise is 
$1539+3202424=3204963$.
}

%%%%%%%%%% PROBLEM %%%%%%%%%
% Source: check 18.100B text
% Topic: Infinity



%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% STILL IN PROGRESS %%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% 

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

\problem 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/spring97.tex, pset3/spring97sol.tex
% Topic: False Proofs, Well Ordering, Induction, 

\problem 
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}

%\endinput

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

\problem [10 pts]

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

\problem 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

\problem
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

\problem
% 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

\problem
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}

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

\problem
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}

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

\problem {\bf (15 points)} 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.

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

\ppart In your drawing, highlight a Hamiltonian circuit.

\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$.

\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/spring98.tex, pset3/spring98sol.tex (Problem 5)
% Topic: Simple Graphs, Induction, Well Ordering, Graph Coloring

\problem [30 pts]

{\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


%%%%%%%%%% PROBLEM %%%%%%%%%
% Source: 
% Topic: 

%%%%%%%%%% PROBLEM %%%%%%%%%
% Source: 
% Topic: 

%%%%%%%%%% PROBLEM %%%%%%%%%
% Source: 
% Topic: 

%%%%%%%%%% PROBLEM %%%%%%%%%
% Source: 
% Topic: 

%%%%%%%%%% PROBLEM %%%%%%%%%
% Source: 
% Topic: 

\end{problems}
\end{document}
\endinput

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

\problem 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

\problem Show that the Fibonnacci number $f_n$ satisfy $f_n \leq 2^n$
  using strong induction.

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

%%%%%%%%%% PROBLEM %%%%%%%%%
% Source: pset3/spring94.tex, pset3/spring94sol.tex (modified slightly)
% Topic: Graphs

% kdmc: too 6.046ey

\problem 
You have a collection of $n$ boxes that have the same
dimension but distinct weights.  Suppose you wish to find the heaviest
of $n$ boxes using only a balance which can tell you which of two
boxes is heavier.  A \defi{comparison} consists of using the balance
to compare the weights of two boxes.

\begin{problemparts}

\problempart Give an algorithm for determining the heaviest box using
$n-1$ comparisons.
\solution{
There are many ways to do this.
One way is to compare each untested box with the
heaviest box seen so far.
}
\problempart
%Prove that fewer than $n-1$ comparisons are not sufficient to
Prove that $n-1$ comparisons are necessary to
determine the heaviest box in the worst case.
Argue by looking at a directed graph on $n$
nodes---one node for each box---with an edge from node $u$ to node $v$
if a direct comparison showed that box $u$ was heavier than box~$v$.
\solution{
Consider the directed graph with  an edge from node $u$ to node $v$
if a direct comparison showed that box $u$ was heavier than box~$v$. 
If there are fewer than $n-1$ edges then the graph is not connected.
The nodes of the graph can therefore be partitioned into two disjoint
nonempty sets $V_1$ and $V_2$ such that there is no edge going from
a node in one set to a node in the other.
It is therefore possible that the boxes in $V_1$ are all heavier than
those in $V_2$ or vice versa, and so the heaviest box has not been 
determined.
}
\problempart Give an algorithm for determining both the heaviest {\em
and the second-heaviest} boxes using only $n+\lg n -2$ comparisons.
%	(\hint Single-elimination playoffs.)
\solution{
Compare the boxes as in a single-elimination playoffs tournament
like Wimbledon---create a full binary tree with $n$ leaves, as balanced
as possible so the depth is $\lg n$, and compare siblings, 
working your way from the bottom of the tree to the top.
Firstd determine the heaviest (the winner of the tournament, at the 
top of the tree).
The second-heaviest box can lose only to the heaviest,
so then determine the heaviest among the $\lg n$ boxes that lost
to the heaviest. 
The total number of comparisons is $n-1 + \lg n -1$.
}
\problempart Give an algorithm for determining both the heaviest and
the lightest boxes using only $\ceil{3n/2}-2$ comparisons.  
%	(\hint Process the boxes 2 at a time.)

Again, the tournament structure helps.
This time, we know that the lightest box must have lost in the first round.
So after determining the heaviest, determine the lightest of the $\ceil{n/2}$
boxes that lost in the first round.
The total number of comparisons is $n-1+\ceil{n/2}-1$.

\end{problemparts}