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

\begin{document}
\pset{4}{February 25, 1997}{March 4, 1997}

{\bf Reading:} Sections 2.3--2.5, and 3.4-3.5 of {\it Discrete
  Mathematics and its Applications} by Kenneth H. Rosen.  Warning: we
take a different approach than 3.5; it should be read for intuition
  rather than method.

\begin{problems}

\problem  Let $n$ be a positive integer with no factors (other than 1) that are
perfect squares.  Let $a$ be the sum of the factors of $n$.  Let $b$ be the sum
of the squares of the factors of $n$.  Let $c$ be the sum of the factors
of $n^3$.  Prove using well-ordering that $a \cdot b = c$.

\problem Fill in the missing proof from class, that if $p \mid
a_1a_2\cdots a_k$, then $(\exists i) (p \mid a_i)$.

\problem Show that if $a,b,$ and $m$ are positive integers such that $m \geq
2$ and $m \mid (a-b)$, then $\mbox{gcd}(a,m) = \mbox{gcd}(b,m)$.

\problem Let $a$ and $b$ be positive integers.  The least common
multiple of $a$ and $b$ is defined to be the smallest positive integer
they both divide.  Prove that this quantity always exists.  Prove that
$a \cdot b = \mbox{gcd}(a,b) \cdot \mbox{lcm}(a,b)$.

\problem 
We are given two buckets, $A$ and $B$, a water hose, a receptacle, and a
drain.  The buckets and receptacle are initially empty.
The buckets are labelled with their capacities, which are the
positive integers $a$ and $b$, respectively.
The receptacle can be
used to store an unlimited amount of water, but
has no measurement markings.  Excess water can
be dumped into the drain.
Consider the following ``Die Hard'' operations:
\begin{itemize}
\item fill bucket $A$ or bucket $B$ from the hose
\item pour from the receptacle to either $A$ or $B$ until it is full
or the receptacle is empty (whichever happens first)
\item empty bucket $A$ or bucket $B$ to the drain or the receptacle
\item pour from $A$ to $B$ until either $A$ is empty or $B$ is full
(whichever happens first)
\item pour from $B$ to $A$ until either $B$ is empty or $A$ is full
(whichever happens first)
\end{itemize}
Let $c = \mbox{gcd}(a,b)$.  Let $g$ be a positive integer.
Prove that we can put $g$ gallons into the
receptacle using the above operations if, and only if, $c \mid g $.  

\problem Use Euclid's algorithm to compute $c=\mbox{gcd}(171,63)$ and compute
integers $x$ and $y$ for which $171x+63y=c$ (show your work).  Using
the model of the ``Die Hard'' problem, give an explicit scheme for putting
exactly 18 ounces of water into the receptacle (the final holder)
using a 171 ounce and a 63 ounce bucket.

\problem
Prove the correctness of the following algorithm for calculating $m^n$.  
Assume that initially, for any call to Power$(m,n)$, $n \ge 1$.

{\bf procedure} Power$(m,n)$

{\bf if} $(n = 1)$
    
\hspace{.5in} {\bf return}$(m)$

{\bf  else }

\hspace{.5in}
    {\bf return}$($Power$(m,\lfloor n/2 \rfloor) *$ Power
    $(m,n-\lfloor n/2 \rfloor))$

\smallskip

(note that $ \lfloor x \rfloor$  truncates to an integer, so $\lfloor
5/2 \rfloor= 2$.  See Rosen p. 68)

\problem 
Prove that the following algorithm for computing the Fibonacci numbers is 
correct.

{\bf procedure} Fib($n$)

{\bf if} $n=0$ then $y:=0$

{\bf else}

\hspace{.5in} $x:=0$

\hspace{.5in} $y:=1$

\hspace{.5in} {\bf for} $i:=1$ to $n-1$

\hspace{1in} $z:=x+y$

\hspace{1in} $x:=y$

\hspace{1in} $y:=z$

\hspace{.5in} {\bf end for}

{\bf return}($y$)

($y$ is the $n$th Fibonacci number).

\problem {\bf (Optional).} Consider the ``Die Hard'' problems.  Can you
solve problems 5 and 6 if you are forbidden to ever remove
water from the receptacle?

\end{problems}



\end{document}










% Local Variables: 
% mode: latex
% TeX-master: t
% End: 
