\documentstyle[12pt,twoside]{article}

\newcommand{\problem}{%
  \paragraph{Problem}}
\newcommand(\solution}{%
  \paragraph{Solution}}

\begin{document}

\begin{problems}

%BEGIN Kavita's problems
% Fall 1998


%**************
%   PSET 3    *
%**************

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

\problem {\bf (10 points)} 
John Dunagan, one of the 6.042 TAs, gave our friend Theory Pig a new
toy for his birthday.  The toy consists of a $3 \times 3$ grid of
squares, where each square contains one of the letters in THEORY PIG.
Each row can be rotated right or left and each column can be rotated
up or down.  The effects of such rotations are explained in the figure
below.

\[
\begin{array}{|c|c|c|}
\hline
H & E & Y \\ \hline
P & I & G \\ \hline
R & O & T \\ \hline
\end{array}
\rightarrow
\begin{array}{|c|c|c|}
\hline
R & E & Y \\ \hline
H & I & G \\ \hline
P & O & T \\ \hline
\end{array}
\rightarrow
\begin{array}{|c|c|c|}
\hline
R & E & Y \\ \hline
I & G & H \\ \hline
P & O & T \\ \hline
\end{array}
\]

The first picture shows Theory Pig's new toy configured as he first
received it.  The leftmost column is then rotated downward to give the
middle picture.  The $H$ and $P$ move down, and the $R$ rotates back
up to the top.  Then the middle row is rotated leftward to produce the
final picture.  The $I$ and $G$ move left, and the $H$ rotates back
around to the right.

Naturally, Theory Pig wants to arrange the letters so as to spell his
name.

\[
\begin{array}{|c|c|c|}
\hline
T & H & E \\ \hline
O & R & Y \\ \hline
P & I & G \\ \hline
\end{array}
\]

Based on prior experience, Theory Pig is afraid that the toy might be
specially designed to make this delightful combination utterly
impossible, no matter what sequence of row and column rotations he
attempts.

\begin{problemparts}

\problempart Model Theory Pig's toy as a state machine.

\solution{
\begin{itemize}

\item The set of states $Q$ consists of all arrangements of the letters in
THEORY PIG on a $3 \times 3$ grid.

\item The set of start states $Q_0$ consists of the single arrangement HEY PIG,
ROT!

\item The set $\delta \subseteq Q \times Q$ consists of all pairs of states
$(q_1, q_2)$ such that $q_2$ can be obtained from $q_1$ by a row or
column rotation.

\end{itemize}
}

\problempart Given the initial configuration of the toy indicated above,
prove that Theory Pig can never spell his name.

\solution{
The idea is to keep track of the number of letter pairs that are out
of order relative to $THEORYPIG$.  For example, in the initial
configuration, $H$ appears before $T$; this pair of letters is out of
order, because $T$ appears before $H$ in $THEORYPIG$.  We will refer
to an out-of-order letter pair as an {\em inversion}.  In the initial
configuration, there are 17 inversions:

\[
\begin{array}{ccccc}
HT & ET & YT & YO & YT \\
PR & PO & PT & IR & IO \\
IT & GR & GO & GT & RO \\
RT & OT
\end{array}
\]

The key observation is that a rotation always changes the number of
inversions by an even amount.  Since the puzzle initially has an odd
number of inversions, no sequence of rotations can reduce the number
of inversions to 0, an even number.  Consequently, there will always
be at least one pair of letters out of order, and Theory Pig can never
spell out his name.

The main challenge is to prove that a rotation always changes the
number of inversions by an even amount.  We will prove this claim in a
sequence of lemmas, and then we will prove the main result as a
theorem.

\begin{lemma}
Swapping an adjacent pair of letters changes the number of inversions
by an odd amount.
\end{lemma}

\begin{proof}
If the letters were initially in the same order as in $THEORYPIG$,
then the number of inversions is increased by 1, an odd number.
Otherwise, the letters were initially in the wrong order, and the
number of inversions is decreased by 1, also an odd number.
\end{proof}

\begin{lemma}
Swapping any pair of letters changes the number of inversions by an
odd amount.
\end{lemma}

\begin{proof}
We will show how to swap of any pair of letters using an odd number of
swaps of adjacent letters.  The preceding lemma says that swapping
adjacent letters changes the number of inversions by an odd amount.
Therefore, swapping any pair of letters changes the number of
inversions by an odd amount, because the sum of an odd number of odd
numbers is odd.

All that remains is to show how to swap any pair of letters using an
odd number of swaps of adjacent letters.  Suppose that we are swapping
letters $x$ and $y$, where $x$ is on the left, $y$ is on the right,
and there are $k$ stray letters between the two.  First, we swap $x$
with its right neighbor $k$ times.  This leaves $x$ directly left of
$y$ and leaves all the stray letters shifted one place to the left.
Then we swap $x$ and $y$, putting $x$ into $y$'s original positions.
Finally, we swap $y$ with its left neighbor $k$ times.  This puts $y$
into $x$'s original position and shifts the stray letters back to
their original position.  The total number of swaps of adjacent
letters is $k + 1 + k = 2k + 1$, which is odd for all $k \geq 0$.
\end{proof}

\begin{lemma}
Rotating any row or column changes the number of inversions by an even
amount.
\end{lemma}

\begin{proof}
We show below that any row or column rotation can be obtained by two
swaps.  The preceding lemma says that every swap changes the number of
inversions by an even amount.  Since the sum of two odd numbers is
even, any row or column rotation changes the number of inversions by
an even amount.

Here is how to obtain a rotation from two swaps.  Suppose that the
letter sequence $xyz$ appears in some row or column.  Swapping $x$
with $y$ and then swapping $x$ with $z$ creates the sequence $yzx$,
which corresponds to a leftward or upward rotation.  Swapping $z$ with
$y$ and then $z$ with $x$ creates the sequence $zxy$.  This corresponds
to a rightward or downward rotation.
\end{proof}

\begin{theorem}
Theory Pig can never spell his name.
\end{theorem}

\begin{proof}
The proof uses the Invariant Theorem.  We prove the following
invariant: the number of inversions in the letter sequence relative to
$THEORYPIG$ is always odd.

The invariant holds in the single start state, because the number of
inversions is initially 17, which is odd.  Furthermore, the invariant
is maintained under every transition.  The preceding lemma states that
every row or column rotation changes the number of inversions by an
odd amount.  Therefore, if the number of inversions was odd before a
transition, then the number of inversions must be odd after a
transition.  Thus the invariant is established by the Invariant
Theorem.

Since the number of inversions relative to $THEORYPIG$ is always odd,
the string can never be formed.
\end{proof}
}

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

%END   Kavita's problems

%BEGIN Joe's problems
%END   Joe's problems

%BEGIN Ray's problems


%%%%%%%%%%%%%  S99 ps1


\problem (\S 1.4, Exercise 12) We will prove that if the power sets of
$A$ and $B$ are equal, then sets $A$ and $B$ are equal.  In
particular, we will prove $A = B$ by showing that each set is
contained in the other.

First, we show that $A \subseteq B$.  Let $x$ be an element of $A$.
Then $\{ x \}$ is an element of $P(A)$, the power set of $A$.  By the
assumption that $P(A)= P(B)$, we know that $\{ x \}$ is an element of
$P(B)$.  This implies that $x \in B$.  Therefore $A \subseteq B$.  The
argument that $B \subseteq A$ is symmetric.  Therefore, $A = B$ as
claimed.

\problem Prove that $\card{A \oplus B} = \card{A} + \card{B} - 2\card{A
\cap B}$.  \hint See \S1.5, paragraph following Example 5.


\solution Note that $|A| + |B|$ counts each element that is in $A$ but
not in $B$ or in $B$ but not in $A$ exactly once, and each element
that is in both $A$ and $B$ exactly twice.  Thus, $|A| + |B| - 2 |A
\cap B|$ counts only elements that are in $A$ but not in $B$ or in $B$
but not in $A$.  This is precisely the set $A \oplus B$, so we have

\begin{eqnarray*}
|A \oplus B| & = & |A| + |B| - 2 |A \cap B|.
\end{eqnarray*}

\problem (\S 1.5, Exercise 26)  We prove that

\begin{eqnarray*}
A \oplus B & = & (A - B) \cup (B - A)
\end{eqnarray*}

by showing that each set contains the other.  Let $S$ be the set on
the left side of the equation, and let $T$ be the set on the right
side.  Our goal is then to prove that $S = T$.

First, we prove that $S \subseteq T$.  If $x \in S$, then either $x
\in A$ and $x \not\in B$ or else $x \not\in A$ and $x \in B$.  In the
former case, $x \in A - B$, and so $x \in T$.  In the latter case, $x
\in B - A$, and so $x \in T$ again.  Thus, $S \subseteq T$.

Now, we prove that $T \subseteq S$.  If $x \in T$, then there are two
cases: either $x$ is only an element of $A - B$ or only an element of
$B - A$.  (Note that $x$ can not be an element of both sets; they are
disjoint.)  In the first case, $x$ is an element of $A$, but not $B$,
so $x \in S$.  In the second case, $x$ is an element of $B$, but not
$A$, so $x \in S$ again.  Thus, $T \subseteq S$.

Since each set contains the other, $S = T$ as claimed.


%END   Ray's problems

%BEGIN Ivan's problems (Spring '98)

%%%%%
%pset1, problem1 in spring98 (variant of F97)
\problem\hfill

\bparts

\ppart

The {\em symmetric difference}, $A \oplus B$, of two sets, $A$
and~$B$, is defined by
\[A \oplus B = (A \cup B)-(A \cap B).\]

Show that $A \oplus B = (A-B) \cup (B-A)$.

\ppart Prove that $\oplus$ is associative.

\eparts

%%%%% SOLUTION
%pset1, problem1 in spring98 (variant of F97)

\solution{
\bparts

\ppart

The {\em symmetric difference}, $A \oplus B$, of two sets
$A$ and~$B$, is defined by
\[A \oplus B = (A \cup B)-(A \cap B).\]

Show that $A \oplus B = (A-B) \cup (B-A)$.

First we show that  $(A-B) \cup (B-A) \subseteq (A \cup B)-(A \cap B)$.

Let $x \in (A-B) \cup (B-A)$. Then $x \in (A-B) \vee x \in (B-A)$.
So, $x \in A$, but $x \not\in B$, or $x \in B$, but $x \not\in A$
from which it follows that $x \in A \vee x \in B$, but $x$ is not in both
$A$ and $B$. So, $x \in A \cup B$, but $x \not\in A \cap B$, therefore
$x \in  (A \cup B)-(A \cap B)$.\\

Now we show that $(A \cup B)-(A \cap B) \subseteq (A-B) \cup (B-A)$.

Let $x \in (A \cup B)-(A \cap B)$.  Then $x \in A \cup B$, but
$x \not\in A \cap B$. So  $x \in A \vee x \in  B$, but $x$ is not in both
$A$ and $B$.
We take cases.
Case 1:
If $x \in A$, then since $x$ is not in $A \cap B$, we conclude that
$x$ is not in $B$.  Therefore $x \in A-B$.\\
Case 2:
If $x \in B$, then by the same argument, $x$ is not in $A$,
therefore $x \in B-A$. So $ x \in A-B \vee x \in B-A$, therefore
$x \in (A-B) \cup (B-A)$.\\

The two inclusions establish the set equality.

\ppart Prove that $\oplus$ is associative.\\

Using membership tables:

\begin{center}
\begin{tabular}{||c|c|c|c|c||}\hline
$A$ $B$ $C$& $A \oplus B$ & $B \oplus C$ & $A \oplus (B \oplus C)$ & $(A \oplus B) \oplus C$ \\ \hline
1 1 1 & 0 & 0 & 1 & 1 \\ \hline
1 1 0 & 0 & 1 & 0 & 0 \\ \hline
1 0 1 & 1 & 1 & 0 & 0 \\ \hline
1 0 0 & 1 & 0 & 1 & 1 \\ \hline
0 1 1 & 1 & 0 & 0 & 0 \\ \hline
0 1 0 & 1 & 1 & 1 & 1 \\ \hline
0 0 1 & 0 & 1 & 1 & 1 \\ \hline
0 0 0 & 0 & 0 & 0 & 0 \\ \hline

\end{tabular}
\end{center}

\eparts
} %solution

%END   Ivan's problems

%BEGIN George's problems
%END   George's problems

%BEGIN Josh's problems
%END   Josh's problems

%BEGIN Tina's problems

%problems for Fall 99
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Pset 1, problem 2
\problem  \textbf{Sets}
\bparts
\ppart \S 1.4, Exercise 14.  Prove it or give a counterexample.

\solution{The union of all the sets in the power set of a set $X$ must be exactly
$X$. In other words, we can recover $X$ from its power set, uniquely. 
Therefore the answer is yes.}

\ppart \S 1.5, Exercise 12(e).

\solution{To establish the equality, we need to prove inclusion in both
directions. To prove that $(B-A)\cup(C-A)\subseteq(B\cup C)-A$, 
suppose that $x\in(B-A)\cup(C-A)$.
Then either $x\in(B-A)$ or $x\in(C-A)$. Without loss of generality, assume the
former (the proof in the latter case is exactly parallel.) Then $x\in B$
and $x\not\in A$. From the first of these assertions, it follows that
$x\in B\cup C$. Thus we can conclude that $x\in (B\cup C)-A$, as desired. For the
converse, that is, to show that $(B\cup C) -A\subseteq (B-A)\cup (C-A)$, suppose that
$x\in (B\cup C)-A$. This means that $x\in (B\cup C)$ and $x\not\in A$. 
The first of these
assertions tells us that either $x\in B$ or $x \in C$. Thus either $x\in B-A$ or
$x\in C-A$. In either case, $x\in (B-A)\cup (C-A)$. (An alternative proof could be
given by using Venn diagrams, showing both sides represent the same
region.)}

\ppart \S 1.5, Exercise 14.

\solution{That $A\subseteq(A\cap B)\cup (A\cap \bar{B})$ follows from the 
fact that every element $x\in A$ is an
element of either $A\cap B$ (if $x\in B$) or $A\cap \bar{B}$ (if $x\not\in B$). 
On the other hand, if
$x\in (A\cap B)\cup (A\cap \bar{B})$, 
then either $x\in A\cap B$ or $x\in A\cap \bar{B}$. 
In either case, $x\in A$ by the definition of intersection.}

\ppart \S 1.5, Exercise 36.

\solution{We note that these sets are decreasing, that is 
$A_1\supseteq A_2 \supseteq A_3 \supseteq \ldots$.
Therefore the union of any collection of these sets is just the
one with the smallest subscript, and the intersection is just the one
with the largest subscript.\\
a) $A_1=\{1,2,3,\ldots\}$   \ \ \ b) $A_n=\{n, n+1, n+2,\ldots\}$}

\eparts
%%%%%%%%%%%%%%%%

%END   Tina's problems

\end{problems}

\end{document}



