\documentstyle[12pt,twoside]{article}
\input{macros-course}
\input psfig
%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}

\begin{document}

\pset{3}{September 17, 1996}{Start of Class, Tuesday, September 24}

{\bf Reading:} Sections 1.4-1.5, 2.3-2.5, 3.3, 6.1-6.2, 6.5.

\bigskip

\begin{problems}
\problem{\bf [15 points]}
% Euclidean algorithm.

Show all your work in the following:
\begin{enumerate}
\item
Use the Euclidean algorithm to calculate $\gcd(294,1386)$.
\item
Use the Euclidean algorithm to express $\gcd(294,1386)$ as a linear
combination of the numbers $294$ and $1386$.
%determine the coefficients in the
%expression of $\gcd(294,1386)$ as a sum of the form $a (294) + b
%(1386)$.
\item
What is the least common multiple of 294 and 1386, $\lcm(294,1386)$?
\end{enumerate}

\problem{\bf [15 points]}
% Lynch--Number of phases for the Euclidean algorithm
In class, it was shown that the number of passes used in the Euclidean
GCD algorithm for arguments $x$ and $y$ is at most $x + y$.
It is possible to improve this bound.
\begin{enumerate}
\item
Prove that when the Euclidean algorithm with inputs $x$ on $y$ calls
itself on new arguments $x'$ and $y'$, then 
the sum $x' + y'$ is at most $({3 \over 4}) (x + y)$.
\item
Use part (1) to get a better bound on the number of passes, using
induction. 
\end{enumerate}
%[[[check me carefully -- should always do that, in fact]]]

\problem{\bf [10 points]}
% RSA finger exercise
%Section 2.5, Exercise 32
Encrypt the message {\bf ATTACK} using the {\bf RSA} system with $n =
43 \cdot 59$ and $e = 13$, translating each letter into integers and
grouping together pairs of integers, as done in Example 10.

\problem{\bf [15 points]}
% GCD application
Olympic Hopscotch is played on a two-dimensional field of
squares, numbered by pairs of integers representing $x$ and $y$
coordinates in the usual way.  You may assume that the field is
infinite in all directions.

You are supposed to start in square $(0,0)$.
You are allowed to jump in only the following ways:
\begin{itemize}
\item
$12$ squares north, south, east or west. 
\item
$9$ squares north or south.
\item
$15$ squares east or west.
\end{itemize}
At the beginning of a game,
the referee calls out the number of a square, and you are supposed to
tell him either that it is 
{\em impossible} for you to jump to that square using the given moves,
or else to actually jump there.
\begin{enumerate}
\item
How do you determine whether or not it is possible to jump to a given
square?
\item
For those squares that it's possible to reach, give a method for
jumping there.
\end{enumerate}

\problem{\bf [15 points]}
% Set Identities
Let $A$, $B$, and $C$ be sets. Which of the following are correct set
identities?  For each, if it is a set identity, give a proof that it
is (using the style of argument used in class to prove the basic set
identities, or using the basic set identities themselves).  If it is
not a set identity, then give a counterexample.
\begin{enumerate}
\item
$(A - B) \cap (B - C) = \emptyset$
\item
$(B - A) \cup (C - A) = (B - (C \cup A)) \cup (C - (B \cup A))$
\item
$(A \oplus B) \oplus C = A \oplus (B \oplus C)$
\item
$(A \cap B) \times (B \cap C) =
(A \times C) \cap B^2 \cap (A \times B) \cap (B \times C)$
\end{enumerate}

\problem{\bf [15 points]}
%Section 6.1, Problems 22,24
\begin{enumerate}
\item
List the 16 different binary relations on the set $\{ 0,1 \}$.
\item
Which of the 16 relations in part (1) are
reflexive? symmetric? antisymmetric? transitive?
\end{enumerate}

\problem{\bf [15 points]}
% Equivalence relations
%Section 6.5, Problem 32

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}


\end{problems}
\end{document}
