Index: kdmc.tex
===================================================================
RCS file: /a/class/6.042/spring00/repository/final/kdmc.tex,v
retrieving revision 1.8
retrieving revision 1.10
diff -r1.8 -r1.10
1,991d0
< \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 %%%
< %%%%%%%%%%%%%%%%%%%%%%%%%%%%
< 
< %
< 
< %%%%%%%%%%%%%%%%%%%%%%%%%%%%
< %%%% STILL IN PROGRESS %%%%%
< %%%%%%%%%%%%%%%%%%%%%%%%%%%%
< 
< % 
< 
< %%%%%%%%%% PROBLEM %%%%%%%%%
< % Source: kdmc
< % Topic: Relations
< 
< \kproblem
< 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) \or (x = 1 \land y \in M_2) \or \[(x = 2 \or x = 3) \land y \in M_0\]$
< }
< \end{problemparts}
< 
< %%%%%%%%%% PROBLEM %%%%%%%%%
< % Source: pset3/spring97sol.tex
< % Topic: Structural Induction, Recursive Definition (Binary Trees)
< 
< \kproblem 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 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 Show that the Fibonnacci number $f_n$ satisfy $f_n \leq 2^n$
<   using strong induction.
< 
< \solution{
< {\bf not done yet.}
< }
< 
< %%%%%%%%%% PROBLEM %%%%%%%%%
< % Source: pset3/spring97.tex
< % Topic: Fibonnacci Numbers, Well Ordering, Strong Induction
< 
< \kproblem 
< 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/fall95.tex, pset3/fall95sol.tex
< % Topic: Well Ordering (gcd, lcm)
< 
< \kproblem 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, 
< 
< \kproblem 
< 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 \textbf{Posets}
< 
< 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/fall94.tex
< % Topic: Recursive Definitions, Strong Induction, Well Ordering, Weak Induction
< 
< \kproblem 
< 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/spring98sol.tex, original source Rosen 7.3-32
< % Topic: Relations, Adjacency Matrix, Recursive Definitions
< 
< \kproblem [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
< 
< \kproblem 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
< 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
< % 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
< 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 %%%%%%%%%
< <<<<<<< kdmc.tex
< =======
< % Source: kdmc
< % Topic: Relations
< 
< \kproblem
< 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 %%%%%%%%%
< >>>>>>> 1.5
< % Source: 
< % Topic: 
< 
< %%%%%%%%%% PROBLEM %%%%%%%%%
< % Source: 
< % Topic: 
< 
< %%%%%%%%%% PROBLEM %%%%%%%%%
< % Source: 
< % Topic: 
< 
< %%%%%%%%%% PROBLEM %%%%%%%%%
< % Source: 
< % Topic: 
< 
< %%%%%%%%%% PROBLEM %%%%%%%%%
< % Source: 
< % Topic: 
< 
< %%%%%%%%%% PROBLEM %%%%%%%%%
< % Source: pset3/spring99sol.tex
< % Topic: Graphs, Recursive Definitions
< 
< \kproblem {\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/fall94.tex
< % Topic: Graphs, Well Ordering
< 
< \kproblem 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.)
< 
< %%%%%%%%%% PROBLEM %%%%%%%%%
< % Source: pset3/spring98.tex, pset3/spring98sol.tex (Problem 5)
< % Topic: Simple Graphs, Induction, Well Ordering, Graph Coloring
< 
< \kproblem [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