
\documentclass[12pt,twoside]{article}
\usepackage{amsmath}
\input{/pub/www/classes/6.042/fall99/inputs/macros-course}

%\def\cent{{\not\!\mathrm{c}}}

%\newcommand{\solution}[1]{}
\newcommand{\solution}[1]{\bigskip {\bf Solution:}\\ #1\bigskip}


\begin{document}

\tutn{5}{9/24/99}{September 24, 1999}

\begin{problems}

\problem
A complete binary tree is defined inductively as follows,
\begin{itemize}
\item In height $0$, it consists of one node which is called the root.
(see Fig. 1)
\item In height $h+1$, it consists of a distinguished node called the root and
two complete binary trees of height $h$, called the left and right subtree.
(see Figs. 2 and 3)
\end{itemize}

We will refer to the root of the tree as the {\em father}
 of the roots of its right 
and left subtrees.

The {\em depth} of a node in a tree is defined as follows.
\begin{itemize}
\item depth(root)=0
\item depth(n)=1+depth(father of n), $\forall$ nodes n $\neq$ root.
\end{itemize}
e.g. in Fig. 3, depth(r)=0, and depth(l)=h.

%\begin{enumerate}
%\item
\bparts
\ppart
Let $T$ be a complete binary tree of height $h$. 
The {\it height of a node} in $T$ is 
$h - depth (node)$, 
e.g. in Fig. 3, height(r)=h, and height(l)=0.

Prove by induction that the sum of the heights of all the
nodes in $T$ is $2^{h+1} -h -2$

\solution{
The first part is an easy  warm up to get used to the concept of a tree.
To solve the first part let P(h) be the sum of the heights of a tree of height
h is $2^{h+1} -h -2$. Base case follows as P(0)=0. 
Inductive step: need to realize that the height of all nodes remains the same
except for the new root whose height becomes h+1. So,
add up the old height of left and right subtreees+height of sub tree, to get
$P(h+1)=P(h)2 +{h+1}=2^{h+2} -2h-4+{h+1} =2^{h+2} -(h+1) -2$. QED}

\ppart
Let $T$ be a complete binary tree of height $h$. 
Prove by induction that the sum of the depths of all the
nodes in $T$ is $2 +h2^{h+1} -2^{h+1}$.

\solution{
The second part requires more work. 
You need to figure out how many nodes are
in a complete binary tree of height h, as an intermediate result. This can
be trivially done by induction on h and the answer is ${2^h+1 -1}$.

Now, set P(h)= the sum of all depths of all nodes in a tree of height h is 
 $2 +h2^{h+1} -2^{h+1}$.  Base case follows since P(0)=0.
Inductive Step: all nodes in right sub tree and (left sub tree) are now one
level deeper.
The root adds nothing as it is at depth 0. So, 
to compute P(h+1)= 2P(h) + number of nodes are in the right sub-tree + number of
nodes in the left sub-tree. This suffices as each old node contributes a +1 to the
new sum. Now lets do the algebra: $P(h+1)=2P(h)+2(2^{h+1}-1) = 2 +(h+1)2^{h+2} -2^{h+2}$.
QED
}
\eparts

\problem

\begin{enumerate}  
\item
Let m,n be positive integers.
Recall the $gcd(n,m) =$ greatest common divisor of n and m, and 
$lcm(n,m)=$ smallest positive integer that is divisable by both  n and m.
Prove that $gcd(n,m) \cdot lcm(n,m) = m\cdot n$. 
\item
Prove that
If $n^j=1$ mod $m$ and $n^k=1$ mod $m$, then $n^{gcd(j,k)}=1$ mod $m$.
(Hint: there exists two integers a,b s.t. $gcd(j,k)=aj+bk$).
\item
Suppose $n,m$ are two integers such that
$gcd(n,m)=1$ and moreover $n$ mod $m$, $n^2$ mod $m$, ..., $n^{m-1}$ mod
$m$ are all distinct numbers. Show that $m$ is prime.
(Hint: show that for all $1\leq j \leq (m-1)$, $gcd(n^j,m)=1$ as
an intermediate step.)
\end{enumerate}

\solution{

Part 1 uses the fact that each $n>1$ can be written as a unique product of prime
powers (i.e unique prime factorization or as we called it in lecture the
fundamental theorem of arithmetic (FTA)). It also  uses the 
well ordering principle(WOP).
Let $m = \Pi_{0\leq i\leq k}{p^{{\alpha_i}}}$ and 
$n = \Pi_{0\leq i\leq k} {p^{{\beta_i}}}$ where $p_i$'s are {\bf all} the primes occurring in the
factorization of either m and n in increasing order
(note that some of the $\alpha_i$'s and $\beta_i$'s are 0). 
By WOP, it was shown in the book  page 19, example 13, that
$gcd(m,n)= {p_1^{min{( \alpha_1 ,\beta_1)}   }} {p_2^{min{( \alpha_2 ,\beta_2)}}} \ldots {p_k^{min{( \alpha_k ,\beta_k)} }}$. 
Similarily, in page 120, it was shown that
$lcm(m,n)= {p_1^{max{( \alpha_1 ,\beta_1)}   }} {p_2^{max{( \alpha_2 ,\beta_2)}}} \ldots {p_k^{max{( \alpha_k ,\beta_k)} }}$. 

Now, since for all $\alpha,\beta$, $\alpha + \beta = \max{(\alpha, \beta)} + \min{(\alpha,\beta)}$,
it follows that $mn=gcd(m,n)+lcm(m,n)$. QED.


Part 2. 
Let $gcd(j,k)=aj-bk$ for some integers $a,b$. Then, 
$n^{bk}n^{gcd(j,k)}= n^{aj-bk+bk}= ({n^j})^a = 1$ mod $m$ and
since $n^{bk}=1$ mod $m$, then $n^{gcd(j,k)} = 1$ mod $m$.

Part 3.
If the numbers $n^1$ mod $m$  $n^2$ mod $m$ ,.... $n^{m-1}$  mod $m$ 
are all relatively prime and distinct then they must coincide
exactly with the numbers 1,2,...,m-1. Thus all numbers
smaller than m are relatively prime  to it, namely no number other
than m and 1 divide it, which means that m is a prime.

}

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

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

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

Use the well-ordering principle to prove that every element in the
sequence is a  multiple of $7$. 
({\it Hint:  In case you have forgotten, the well-ordering principle says
that every nonempty set of naturals has a smallest element.})

\solution{
\begin{proof}
Let $S =$ \{all elements in the sequence that are not multiples of $7$ \}. \\
Assume that $S$ is nonempty.  Then, by well-ordering, it has a smallest 
element $a_{n}$. \\
If  $a_{n}$ is obtained by rule A,  then $a_{n} = a_{i} +  a_{j}$ 
for some  $a_{i}$ and $a_{j}$ smaller than $a_{n}$. But then  $a_{i}$ and
$a_{j}$ are multiples of $7$ therefore $a_{n}$ has to be a multiple of $7$
also. \\
If  $a_{n}$ is obtained by rule B, then there are $k$ smaller elements
in the sequence ,that are multiples of $7$, so we can write them in the form
$a_{k} = 7n_{k}$. $a_{n}$ is the product of the $a_k$
divided by $7^{k-1}$.  Then we can write \\

\begin{displaymath}
a_{n} = (\prod_{i=1}^{k} (7n_{i}))/7^{k-1} = 7(\prod_{i=1}^{k} n_{i})
\end{displaymath}

Therefore $a_{n}$ is also a multiple of $7$.
\end{proof}
}

\end{problems}

\end{document}
