%evens/odds
%reverse
%inverse

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

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

\setcounter{page}{0}

\begin{document}

\handout{pq1}{Practice Quiz 1}{March 13, 1997}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problems}


\problem
Prove by induction that 
\[ {\displaystyle \sum_{i=1}^n i^3 =  \left(\sum_{i=1}^n i\right)^2}.\]

\problem
An infinite sequence of natural numbers $a_1, a_2, a_3$, \ldots is
defined in such a way that $a_1 = 14, a_2 = 35$, and each later
$a_i$, $i \geq 3$, is obtained using one of the following rules:\\

\vspace{.01in}
{\bf Rule A} Choose any two preceding elements of the sequence and define $a_i$
to be their sum. \\

\vspace{.01in}
{\bf Rule B} Choose any number $k \geq 1$ of preceding elements of the sequence,
and define $a_i$ to be their product divided by $7^{k-1}$. \\

\vspace{.01in}
Use the well-ordering principle to prove that every element in the
sequence is a  multiple of $7$. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%3
\problem

Number theory.

\begin{problemparts}
\problempart
Using Euclid's algorithm, or otherwise, find an $x$ such that 
\[43x \equiv 4 \pmod {105}. \]
\problempart Prove that if $p$ and $q$ are distinct primes, and $p
\mid a$ and $q \mid a$, then $pq \mid a$.
\end{problemparts}


\problem Which of the following functions are injections? surjections?
bijections?  If a function is a bijection write down its inverse.

\begin{problemparts}

\ppart $f: \reals \rightarrow \reals , f(x) = x$ \\

\ppart $f: \reals^{+} \rightarrow \reals^{+} , f(x) = \frac{1}{x}$ \\

\ppart $f: \naturals \rightarrow \naturals , f(x) = x^{2}$ \\

\ppart $f: \reals \rightarrow \reals , f(x) = x^{3}$

\end{problemparts}



\problem
Let $f:U \rightarrow V$ be an arbitrary function and $A,B$ be arbitrary 
subsets of $U$. Prove or disprove the following claims (recall that
$f(A)=\{f(a) \mid a \in A\}$.\\
a) $f(A \cap B) = f(A) \cap f(B)$ \\

b) $f(A \cup B) = f(A) \cup f(B)$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%3
\problem 
Let $(a,b) \sim (c,d)$ if $a+d = b+c$.
\begin{problemparts}
\ppart Prove that $\sim$ is an equivalence relation on $\integers \times \integers$.
\ppart Partition the set $\{0,1,2\} \times \{0,1,2\}$ into the  distinct equivalence classes under $\sim$.
\ppart How many distinct equivalence classes under $\sim$ are there on
the set $\{0,1,\ldots, n\} \times \{0,1,\ldots, n\}$? You do not need
to prove your answer. 
\end{problemparts}

\problem Consider the following algorithm for performing subtraction
by repeated decrements.  It takes two natural numbers $a$ and $b$.

\begin{tabbing}
else \= else \= else \= else \=\kill
Sub$(a,b)$\\
\\
$x\leftarrow a$\\
$y \leftarrow b$\\
while $(y>0)$\\
\>   $x\leftarrow x-1$\\
\>   $y \leftarrow y-1$\\
return $x$.\\
\end{tabbing}

\begin{problemparts}
\problempart Prove that this algorithm terminates
\problempart Prove that this algorithm returns $a-b$.
\end{problemparts}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage
\problem
You are given the following operations on a string:

        FIRST$(w)$ -- returns the first character of a string or $\epsilon$ if 
        $w=\epsilon$ \\
        REST$(w)$ -- returns the string w minus w's first character.  if 
        $w=\epsilon$, then returns $\epsilon$ \\
        EMPTY$(w)$ -- returns TRUE if $w$ is $\epsilon$, FALSE otehrwise. \\

        The alphabet in this case is {0,1}.
        $a \cdot w$ is the character or string $a$, concatenated with $w$.


\begin{tabbing}
else \= else \= else \= else \=\kill
Separate$(w)$\\
\>          if (EMPTY$(w)$) return ($\epsilon$);\\
\>        else  if (FIRST$(w)$='0') \\
\>\>            return ('0' $\cdot$ separate(REST$(w)$));\\
\>          else\\
\>\>            return (separate(REST$(w)$)$\cdot'1'$);
\end{tabbing}

\begin{problemparts}
\problempart Prove that this algorithm terminates.
\problempart
Prove that if the input to the above algorithm is a string with $a$
0's and $b$ 1's, then the output is the string consisting of $a$ 0's
followed by $b$ 1's
\end{problemparts}

%10
\problem

The Massachusetts Transit Authority has just built a new one-way
bridge that will collapse if more than 60 cars are on it at the same
time.  To prevent this from happening, they've put a 25 cent toll both
$A$ at the entrance and a 25 cent toll booth $B$ at the end.  A car
deposits 25 cents at $A$ go onto the bridge and 25 cents at $B$ to get
off.  At $A$, they only let cars on when the difference between the
amount of money at $A$ and at $B$ is less than 15 dollars.  

\begin{problemparts}
\problempart Describe a
state machine that models the bridge, and list its transitions.  
\problempart
Prove
that there will never be too many cars on the bridge.
\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%4


\bigskip




\end{problems}
\end{document}
% Local Variables: 
% mode: latex
% TeX-master: t
% End: 
