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

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

\setcounter{page}{0}

\begin{document}

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

\begin{problems}


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

Base case: n=1 \\

$1^3 = 1^2 = 1$

Inductive Step: $H(n) \rightarrow H(n+1) $ \\

\begin{eqnarray*}
\left(\sum_{i=1}^{n+1} i\right)^2 &=& \left(\sum_{i=1}^n i + (n+1)\right)^2 \\
&=& \left(\sum_{i=1}^n i\right)^2 +2(n+1)(\sum_{i=1}^n i) + (n+1)^2 \\
&=& \sum_{i=1}^n i^3 +2(n+1)(\sum_{i=1}^n i) + (n+1)^2  \\
&=& \sum_{i=1}^n i^3 +2(n+1)n(n+1)/2 + (n+1)^2  \\
&=& \sum_{i=1}^n i^3 +(n+1)n(n+1) + (n+1)^2  \\
&=& \sum_{i=1}^n i^3 +(n+1)^3  \\
&=& \sum_{i=1}^{n+1} i^3 \\
\end{eqnarray*}


\problem
{\em 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$. 
}

We note that $a_1, a_2$ are both divisible by $7$.

Let $S$ be the set of numbers, $a_i$, which are not divisible by 7, where
$i \geq 3$.

If $S$ is non-empty, then by well-ordering, there is a least element, $a_m$.
If $a_m$ is formed by rule A, then $a_m=a_i+a_j$ where $i<k$ and $j<k$.
Since $a_m$ is the least element in $S$, $a_i$ and $a_j$ are divisible
by $7$, and so $a_i+a_j$ is divisible by 7, so $7 \mid a_m$, and
we have a contradiction.

If $a_m$ is formed by rule B, we have $a_m = a_{i_1} \cdot  a_{i_2} \cdot
 \ldots \cdot  a_{i_k} $
where all $a_{i_j} < a_m$. Since $a_m$ is the least element of $S$, 
$7 \mid a_{i_j}$
for all $1 \leq j \leq k$, and so, $k$ $7$'s can be factored
out of $a_m$ and $ 7 \mid (a_m / 7^{k-1})$ .
Again, we have a contradiction.

So $S$ must be empty, and all $a_i$ are divisible by $7$.



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

Number theory.

\begin{problemparts}
{ \em \problempart
Using Euclid's algorithm, or otherwise, find an $x$ such that 
\[43x \equiv 4 \pmod {105}. \] }
\begin{tabular}{lllll}
x & y & q & r & Equation \\
105 & 43 & 2 &19 & $ 105 = 43 \cdot 2 + 19 $\\
43 & 19 & 2 & 5 & $ 43 = 19 \cdot 2 + 5 $\\
19  & 5 & 3 & 4& $ 19 = 5 \cdot 3 + 4$\\
5 & 4 & 1 & 1& $ 5 = 4 \cdot 1 + 1 $\\
\end{tabular} 

Looking at the above equations and going in backwards order, we have
\begin{eqnarray*}
1 &=& 5-4 \\
 &=& 5-(19-5\cdot 3) \\
 &=& 5\cdot 4 - 19 \\
 &=& (43-19\cdot 2)\cdot 4 -19 \\
 &=& 43\cdot 4 - 19\cdot 9 \\
 &=& 43\cdot 4 - (105 - 43\cdot 2)\cdot 9 \\
 &=& 43 \cdot 22 - 105\cdot 9.
\end{eqnarray*}
and multiplying by 4
\begin{eqnarray*}
 1 &=& 43\cdot 22 - 105\cdot 9 \\
 4 &=& 43\cdot 88 - 105\cdot 36
\end{eqnarray*}

So, $x=88$.

{ \em \problempart Prove that if $p$ and $q$ are distinct primes, and $p
\mid a$ and $q \mid a$, then $pq \mid a$.}

Find the prime factorization of $a = p_1 p_2 p_3 \ldots p_n$.
If $p \mid a $, then for some $i$, $p_i = p$.  Similarly,
for some $j$, $p_j = q$. Rearranging the factors (by
commutativity), we have $a = (p_i p_j) p_1 p_2 p_3 \ldots p_n$.
So, $p_i p_j \mid a$ which means that $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$ \\
injection, surjection, bijection, $f^{-1}(x)=x$

\ppart $f: \reals^{+} \rightarrow \reals^{+} , f(x) = \frac{1}{x}$ \\
injection, surjection, bijection, $f^{-1}(x)=1/x$

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

\ppart $f: \reals \rightarrow \reals , f(x) = x^{3}$
% TVI check this (the cube root).
injection, surjection, bijection, $f^{-1}(x)={x^{1/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)$ \\

Disprove:\\
Take $f = \{(2,4), (5,4) \}$.  \\
Let $A = \{2\}$, $B = \{5\}$
$f(A) = \{4\}$,  $f(B) = \{4\}$,  \\
$A \cap B =  \emptyset $ \\
$f(\emptyset ) = \emptyset $ \\
$f(A) \cap f(B) = \{4\}$

so $f(A \cap B) \neq f(A) \cap f(B)$ \\

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

Prove true: \\
1.  Show $ x \in f(A \cup B)  \rightarrow x \in (f(A) \cup f(B))$ \\
Assume $x\in f(A\cup B)$, i.e., $f(y)=x$  for some $y\in A\cup B$.
Either $y\in A$ and $x=f(y)\in f(A)$ or $y\in B$ and $x=f(y)\in f(B)$.
In both cases $y\in f(A)\cup f(B)$.
2.  Show $ x \in f(A) \cup f(B)  \rightarrow x \in f(A \cup B)$ \\
Let $x\in f(A)\cup f(B)$.
Either $x=f(y)$ for some $y\in A$ or $x=f(y)$ for some $y\in B$.
In both cases $x=f(y)$ for some $y\in A\cup B$ and 
therefore $x\in f(A\cup 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$.

And equivalence class is reflexive, symmetric, and transitive.  

$(a,b) \sim (a,b)$ for all $(a,b)$ since $a+b=a+b$, so $\sim$ is reflexive.

If $(a,b) \sim (c,d)$ then $(c,d)\sim (a,b)$ because
if $a+d=b+c$ then also $c+b=d+a$, so $\sim$ is symmetric.

If $(a,b) \sim (c,d) \wedge (c,d) \sim (e,f)$ then $(a,b) \sim (e,f)$ 
because $(a+d=b+c) \wedge (c+f = d+e) $ implies $a+d+c+f = b+c+d+e$
and therefore $a+f = e+b$.

\ppart Partition the set $\{0,1,2\} \times \{0,1,2\}$ into the  distinct equivalence classes under $\sim$.

The equivalence classes of the above set are 
$\{(0,0),(1,1),(2,2)\}$, $\{(0,1),(1,2)\}$,
$\{(0,2)\}$, $\{(1,0),(2,1)\}$ and $\{(2,0)\}$.

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

There are $2n+1$ equivalence classes corresponding to 
representatives $(n,0),(n-1,0),\ldots,(1,0),(0,0),(1,0),\ldots,(n,0)$.

\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

Since, $b \geq 0$ and $y \geq 0$, and either the while loop is never 
entered because $y=0$, or $y$ continually decrements to 0.

\problempart Prove that this algorithm returns $a-b$.

Proof by induction on the number of iterations, $i$, through the while loop.
$H(i) = $ after the $i$th iteration, $x=a-i$ and $y=b-i$.

Base Case: H(1)\\
$x = a-1$, and $y=b-1$.

Inductive Step: \\
Assume $H(m)$, show $H(m+1)$.
$x_{m+1} = x_m -1$ and $y_{m+1} = y_m -1$ \\
by the inductive hypothesis, 
$x_{m+1} = a-i -1 = a-(i+1)$ and $y_{m+1} = b-i -1 = b-(i+1)$

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

Inductive hypothesis: $H(i)$: Separate(w) where $w$ is $i$ characters long, 
terminates.

Base case:\\
H(0): EMPTY(w) is true terminates.

Inductive step: \\
Assume $H(n)$, show termination for $H(n+1)$.

if (FIRST='0'), then Separate(w) terminates if the call to Separate(REST(w))
terminates. REST(w) only has $n$ characters, so it terminates
by the inductive hypothesis.  The argument for FIRST(w)='1' is similar,
so Separate(w) 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


Inductive Hypothesis:  H(n): if $w$ is a string of length $n$,
with $i$ 0's and $j$ 1's, $i+j=n$, then Separate(w) returns
a string with $i$ 0's followed by $j$ 1's.

If (FIRST(w) ='0') then there are $i-1)$0's and $j$ 1's in REST(w), 
and Separate(REST(w)) returns $i-1$ 0's
followed by $j$ 1's by the inductive hypothesis.  So Separate(w) returns
$1+(i-1)=i$ 0's and $j $ 1's.

Similarly, if (FIRST(w) = '1'), then there are 
$i$ 0's and $j-1$ 1's in REST(w), 
and Separate(REST(w)) returns $i$ 0's
followed by $j-1$ 1's by the inductive hypothesis.  So Separate(w) returns
$i$ 0's and $j-1+1=j $ 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.  

Variables:\\
A: Amount of money at bridge A\\
B: Amount of money at bridge B \\
cars: number of cars on the bridge\\

Initial conditions:\\
$A=B=cars=0$\\

Transitions: 

BridgeA(car) \\
{\em Precondition: } \\
$A-B < 15$ \\
there's a car at the A's booth \\
{\em effects: } \\
$A = A +0.25$ \\
$cars=cars+1$ \\

BridgeB(car) \\
$A-B < 15$ \\
there's a car at the B's booth \\
{\em effects: } \\
$B = B +0.25$ \\
$cars=cars-1$ \\

\problempart
Prove
that there will never be too many cars on the bridge.

Invariant: \\
$4(A-B) = cars \leq  60 $

Initial conditions:
$0 = 0 \leq 60$ 

After Transition A: \\
$A_{new} = A + 0.25$ and
$cars_{new} = cars +1$
so $4(A_{new} -B) = 4((A+0.25)) -B) = 4(A-B) +1 = cars +1= cars_{new}$.
Also, $4(A-B) = cars < 60 \rightarrow cars +1 = cars_{new} \leq 60$,
(because the precondition has $A-B <15$).

After Transition B:\\
$B_{new} = B + 0.25$
$cars_{new} = cars +1$
so $4(A -B_{new}) = 4(A-(B-.025)) = 4(A-B) -1 = cars -1= cars_{new}$.
Also, since $cars \leq  60$ to start, it will still be $cars \leq 60$.
\end{problemparts}

So the invariant is satisfied and the number of cars is never greater
than $60$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%4


\bigskip




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