\documentstyle[12pt,twoside,macpsfig,amssymb]{article}
\input{macros-course}

\addtolength{\topmargin}{-.35in}
\setlength{\textheight}{9in}

\begin{document}

\pset{3}{September 20, 1994}{In tutorial, September 26 and 27}

{\bf Reading:\ } [CLR] Chapter 5 (Handout~\ref{clrchap5}) 
	and [MR] Sections 3.1--3.2.

\bigskip\bigskip

\noindent
{\bf A word on proofs and definitions.}\\ \indent
In some problems, we use terms that we have not defined precisely in 
class, but assume that you understand.  In solving such a problem---and 
especially when giving a proof---you should clearly state the definition 
you are using and show that it is well defined.  
If the meaning of any problem is not clear, you should ask.
Also, you should always restate exactly what you are assuming and what you are 
proving in explicit mathematical terms.

For example, on Problem Set 1 we used the phrase ``lowest terms''
without defining it, since everyone has heard of this concept.  In
order to provide a mathematical proof about a fraction in lowest
terms, however, you should provide a mathematical definiton of
``lowest terms,'' and then derive any basic properties that you wish
to use from your definition.  For instance, you may blithely think
that if a positive rational number $q=a/b<1$ is in lowest terms, then
$a<b$.  If you were to try to prove this, however, you would soon
notice that the truth of this statement depends on your definition of
``lowest terms'': $a$ and $b$ may be negative integers (which is
consistent with our definition of $\rationals$), so if your definition
allows, say, both $q=2/3$ and $q=-2/-3$ to be in ``lowest terms'',
then the statement is obviously false.  A similar problem arises if
you try to define ``lowest terms'' as follows.
\begin{quote}
{\bf Bad Definition:} 
$q=a_0/b_0$ is in {\bf lowest terms} if $b_0$ is the smallest element of
the set $\{ b\in\integers : \exists a\in\integers \mbox{ such that } a/b =q\}$.
\end{quote}
This definition is not {\em well defined}, since this set has no
smallest element.  For example, we have $2/3 = (-2/-3) = (-4/-6) =
(-6/-9) = \cdots $ .

This bad definition may be corrected by stipulating that $b\in\nats$.
\begin{quote}
{\bf Okay Definition:} 
$q=a_0/b_0$ is in {\bf lowest terms} if $b_0$ is the smallest 
element of the set $\{ b\in\naturals : \exists a\in\integers \mbox{ such that } a/b =q\}$.
\end{quote}
The elements in this set form a subset of $\nats$ and therefore, by
the Well-Ordering Principle, the set has a smallest element.  Notice
that by this definition, $-3/-5$ is not in lowest terms.
Alternatively, we could define lowest terms to include $-3/-5$ by
referring to absolute values in the definition.

It is also possible to define ``lowest terms'' in terms of the greatest
common divisor function.
\begin{quote}
{\bf Another Okay Definition:} 
$q=a/b$ is in {\bf lowest terms} if $\gcd(a,b)=1$.
\end{quote}
But, be careful.  In order to show that ``Another Okay Definition'' is
well defined, we must prove that for every $q\in \rationals$, there
exist $a,b\in\integers$ with $\gcd(a,b)=1$, a fact whose proof depends
on the Well-Ordering Principle.  For this reason, it is somewhat more
desirable to use ``Okay Definition,'' because it is more basic, and
then prove as a theorem that it implies that $\gcd (a,b) = 1$.

Nevertheless, either of the two ``Okay Definitions'' can be used.
What is important is to make sure that you define in a mathematical
way any of the common-knowledge terms that you want to use in your
proof, and then prove the basic properties that you need.

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\remove{

  \problem 
  Show that the two rules of inference, \defn{modus ponens} and 
  \defn{syllogism}
  (from Lecture 4 and [MR, p.~554]), are equivalent.
  That is, show that
  \[
  \left[ \rule{0pt}{13pt} 
  \left( P \wedge (P\implies Q) \rule{0pt}{10pt} \right) 
	  \implies Q 
  \right] 
  \iff
  \left[ \rule{0pt}{13pt}
  \left( (P\implies Q) \wedge (Q\implies R)\rule{0pt}{10pt} \right) 
	  \implies (P\implies R) 
  \right].	
  \]
  %	using the former---\mbox{$(P \wedge (P\implies Q) ) \implies Q$}---%
  %	one can prove the latter---%
  %	$((P\implies Q) \wedge (Q\implies R)) \implies (P\implies Q)$---% 
  %	and vice-versa.
  %	The logical principle of deduction called \defn{modus ponens} states
  %	that if $A \implies B$ is true and $A$ is true, then $B$ is true
}

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

\problem Let $A$ and $B$ be subsets of a universe $U$ of elements.
Define $P(x)$ to be the predicate ``$x\in A$,'' and define $Q(x)$ to
be the predicate ``$x\in B$.'' Prove that $A\subseteq B$ if and only
if $\forall x, P(x)\implies Q(x)$.  How should we interpret $\forall
x, \neg P(x) \vee Q(x)$ in terms of sets, and how does this formula
relate to the the formula $A\subseteq B$?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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,
\problempart
well ordering,
\problempart
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 Consider four knights positioned at the corners of a $3\times
3$ chessboard, two white knights on the first rank and two black
knights on the third rank.
\begin{problemparts}

\problempart Determine how to exchange the positions of the white
knights with the positions of the black knights in the fewest number 
of knight moves.
(If you don't know how a knight moves on a chessboard, ask your
recitation instructor.)  Argue that your answer is optimal.  (\hint
Construct an undirected graph containing a node for each square of the
chessboard and an edge between two squares if a knight can move
between the two squares.)

\problempart Now, suppose that one of the white knights is replaced by
a red knight.  How many moves does it take to exchange the position of
the white knight with that of the red knight?  Justify your answer.
\end{problemparts}

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

\problem Prove that in any undirected graph, the sum of the squares of
the vertex degrees is even, or provide a counterexample.

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

\problem For a rooted tree, we define the \defi{degree} of a node to
be the number of children it has.  Thus, the conventional terminology
for the degree of a node in a tree differs depending on whether the
tree is considered to be a free tree (that is, a graph) or a rooted
tree.  In other words, except for the root, the degree of each node in
a rooted tree is one fewer than its graph degree.  (See the footnote
concerning the degree of a node in a rooted tree on page 94 of
Handout~\ref{clrchap5}.)

Prove that the number of leaves in any rooted binary tree is one more
than the number of nodes of degree~$2$.

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

\problem In a free tree, a vertex of degree one is called a
\defn{leaf}.  Prove that every free tree with two or more vertices has
at least two leaves.  (For partial credit, prove that every free tree
with two or more vertices has at least one leaf.)

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

\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 on page 94 of Handout~\ref{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].)

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

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

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

\remove{
  \problem Prove that the edges of any connected, undirected graph with 
  an even number of edges can be oriented---that is, assigned a 
  direction---so that every vertex has even out-degree.
}

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

\problem {\bf (Optional---for extra credit and extra fun.)} Each
vertex of an undirected graph $G=(V,E)$ contains a toggle switch and a
lightbulb.  If you push the toggle switch of a vertex, the bulb of
that vertex and the bulbs of all neighboring vertices are toggled:
each bulb goes off if it was on, and on if it was off.  Initially, all
the bulbs are off.  The goal is to turn all the bulbs on.  Such a
puzzle can be constructed from simple electronic components.  This
problem focuses on showing that no matter what graph underlies the
puzzle, the puzzle can always be solved.

The first observation that we make is that pushing the same switch
twice leaves the bulbs in the same state as before pushing the switch.
Likewise, pushing a switch an odd number of times is equivalent to
pushing it just once.  Furthermore, pushing a set of switches each
once has the same net effect on the bulbs independent of the order in
which the switches are pushed.  Hence, we can talk of a ``setting'' of
the switches, which corresponds to the subset of vertices whose
switches have been pushed once (or an odd number of times).  The aim
of this problem is to prove that for any undirected graph $G$, there
exists a \defi{good} setting of the switches: a setting such that all
the bulbs are turned on simultaneously.

The proof is by induction on the number of vertices in the graph.
Specifically, we shall prove that there is a good setting of the
switches for any graph $G$ on $n$ vertices by assuming that there is
such a setting for any graph on $n-1$ vertices.  We shall need to
handle separately two cases: when $n$ is even (part {\bf (a)}), and
when $n$ is odd (parts {\bf (b)} and {\bf (c)}).  In part {\bf (d)},
you must perform the actual induction, providing the base case and
referring to results from earlier parts.

\begin{problemparts}

\problempart Suppose that $G$ has an even number $n$ of vertices.
Assume that every graph on $n-1$ vertices has a good setting.  Notice
that there are $n$ subsets of $V$ that have size~$n-1$.  By
assumption, each of the corresponding $n$ induced
subgraphs\footnote{The \defi{induced subgraph} on $S \subset V$ is the
graph obtained by removing all nodes (and incident edges) not in~$S$.
(See Handout~\ref{clrchap5}, page 88.)} has a good setting.  Prove
that these $n$ good settings can be combined (in some suitable way,
which you must determine) to obtain a good setting for $G$.

\problempart 
Suppose that $G$ has an odd number of vertices.  Prove
that there exists a vertex with even degree.

\problempart Suppose that $G$ has an odd number $n$ of vertices.
Assume that every graph on $n-1$ vertices has a good setting.  Let $v$
be a vertex of even-degree, and let $S$ be the set of vertices that
contains $v$ and its neighbors.  Notice that there are $n-\card{S}$
subsets of $V$ that have $n-1$ vertices and also contain $S$ (each is
obtained by removing a different element of $V-S$).  Prove that these
$n-\card{S}$ good settings can be combined to obtain a good setting
for~$G$.

\problempart 
Conclude that a good setting exists for any undirected graph.

\end{problemparts}

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

\problem {\bf (Optional---for even more extra credit and even more
extra fun.)} A host and hostess invite four other couples to their
house for a dinner party.  As the couples arrive, various people shake
hands, but, of course, no one shakes the hand of another person more
than once, and no one shakes the hand of his or her spouse.  During
dinner, the hostess asks each of the nine other people how many hands
he or she shook, and finds, interestingly, that no two of them shook
exactly the same number of hands.  How many hands did the host shake?
(\hint Use induction to solve the problem for $n$ couples.)

\end{problems}

\end{document}
