{\huge 6042 F02, Q1 EXTRA UNUSED PROBLEMS}

%% NEWPAGE--------------------------------------------------
\ifshowsolutions {} \else \newpage \fi

%% by Adrian
%% INDUCTION
\begin{examproblem}{10}
Consider the following game.  $n$ players sit around a round table,
and each has a penny.  The game begins with player $1$ passing a penny
to player $2$, and player $2$ then passing two pennies to player $3$.
Player $3$ then passes a penny to player $4$, who passes two pennies
to player $5$, and so on, with players alternatively passing one or
two pennies to the next player.  When any player runs out of pennies,
he leaves the table and is no longer in the game.

Prove that if $n = 2^m + 2$ for some natural number $m$, the game ends
with a single player collecting all the pennies.

\solution{Note that after the first two moves, there are $2^m$ players
left, with the first player having three pennies and the rest having
one penny.

We now prove the following claim by induction:
 
$P(m) ::=$ For any positive integers $i, j$ with $i > 1$, if there are
$2^m$ players at the table, with the first player having $i$ pennies
and the rest having $j$ pennies, the game ends with the first player
collecting all the pennies.

Base case: If $m=0$ there is only one player, so the result is clearly
true.

Inductive step: Assume $P(m)$.  Consider a table of $2^{m+1}$ players,
where the first player has $i$ pennies and all other have $j$ pennies
for some $i, j$ positive integers with $i > 1$.  Note that after a
game goes around a table once (i.e. each player makes one move), all
the even-numbered players lose a penny, and all the odd numbered ones
gain a penny.  Therefore after the game goes around the table $j$
times, all the even numbered players drop out, and of the odd-numbered
players, first player has $i+j$ pennies, and the rest have $2j$
pennies.  The number of players is now $2^m$, so $P(m)$ applies and we
conclude that the game ends with the first player collecting all the
pennies.

By induction, $P(m)$ holds for all $m$.  Applying it with $i = 3$ and
$j=1$ concludes the proof.
}
\end{examproblem}



ORIGINAL VERSION
\begin{examproblem}{20}

Recall that a $k$-coloring of a simple graph is an assignment of a
color to each vertex such that no two adjacent vertices have the same
color and no more than $k$ colors are used. In class we proved that if
a graph has maximum degree $k$, then it can be colored with $k+1$
colors.

A graph is defined to be {\em regular} if every vertex in the 
graph has the same degree.  

Prove by strong induction that if a connected graph has maximum node
degree $k$ and is not regular then it can be colored with $k$
colors. (you may use the result from class without proof)

\solution{

Proof by strong induction on the number of vertices:

Inductive hypothesis:\\
$P(n) = $``Every connected graph of $n$ vertices and maximum node degree $k$ 
that is not regular is $k$-colorable.''

{\bf Base case:} (n=1)\\
The graph with one vertex is always regular, so $P(1)$ holds vacuously.

{\bf Inductive step:}

Assume $P(1)\wedge P(2) \wedge\cdots\wedge P(n)$, in order to prove $P(n+1)$.\\
Given any graph $G_{n+1}$ with $n+1$ vertices and maximum vertex degree $k$,
$P(n+1)$ holds trivially if the graph is not connected or is regular.
Therefore assume $G_{n+1}$ is connected and not regular.
Then, since $G_{n+1}$ is not regular, it must have some vertex of degree
less than $k$.  Remove that vertex, $v$, to produce a graph $G_n$.  Then we
can consider each connected component $C_i$ of $G_n$:

Case 1: $C_i$ is regular.  Since $G_{n+1}$ was connected, $v$ must have
been connected to at least one node in $C_i$.  Therefore, at least one
node of $C_i$ must have a lower degree than it did before $v$
was removed.  Therefore $C_i$ has at least one node of degree less than
$k$.  Since $C_i$ is regular, all nodes must therefore have degree less
than $k$, meaning $C_i$ has a maximum node degree less than $k$.  Therefore
$C_i$ is $k$-colorable by part (a).

Case 2: $C_i$ is not regular.  $C_i$ must have degree at most $k$
and it is connected by definition, so
by the inductive hypothesis, it is $k$-colorable.

Since all components of $G_n$ are $k$-colorable, $G_n$ is $k$-colorable.  We
can therefore assume $G_n$ is assigned some $k$-coloring.  Now we can
reattach $v$.  Since $v$ has less than $k$ neighbors, there must be some
$j \leq k$ such that $v$ is not adjacent to any node of color $j.$  Thus,
we can color $v$ with color $j$, producing a $k$-coloring of $G_{n+1}$.
Therefore, if $G_{n+1}$ has maximum vertex degree $k$ and is not regular
then it is $k$-colorable.
}

\end{examproblem}

% \problemdata     
% {S01-PS4-5}           
% {graphs, induction}
% {}              
% {S01-PS4} 		
% {S01 Karger}

\begin{examproblem}{15}
GRAPHS, CONNECTIVITY, INDUCTION, FALSE PROOF. An $n$-node graph is
said to be {\em tangled} if there is an edge leaving every set of
$\ceil{\frac{n}{3}}$ or fewer vertices.  As a special case, the
graph consisting of a single node is considered tangled.  (Recall that
the notation $\lceil x \rceil$ refers to the smallest integer greater
than or equal to $x$.)

Consider the following false claim:

\begin{claim}
 Every non-empty, tangled graph is connected.
\end{claim}

Consider the following proof of the false claim:

\begin{proof}
The proof is by strong induction on the number of vertices in the
graph.  Let $P(n)$ be the propostion that if an $n$-node graph is
tangled, then it is connected.  In the base case, $P(1)$ is true
because the graph consisting of a single node is defined to be tangled
and is trivially connected.

In the inductive step, for $n \geq 1$ assume $P(1), \ldots, P(n)$ to
prove $P(n+1)$.  That is, we want to prove that if an $(n+1)$-node
graph is tangled, then it is connected.  Let $G$ be a tangled,
$(n+1)$-node graph.  Arbitrarily partition $G$ into two pieces so that
the first piece contains exactly $\lceil\frac{n}{3}\rceil$ vertices,
and the second piece contains all remaining vertices.  Note that since
$n \geq 1$, the graph $G$ has a least two vertices, and so both pieces
contain at least one vertex.  By induction, each of these two pieces
is connected.  Since the graph $G$ is tangled, there is an edge
leaving the first piece, joining it to the second piece.  Therefore,
the entire graph is connected.  This shows that $P(1), \ldots, P(n)$
imply $P(n+1)$, and the claim is proved by strong induction.
\end{proof}

\begin{problemparts}

\problempart[6]
Explain exactly where the proof goes wrong.

\solution{The error is in the statement, ``By induction, each of
these two pieces is connected.''  This is not what the induction
hypothesis says; the induction hypothesis states that {\em if a graph
is tangled}, then it is connected.

In abstract terms, we are proving an induction hypothesis of the form
``if (this), then (that)''.  However, we erroneously use the induction
hypothesis as if it were simply of the form ``(that)''.  }

\ifshowsolutions
{}
\else
\vspace{2in}
\fi

\problempart[3] Draw a tangled graph that is not connected.

\graphicspath{{/toc/a/class/6.042/spring02/problemRepository/figures/}}
\solution{
  \begin{samepage}
    \begin{center}
      \includegraphics[height=1in]{ps4-tangled-cx}
    \end{center}
  \end{samepage}
}


\ifshowsolutions
{}
\else
\vspace{2in}
\fi

\newpage

An $n$-node graph is said to be {\em mangled} if there is an edge
leaving every set of $\lceil\frac{n}{2}\rceil$ or fewer vertices.
Again, as a special case, the graph consisting of a single node is
considered mangled.

\begin{claim} Every non-empty, mangled graph is connected.
\end{claim}

\problempart[6] Prove the above claim by contradiction.

\solution{
\begin{proof}
The proof is by contradiction.  Assume for the purpose of
contradiction that these exists an $n$-node graph that is mangled, but
not connected.  Then the graph must have at least two connected
components.  However, there can be at most one connected component
with more than $\lceil\frac{n}{2}\rceil$ vertices, since the graph has
only $n$ vertices in total.  Therefore, there exists a connected
component with $\lceil\frac{n}{2}\rceil$ or fewer vertices.  Since the
graph is mangled, there is an edge leaving this component.  But this
contradicts the definition of a connected component.
\end{proof}
}

\end{problemparts}
\end{examproblem}

\begin{examproblem}{10} 
INDUCTION: The 6.042 mascot, Theory Pig, made a startling discovery
while playing with his prized collection of unit squares over the
weekend.  Here is what happened.

First, Theory Pig put his favorite unit square down on the floor as in
Figure~\ref{fig:squares}~(a).  He noted that the length of the periphery
of the resulting shape was 4, an even number.  Next, he put a second unit
square down next to the first so that the two squares shared an edge as in
Figure~\ref{fig:squares}~(b).  He noticed that the length of the periphery
of the resulting shape was now 6, which is also an even number.  (The
periphery of each shape in the figure is indicated by a thicker line.)
Theory Pig continued to place squares so that each new square shared an
edge with at least one previously-placed square and no squares overlapped.
Eventually, he arrived at the shape in Figure~\ref{fig:squares}~(c).  He
realized that the length of the periphery of this shape was 36, which is
again an even number.

Our plucky porcine pal is perplexed by this peculiar pattern.  Use
induction on the number of squares to prove that the length of the
periphery is always even, no matter how many squares Theory Pig places or
how he arranges them.

\begin{figure}[htbp]
\centering
\graphicspath{{/toc/a/class/6.042/spring02/problemRepository/figures/}}
\includegraphics[width=4in]{f98ps2}
\caption{Some shapes that Theory Pig created.} \label{fig:squares}
\end{figure}

\emph{(TO HARD TO GRADE?)}

\solution{
\begin{proof}
The proof is by induction.  Let $P(n)$ be the proposition that the
periphery length is even after $n$ squares are placed.  In the base
case, $P(1)$ is true because the periphery of a single square has
length 4, which is even.

In the inductive step, assume that the periphery length is even after
$n$ squares are placed to prove that the periphery length is even
after $n+1$ squares are placed.  The $(n+1)$-st square could share 1,
2, 3, or 4 edges with previously-placed squares.

\begin{itemize}

\item If the new square shares 1 edge with a previously placed square,
then this one edge is removed from the periphery, but three edges of
the new square are added to the periphery.  Overall, the periphery
length increases by two and thus remains even.

\item If the new square shares 2 edges with previously placed squares,
then these two edges are removed from the periphery, but two edges of
the new square are added.  The periphery length is unchanged and thus
remains even.

\item If the new square shares 3 edges, then these three edges are removed
from the periphery, but one edge is added.  The periphery length
decreases by two and remains even.

\item If the new square shares 4 edges, then these four edges are removed
from the periphery and none are added.  The periphery length decreases
by four and remains even.

\end{itemize}

In all cases, the length of the periphery remains even.  Therefore,
for all $n \geq 1$, $P(n)$ implies $P(n+1)$ and the claim is proved by
induction.
\end{proof}
}
\end{examproblem}

% Found from the old repository.  Seems like a good logic problem.
% Something we can do is not give them the logic notation but give them 
% sentences and ask them to translate into logic notation as a first part 
% haven't run this thru latex yet -- so it may not run.  If you want to use 
% it, i can do that then.

\begin{examproblem}{10}
LOGICAL NOTATION, DEDUCTION. The 6.042 mascot, Theory Pig, was
recently found squished under a pile of course handouts.  Fortunately,
Theory Pig is okay and is getting his stuffing sorted out.  However,
he demands that the culprit or culprits be found.  The only clue is a
crumpled paper found nearby scrawled over with logic notation.

Let the domain of discourse $= \{ Tina, Adrian, Nikos, Georgi, Lee
\}$.\\
We define $G(x) = \mbox{true}$ if and only if $x$ is guilty.

Translate each of the following logic statements into English.

\begin{problemparts}

\problempart[1]    $(\exists x G(x)) \wedge (\exists x (\neg G(x)))$\\ 

\brule{5in}

\problempart[1] $(G(\mbox{Adrian}) \vee G(\mbox{Tina})) \rightarrow
        \neg G(\mbox{Lee})$\\

\brule{5in}

\problempart[1] $\neg (G(\mbox{Tina}) \wedge G(\mbox{Georgi}))$\\

\brule{5in}

\problempart[2] $\neg G(\mbox{Lee}) \rightarrow (\exists x \exists y (x \neq
y \wedge G(x) \wedge G(y))$\\

\brule{5in}


\problempart[1] $(G(\mbox{Adrian}) \rightarrow G(\mbox{Lee})) \wedge
  (G(\mbox{Lee}) \rightarrow G(\mbox{Adrian}))$\\

\brule{5in}

\problempart[1] $\neg (G(\mbox{Georgi}) \wedge G(\mbox{Nikos}))$\\

\brule{5in}

\vspace{.2in}

\problempart[3] Who squished Theory Pig? State your answer and sketch
 your deductive process (perhaps remove the explanation part?).\\

\brule{2in}

\end{problemparts}

\solution{
Theory Pig was squished by Tina and Nikos.

A straightforward, but laborious way to solve this problem is to write
out a table with $2^5 = 32$ entries, one for each guilty/innocent
combination.  If we cross off each entry that is contradicted by a
statement on the crumpled paper, then the single, remaining entry
indicates the culprits.

Here is an alternative, ad hoc approach.  Lee appears often, so
let's first try to determine whether he is guilty.  Suppose that
Lee is guilty.  Then by statement 4, neither Adrian nor Tina
can be guilty.  However, by statement 7, Adrian must be guilty.  This
is a contradiction with respect to Adrian, and so Lee must be
innocent.  Since Lee is innocent, statement 7 implies that Adrian
is also innocent, and statement 6 implies that there are at least two
culprits among the remaining three suspects, Tina, Georgi, and
Nikos.  Suppose that Georgi is guilty.  Then Tina and Nikos are
both innocent by statements 5 and 8.  This would imply only one
cuprit, giving a contradiction.  Therefore, Georgi must be innocent.
Since there are at least two culprits, Tina and Nikos must both be
guilty.
}

\end{examproblem}

%% spring 00 exam?

\begin{examproblem}{30} LOGIC 
Use the following propositions where the universe of discourse is the
set of all natural numbers:

\begin{eqnarray*}
P(n):& n \hbox{ is a perfect square}\\
Q(n):& n \hbox{ is prime}\\
R(n,m):& n < m\\
S(n,m):& n \hbox{ divides } m\\
T(n,m):& n = m\\
\end{eqnarray*}

Express each of the following statements using quantifiers, logical
connectives, and the propositions listed above, along with variables and
integers.

\begin{problemparts}

\problempart {\bf (5 points)}  4 is a perfect square and 4 is greater than 1.
\solution{ $P(4) \wedge R(1,4)$ }



\problempart {\bf (5 points)}  There is a natural number that divides 
all natural numbers.

\solution{ $\exists n \forall m S(n, m)$}

\problempart {\bf (5 points)} Two natural numbers are equal exactly
when neither is less than the other.

\solution{ 
$\forall n \forall m T(n, m) \leftrightarrow \neg R(n, m) \wedge
\neg R(m, n)$
}

\problempart {\bf (5 points)} A natural number $n$ that is greater
than 1 is prime exactly when the only positive natural number less
than $n$ that divides $n$ is 1.

\solution{ 
$\forall n Q(n) \wedge R(1,n) 
\leftrightarrow [\forall m R(0, m) \wedge R(m, n)
\wedge S(m, n) \rightarrow T(m, 1)]$
}

\problempart {\bf (5 points)} A natural number $n$ is a perfect square
only if there is a positive natural number (strictly) between 1 and
$n$ that divides $n$.

\solution{ 
$\forall n P(n) \rightarrow [\exists m R(0, m) \wedge R(1, m) 
\wedge R(m, n) \wedge S(m, n)]$
}

\problempart {\bf (5 points)} Given only the statements (a)-(e) above
and the standard rules of propositional and quantifier reasoning, can
you conclude that 4 is not prime?  If not, state a fact you can use
together with the statements (a)-(e) to conclude that 4 is not prime
(your fact should not mention the number 4).  If so, just list which
of the statements (a)-(e) above are necessary.

\solution{

FIX SOLUTION NOT TO USE STRUCTURED PROOFS

We can conclude that 4 is not prime, using parts (a), (c), (d), and (e).

Though a structured proof was not required, we provide one.  The
statement from part (c) was necessary so that we can use that if $m_0
> 1$ then $\neg m_0 = 1$.  Parts (d), and (e) are clearly required, and
part (a) is required so that we know 4 is a perfect square and that 4 > 1,
which are required to use the implications from (d) and (e).  Here is the
structured proof:


\begin{tabbing}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX\=XXXXXX\=\kill
1.  $P(4) \rightarrow [\exists m R(0, m) \wedge R(1, m) \wedge R(m, 4)
\wedge S(m, 4)]$\>UI, from part (e).\\
2.  $P(4)$\>Simplification, from part (a).\\
3.  $\exists x R(0, x) \wedge R(1, x) \wedge R(x, 4) \wedge S(x, 4)$
\>Modus Ponens, from 1 and 2.\\
4.  $R(0, m_0) \wedge R(1, m_0) \wedge R(m_0, 4) \wedge S(m_0, 4)$
\>EI, from 3.\\
5.  $R(1, m_0)$ \>Simplification, from 4.\\
6.  $T(1, m_0) \leftrightarrow \neg R(1, m_0) \wedge \neg R(m_0, 1)$
    \>UI, from part (c).\\
7.  $\neg R(1, m_0) \wedge \neg R(m_0, 1) \leftarrow T(1, m_0)$
    \>Simplification, from 6.\\
8.  $\neg [R(1, m_0) \vee R(m_0, 1)] \leftarrow T(1, m_0)$
    \>DeMorgan's law, from 7.\\
9.  $R(1, m_0) \vee R(m_0, 1)$  \>Addition, from 5.\\
10.  $\neg T(1, m_0)$  \>Modus Tollens, from 8 and 9.\\
11.  $R(0, m_0) \wedge R(m_0, 4) \wedge S(m_0, 4)$ \>Simplification,
     from 4.\\
12.  $(R(0, m_0) \wedge R(m_0, 4) \wedge S(m_0, 4)) \wedge \neg T(1,
     m_0)$ \>Conjunction, from 10 and 11.\\
13.  $\neg[\neg (R(0, m_0) \wedge R(m_0, 4) \wedge S(m_0, 4)) \vee
     T(1, m_0)]$ \>DeMorgan's Law, from 12.\\
14.  $\neg[(R(0, m_0) \wedge R(m_0, 4) \wedge S(m_0, 4)) \rightarrow
     T(1, m_0)]$ \>Logical equivalence, from 13.\\
15.  $\exists m \neg [(R(0, m) \wedge R(m, 4) \wedge S(m, 4))
     \rightarrow T(1, m)]$ \>EG, from 13.\\
16.  $\neg \forall m [(R(0, m) \wedge R(m, 4) \wedge S(m, 4)) \rightarrow
     T(1, m)]$ \>Negation rule for quantifiers\\
17.  $Q(4) \wedge R(1,4) \leftrightarrow [\forall m R(0, m) \wedge
     R(m, 4) \wedge S(m, 4) \rightarrow T(m, 1)]$ \>\>UI, from part (d).\\
18.  $\neg (Q(4) \wedge R(1,4))$  \>Modus Tollens, from 15 and 16.\\
19.  $\neg Q(4) \vee \neg R(1,4)$  \>DeMorgan's Law, from 18.\\
20.  $R(1,4)$ \>Simplification, from part (a).\\
21.  QED $\neg Q(4)$  \>Disjunctive Syllogism, from 19 and 20.  
\end{tabbing}}


\end{problemparts}
\end{examproblem}

%%  converted old problem

\begin{examproblem}{15} GRAPHS ISOMORPHISM. 
Some properties of a simple graph, $G$, are described below.  For each
property, indicate whether or not it is {\em invariant under
isomorphism} by writing \textbf{Yes} or \textbf{No} in the space
provided. For the false ones, \textbf{\emph{describe a
counterexample}}.

NOTE: DEFINE INVARIANT UNDER ISOMORPHISM, make sure ISOMORPHISM formal
definition is in the appendix.


\begin{problemparts}
\problempart $G$ has an even number of vertices. \brule{.5in}
\vspace{0.7in}

\solution{It is invariant under isomorphism. There must be an
one-to-one and onto mapping between the vertices of two isomorphic
graphs. Therefore, the number of vertices in the two graphs must be
the same. If one graph has even number of vertices, then the other
must have even number of vertices.}

\problempart None of the vertices of $G$ is an even integer.\brule{.5in}
\vspace{0.7in}


\solution{It is not invariant under isomorphism. We do not really care
what the vertices are. Vertices can be any kind of mathematical
objects.  All we are interested is that whether there exists a
one-to-one and onto function $f$ mapping from vertices of one graph to
vertices of another with the property that $a$ and $b$ are adjacent in
the first graph if and only if $f(a)$ and $f(b)$ are adjacent in the
second graph, for all $a$ and $b$ in the first graph.

So, for example, let $G_1$ be a graph with a single vertex, 1, and $G_2$ be
a graph with a single vertex, 2. Obviously the two graphs are isomorphic, but
$G_2$ does not have vertices which are even integers.}


\iffalse
\problempart $G$ has a vertex of degree 3.\brule{.5in}
\vspace{0.7in}

\solution{It is invariant under isomorphism.  

Let $G_1, G_2$ be simple graphs and $f:V_1\to V_2$ be an isomorphism
between them.  Suppose $v\in V_1$ has degree 3; we want to show that there
is a vertex of degree 3 in $V_2$.  In fact, we'll show that $f(v)$ has
degree 3.
 
Since $v$ has degree 3, there are exactly 3 vertices adjacent to $v$; say
these are $v_1,v_2,v_3$.  Since $f$ is a bijection, $f(v_1),f(v_2)$ and
$f(v_3)$ are all distinct.  Since there is an edge between $v$ and $v_i$
in $G_1$, the definition of isomrphism implies that there is an edge
between $f(v)$ and $f(v_i)$ for $i=1,2,3$, so the degree of $f(v)$ is at
least 3.
 
We now prove by contradiction that the degree of $f(v)$ is at most 3.
Suppose $f(v)$ had degree $>3$.  This means there is a vertex $w \in V_2$
which is not equal to $f(v_1), f(v_2),$ or $f(v_3)$, but is also adjacent
to $f(v)$.  Since, $f$ is a bijection, there is a vertex $v_4 \in V_1$
such that $f(v_4) = w$ and $v_4 \neq v_i$ for $i=1,2,3$.  Since $w=f(v_4)$
is adjacent to $f(v)$, the definition of isomorphism implies that $v_4$ is
adjacent to $v$, contradicting the fact the $v_1,v_2,v_3$ were exactly the
vertices adjacent to $v$.}
\fi

\problempart $G$ has exactly one vertex of degree 3.\brule{.5in}

\solution[\vspace{0.7in}]{It is invariant under isomorphism.

Prove by contradiction:  Let a graph $G_1$ has exactly one vertex of 
degree $3$ while another graph $G_2$ does not have exactly one vertex of 
degree 3. Suppose the two graphs are isomorphic. If $G_2$ does not have 
a vertex of degree 3, then from part (c), there is a contradiction.
If $G_2$ has more than one vertices of degree 3, then there must
be at least one vertex in $G_2$ of degree 3 which is mapped to 
a vertex of degree $\neq 3$ in $G_1$. Since two vertices of different degrees
are mapped from $G_1$ to $G_2$, using the same argument from part (c),
it reaches a contradiction. Therefore, if $G_1$ has exactly one 
vertex of degree 3 , then $G_2$ must also have exactly one 
vertex of degree 3.}


\iffalse
\problempart One of the vertices of $G$ is also an edge of $G$.\brule{.5in}
\vspace{0.7in}

\solution{It is not invariant under isomorphism.

Let $G_1$ be a graph with three vertices, $1$, $2$ and $\{1,2\}$. There is
only one edge from vertex $1$ to vertex $2$. Therefore, $\{1,2\}$ is a vertex
of $G_1$ and also an edge of $G_1$. 

On the other hand, let $G_2$ be a graph with three vertices,
$7$, $12.1$ and an ordered pair $(1, -3)$(note: these are somewhat
tasteless, but legitimate things to use as vertices). There is only 
one edge from vertex $7$ to vertex $12.1$.
Obviously two graphs are isomorphic; however, $G_2$ does not have 
a vertex which is an edge at the same time. 
Therefore, it is not invariant under isomorphism.}
\fi

\problempart Prove that if two graphs $G_1$ and $G_2$ are isomorphic
then if $G_1$ is 3-colorable, $G_2$ must also be 3-colorable.

\end{problemparts}
\end{examproblem}


\problemdata     
{induction-8}           
{induction, proofs, structural induction}              
{}              
{S01-PS2} 		
{S01 Karger}        	

\def\mult{\diamond}
\begin{problem} 
Consider the following ``mungiplication''
operation $\mult$, defined recursively on the natural numbers as follows:
\begin{enumerate}
\item for any $x$, $0 \mult x = 0$
\item for any $x$, $(n+1) \mult x = n\mult x + x$
\end{enumerate}
(You may note some similarity to the famous ``multiplication''
operation, but should {\bf not} use any facts about multiplication in
this problem.)  Do not assume anything about $\mult$ beyond what is
given above.
\begin{problemparts}

\problempart Prove the {\bf distributive law:} for any $n,a,b$, 
\[
n\mult (a+b) = n\mult a+n \mult b
\]
You may use all standard facts about addition.  But do not use
summation notation.

\solution{

\begin{proof}
By induction on $n$:

{\em Base case, $n = 0$:}
\[ 0 \mult (a + b) = 0 = 0 + 0 = (0 \mult a) + (0 \mult b) \]

{\em Inductive case, assuming $n \mult (a + b) = (n \mult a) + (n \mult b)$:}

\begin{eqnarray}
\label{mung-one}
(n + 1) \mult (a + b) & = & n \mult (a + b) + (a + b)\\
\label{mung-two}
& = & n \mult a + n \mult b + (a + b)\\
\label{mung-three}
& = & (n \mult a + a) + (n \mult b + b)\\
\label{mung-four}
& = & (n + 1) \mult a + (n + 1) \mult b
\end{eqnarray}

Equations~\ref{mung-one}~and~\ref{mung-four} are by the
``mungiplication'' definition. Equation~\ref{mung-two} is by the inductive
assumption. Equation~\ref{mung-three} is by addition's commutative and associative
properties.
\end{proof}
}

\problempart Prove the {\bf annihilation law:} for any $x$,
\[
x \mult 0 = 0
\]

\solution{

\begin{proof}
By induction on $x$:

{\em Base case, $x = 0$:}
\[ 0 \mult 0 = 0 \]
{\em Inductive case, assuming $x \mult 0 = 0$:}

By the ``mungiplication'' definition,
\( (x + 1) \mult 0 = x \mult 0 + 0\).
But \( x \mult 0 + 0 = x \mult 0 = 0 \) by the inductive assumption.
\end{proof}
}

\problempart Prove the {\bf commutative law:} for any $x, n$,
\[
x \mult n = n \mult x
\]

\solution{

\begin{proof}
By induction on $n$:

{\em Base case, $n = 0$:}
\[ x \mult 0 = 0 \mult x = 0 \]
{\em Inductive case, assuming $x \mult n = n \mult x$:}

\begin{eqnarray}
\label{mungcom-one}
x \mult (n + 1) & = & x \mult n + x \mult 1\\
\label{mungcom-onefive}
& = & x \mult n + x\\
\label{mungcom-two}
& = & n \mult x + x\\
\label{mungcom-three}
& = & (n + 1) \mult x
\end{eqnarray}

Equation~\ref{mungcom-one} is by the distributive property from part A.
Equation~\ref{mungcom-onefive} is by a subproof that we show next. 
Equation~\ref{mungcom-two} is by the inductive assumption.
Equation~\ref{mungcom-three} is by the ``mungiplication'' definition.
\end{proof}

\begin{proof}For any $x$, $x \mult 1 = x$ (by strong induction):

{\em Base cases, $x = 0,1$:}
\[ 0 \mult 1 = 0 \]
\[ 1 \mult 1 = 0 \mult 1 + 1 = 0 + 1 = 1 \]

{\em Inductive case, assuming $x \mult 1 = x$:}
\begin{eqnarray}
\label{lemma-one}
(x + 1) \mult 1 & = & x \mult 1 + 1\\
\label{lemma-two}
& = & x + 1
\end{eqnarray}

Equation~\ref{lemma-one} is by the ``mungiplication'' definition.
Equation~\ref{lemma-two} is by the inductive assumption.
\end{proof}
}

\problempart
{\em Optional:} Prove the {\bf associative law:} for any $a, b, n$,
\[
(a \mult n) \mult b = a \mult (n \mult b)
\]

\solution{
\begin{proof}
By induction on $n$:

{\em Base case, $n = 0$:}
\[
(a \mult 0) \mult b = 0 \mult b = 0 = a \mult 0 = a \mult (0 \mult b)
\]
This is by the identity law from part B and the definition of
``mungiplication''.

{\em Inductive case, assuming $(a \mult n) \mult b = a \mult (n \mult b)$:}

\begin{eqnarray}
\label{mungbon-1}
(a \mult (n + 1)) \mult b & = & ((n + 1) \mult a) \mult b\\
\label{mungbon-2}
& = & (n \mult a + a) \mult b\\
\label{mungbon-3}
& = & (n \mult a) \mult b + a \mult b\\
\label{mungbon-4}
& = & (a \mult n) \mult b + a \mult b\\
\label{mungbon-5}
& = & a \mult (n \mult b) + a \mult b\\
\label{mungbon-6}
& = & a \mult (n \mult b + b)\\
\label{mungbon-7}
& = & a \mult ((n + 1) \mult b)
\end{eqnarray}

Equations~\ref{mungbon-1}~and~\ref{mungbon-4} use the commutative property from
part C. Equations~\ref{mungbon-2}~and~\ref{mungbon-7} use the
``mungiplication'' definition.
Equation~\ref{mungbon-6} uses the distributive property from part A.
Equation~\ref{mungbon-3} uses both the commutative and
distributive properties. Equation~\ref{mungbon-5} uses the inductive assumption.

\end{proof}
}

\end{problemparts}

\end{problem}

\begin{problem}
\textbf{Moiler's Oiling Problem}

Once upon a time on the island of Grete in the Nediterranean Sea there
lived a minotaur called \emph{Moiler}. He was wealthy and had a huge
palace. He was also lazy, so the layout of the palace was a simple one -
it was a rectangle, divided into many rectangular rooms of the same size,
as shown on Figure~\ref{palace}.

\begin{center}
\begin{figure}[h]
\setlength{\unitlength}{0.9cm}
\begin{picture}(15,10)
\put(0,0){}
\put(2,7.5){Room 1}
\put(7,7.5){Room 2}
\put(12,7.5){Room 3}
\put(2,2.5){Room 4}
\put(7,2.5){Room 5}
\put(12,2.5){Room 6}
\thinlines
\put(0,0){}
\put(0,5){\line(1,0){7}}
\put(8,5){\line(1,0){4}}
\put(13,5){\line(1,0){2}}
\put(7,5){\line(1,1){1}}
\put(12,5){\line(1,1){1}}
\put(5,10){\line(0,-1){1}}
\put(5,8){\line(0,-1){1}}
\put(5,6){\line(0,-1){2}}
\put(5,3){\line(0,-1){1}}
\put(5,1){\line(0,-1){1}}
\put(10,10){\line(0,-1){1}}
\put(10,8){\line(0,-1){4}}
\put(10,3){\line(0,-1){3}}
\put(5,9){\line(1,-1){1}}
\put(5,7){\line(1,-1){1}}
\put(5,4){\line(1,-1){1}}
\put(5,2){\line(1,-1){1}}
\put(10,9){\line(1,-1){1}}
\put(10,4){\line(1,-1){1}}
\thicklines
\put(0,0){}
\framebox(15,10)[0,0]{}
\end{picture}
\par
\caption{\label{palace} Moiler's palace.}
\end{figure}
\end{center}

To facilitate moving around, \emph{Moiler} put doors between some of the
adjacent rooms. Due to his eccentricity, he sometimes put more than one
door between the same two rooms. He made sure, though, that he can reach
any room in his palace starting from room 1.  \par Every week,
\emph{Moiler} was faced with a hard problem - the hinges of all doors
needed oiling and someone had to go around the huge palace and oil each
one of them. Lazy as \emph{Moiler} was, he hired a wise man called
\emph{Taetalus} to do the oiling of the door hinges.

a) Help \emph{Taetalus} find a way to oil the hinges in the palace so that
he starts from room 1, goes through each door exactly once, and ends up in
room 1 at the end of his oiling trip. We will call a trip like that a {\bf
slick~oiling~trip}.

Produce the sequence of numbers of rooms that \emph{Taetalus} must go through on his 
{\bf slick~oiling~trip} (multiple answers exists).

For example, the trip $(1\ 2\ 1)$ starts from room 1 and ends there, but goes only
through the two doors between rooms 1 and 2.

\solution{The two possible answers are:
\\
1\ 2\ 3\ 6\ 5\ 4\ 5\ 2\ 1
\\
1\ 2\ 5\ 4\ 5\ 6\ 3\ 2\ 1
}

b) Moiler was pleased with \emph{Taetalus'} work, but decided that he should expand his
palace and also put more doors between the rooms. The layout was to remain rectangular,
but expand to $m\times n$ rooms. \emph{Taetalus} was hired as a consultant.
\\
Prove that if \emph{Taetalus} makes sure that every room has an even number of doors,
then he will still be able to find a {\bf slick~oiling~trip}.
\\
{\it Hint: Taetalus recalls studying about multigraphs and insists they might be very
useful here.}

\solution{Let us build an undirected multigraph $G=(V,E)$ that corresponds to \emph{Moiler}'s
palace. Let $V=\{v_1, v_2, \ldots, v_k\}$, where $k=m*n$ and each vertex $v_i$
corresponds to the $i$-th room. Let $E$ contain edges $e_i$, one for every door in the
palace. Since $G$ is a multigraph, we also need to define a function $f$ that maps the
edges in $E$ to unordered pairs of vertices that they connect. Naturally, we define
$f(e_i)=\{v_j,v_k\}$ if the edge $e_i$ corresponded to a door between rooms $j$ and
$k$.

For example, for the palace from \emph{part a)} we have:
\\
$V=\{v_1,v_2,v_3,v_4,v_5,v_6\}
\\
E=\{e_1,e_2,e_3,e_4,e_5,e_6,e_7,e_8\}
\\
f(e_1) = f(e_2) = \{v_1,v_2\}
\\
f(e_3) = \{v_2,v_3\}
\\
f(e_4) = \{v_2,v_5\}
\\
f(e_5) = \{v_3,v_6\}
\\
f(e_6) = f(e_7) = \{v_4,v_5\}
\\
f(e_8) = \{v_5,v_6\}$

The equivalent of a {\bf slick~oiling~trip} in the palace is an {\bf Euler~cycle} in
the graph $G$ (since it is a cycle, it doesn't really matter where it starts/ends).
\
Since the problem states that we can get from room 1 to any room, it follows that $G$
is connected.

\emph{Proof by contradiction:}
\\
Assume $G$ is not connected. Then, by definition, there exist two vertices $v_i$ and
$v_j$ between which there is no path. From the problem statement we know that there
is a path from $v_1$ to $v_i$ and from $v_1$ to $v_j$. Since $G$ is undirected, we can
reverse the path from $v_1$ to $v_i$ to obtain a path from $v_i$ to $v_1$. But then
there is a path from $v_i$ to $v_j$, which we can obtain by concatenating the paths
from $v_i$ to $v_1$ and from $v_1$ to $v_j$ together.
\\
We have reached a contradiction, and, therefore, $G$ is connected.
\\
\\
Now we need to find an Euler cycle in the graph $G$. Start building a simple path $P$
that begins at $v_1$ by going to adjacent vertices and deleting the traversed edges.
Since the graph $G$ was connected, there must be an edge adjacent to $v_1$, so we can
start such a path. The number of edges is finite, and we delete one edge on each step,
so the process will terminate in a finite number of steps. Furthermore, the path $P$
can only terminate at $v_1$, since every time it enters a vertex $v_x$, it decreases
$deg(v_x)$ by 1, making the degree odd, so there must exist another edge adjacent to
$v_x$. After the path traverses that edge and deletes it, $deg(v_x)$ becomes even again.
If there are no edges left after the process has terminated, then we have produced an
Euler cycle.
\\
Otherwise, consider the remaining graph, $G^\prime=(V^\prime,E^\prime)$, where
$V^\prime=\{${\it all vertices in V that still have adjacent edges}$\}$ and
$E^\prime=E-\{${\it all edges in P}$\}$. In general $G^\prime$ might not be connected. All
vertices in $G^\prime$ still have even degrees, because they had even degrees in $G$
and the path $P$ removed an even number of adjacent edges for every vertex it visited.
Every connected subgraph of $G^\prime$ has at least one vertex common with the path
$P$, because $G$ was connected. Let $G^{\prime\prime}=(V^{\prime\prime},E^{\prime\prime})$
be a connected subgraph of $G^\prime$ and let $v_y$ be the vertex it has in common with
$P$. Then, using the same  process, we can build an Euler cycle $P^{\prime\prime}$ for
$G^{\prime\prime}$ starting from $v_y$ that is of the form 
$(v_{j_1}, v_{j_2}, \ldots, v_{j_l},  v_{j_{l+1}})$ where
$v_{j_1}=v_{j_{l+1}}=v_y$ and $|E^{\prime\prime}|=l$.
\\
Let $P=(v_{i_1}, v_{i_2}, \ldots, v_{i_n}, v_y, v_{i_{n+1}}, v_{i_{n+2}}, \ldots, v_{i_m})$.
\\
We can simply substitute $P^{\prime\prime}$ for $v_y$ in $P$ and form the following path:
\\
$P=(v_{i_1}, v_{i_2}, \ldots, v_{i_n}, v_{j_1}, v_{j_2}, \ldots, v_{j_l}, v_{j_{l+1}},
v_{i_{n+1}}, v_{i_{n+2}}, \ldots, v_{i_m})$
\\
We can continue this process for all connected subgraphs of $G^\prime$ until all edges in
$E$ have been used. At the end $P$ will be an Euler cycle for $G$.
}

c) \emph{Moiler} finished the expansion of the palace and it now has $m\times n$ rooms.
Prove that no matter what doors exist between rooms, \emph{Taetalus} can always add a
finite number of extra doors, so that he is again able to find a {\bf slick~oiling~trip}.

\solution{We proved in \emph{part b)} that to be able to find a {\bf
slick~oiling~trip}, it is sufficient to make every room have an even
number of doors. Thus, we can augment the number of doors for each room so
that they are all even. The easiest way to do that is to add one extra
door for every one that already exists. In this way, if room $i$ had
originally $k$ doors, it will now have $2*k$ doors, which is an even
number.}

\end{problem}


%% spring01 practise quiz 1
\begin{examproblem}{10} DIRECTED GRAPHS, CONNECTIVITY, 
The vertices of a directed graph can be partitioned into {\em
strongly-connected components}.  Two vertices $u$ and $v$ belong to
the same strongly connected component if there is a path from $u$ to
$v$ and a path from $v$ to $u$.  A strongly connected component may
consist of a single vertex.

Math Moose has noticed a strange phenomenon.  He starts with a
directed graph and partitions the vertices into strongly-connected
components.  He then removes all edges that connect two vertices in
the same strongly-connected component.  The resulting graph always
seems to be acyclic.

An example is worked out in the figure below.  The original directed
graph is shown on the left.  The vertices $a$, $b$, and $c$ form one
strongly-connected component.  The single vertex $d$ forms a second
strongly-connected component.  Math Moose removes the edges $a
\rightarrow b$, $b \rightarrow c$, and $c \rightarrow a$, since these
edges connect vertices in the same strongly-connected component.  The
resulting graph is shown on the right.  Note that this graph is
acyclic.

\graphicspath{{/toc/a/class/6.042/spring02/problemRepository/figures/}}
\begin{center}
      \includegraphics[height=1in]{scc}
%%      \includegraphics[height=1in]{ps4-tangled-cx}
\end{center}


Use proof by contradiction to show that for every directed graph,
application of Math Moose's procedure gives a directed acyclic graph.

\solution{
\begin{proof}
Let $G = (V,E)$ be an arbitrary directed graph.  Let $G' = (V,E')$ be
the directed graph that remains after we remove all edges that connect
two vertices in the same strongly-connected component.

The proof is by contradiction.  Suppose that $G'$ is not acyclic.
Then let $u$ and $v$ be consecutive nodes in a directed cycle.  There
is a path from $u$ to $v$ consisting of a single edge.  There also is
a path from $v$ to $u$, because the nodes are in a cycle.  Since every
edge in $G'$ is also in $G$, these same two paths exist in the
original graph $G$.  Therefore, $u$ and $v$ are in the same
strongly-connected component of $G$.  But then the edge from $u$ to
$v$ should have been removed during the construction of $G'$.  Since
the the edge was not removed, we have a contradiction.  Therefore,
$G'$ is acyclic.
\end{proof}
}
\end{examproblem}
