\documentclass[12pt]{article}
\usepackage{latex-macros/course}% !! Use the macros

\renewcommand{\reading}{Week 10 Notes on Series and Asymptotics.}

\begin{document}
\problemset{8}

\newcommand{\beqn}{\begin{eqnarray*}}
\newcommand{\eeqn}{\end{eqnarray*}}
\newcommand{\rem}{\text{ rem }}


\begin{problem}
(This problem is carried over from Friday, April 2, class problems.)

A critical question about RSA (which is described below) is whether
decrypting an encrypted message always gives back the original
message.  Mathematically, this amounts to asking whether:

\[
m^{de} \equiv m \pmod{pq}.
\]

Note that the procedure ensures that $de = 1 + k (p - 1)(q - 1)$ for
some integer $k$.

\bparts

\ppart Use Euler's Theorem to prove that $m^{de} \equiv m \pmod{pq}$
for all messages $m$ relatively prime to $pq$.  In practice, is $m$
likely to be relatively prime to $pq$ or not?

\solution{
\begin{eqnarray*}
m^{de} & \equiv & m^{1 + k \phi(pq)} \pmod{pq} \\
       & \equiv & m \cdot (m^{\phi(pq)})^k \pmod{pq} \\
       & \equiv & m \cdot 1^k \pmod{pq} \\
\end{eqnarray*}

The first step uses the fact that $\phi(pq) = (p - 1)(q - 1)$, the
second uses exponent laws, and third uses Euler's Theorem.  If $p$ and
$q$ are hundred-digit primes, $m$ is very likely to be relatively
prime to both $p$ and $q$.}

\ppart This congruence actually holds for all messages $m$.  First,
use Fermat's theorem to prove that $m \equiv m^{de} \pmod{p}$ for all
$m$.

\solution{If $m$ is a multiple of $p$, then the claim holds because
both sides are congruent to 0 mod $p$.  Otherwise, suppose that $m$ is
not a multiple of $p$.  Then:

\begin{eqnarray*}
m^{1 + k (p-1) (q-1)}
	& \equiv &	m \cdot (m^{p-1})^{k (q-1)} \pmod{p} \\
	& \equiv &	m \cdot 1^{k (q-1)} \pmod{p} \\
	& \equiv &	m \pmod{p}
\end{eqnarray*}

The second step uses Fermat's theorem, which says that $m^{p - 1}
\equiv 1 \pmod{p}$ provided $m$ is not a multiple of $p$.
}

\ppart By the same argument, you can equally well show that $m \equiv
m^{ed} \pmod{q}$.  Show that these two facts together imply that $m
\equiv m^{ed} \pmod{pq}$ for all $m$.

\solution{We know that:
 \begin{align*}
p & \divides (m - m^{ed}), \\
q & \divides (m - m^{ed}).
\end{align*}
Thus, both $p$ and $q$ appear in the prime factorization of $m -
m^{ed}$.  Therefore, $pq \divides (m - m^{ed})$, and so:
\[
m  \equiv  m^{ed} \pmod{pq}.
\]
}

\eparts

\begin{center}
\fbox{
\begin{minipage}[t]{6in}
\begin{center}
\textbf{RSA Public Key Encryption}
\end{center}

\begin{description}

\item[Beforehand] The receiver creates a public key and a secret key
as follows.

\begin{enumerate}

\item Generate two distinct primes, $p$ and $q$.

\item Let $n = pq$.

\item Select an integer $e$ such that $\gcd(e, (p-1)(q-1)) = 1$.\\ The
{\em public key} is the pair $(e, n)$.  This should be distributed
widely.

\item Compute $d$ such that $de \equiv 1 \pmod{(p-1)(q-1)}$.\\ The
{\em secret key} is the pair $(d, n)$.  This should be kept hidden!

\end{enumerate}

\item[Encoding] The sender encrypts message $m$ to produce $m^\prime$ using
the public key:
\[
m' = m^e \rem n.
\]

\item[Decoding] The receiver decrypts message $m'$ back to message $m$
using the secret key:
\[
m = (m')^d \rem n.
\]

\end{description}
\end{minipage}
}
\end{center}

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{problem}

TAs Paul and Zardosht have gotten in a \emph{huge} argument over which
Mathematician is better: Euler or Gauss.  Naturally, the only way to
settle the argument is with a game of chicken.  Because both are poor TAs,
the fastest vehicles they can afford are bikes that travel at a constant
20 miles an hour.

Because they're both a little scared at heart, they agree to start 120
miles apart to give ample psyche up time.  At the start of the game, Eric
is on a motorcycle that travels a constant 40 miles an hour.  He starts
next to Paul, drives the course until he meets Zardosht, immediately goes
back to Paul, then back to Zardosht, \etc, \etc  Basically Eric bounces
back and forth between Zardosht and Paul. Assume that turning around takes
0 time and that Eric is always traveling towards one of the players at
exactly 40 mph.
\iffalse

In this question you will be asked to solve for the total distance
that Eric travels before Paul breaks Zardosht.
\fi

\begin{problemparts}

\problempart Find an
infinite series describing the total distance that Eric travels and
determine this distance by evaluating the series.

\solution{
We begin by noticing that if the bikes are a distance $d$ from
each other when Eric leaves one player to meet up with the other
player, Eric arrives at the other player in time $d/60$ because
Eric rides towards the other bike at 40 mph, and the other bike
travels towards Eric at 20 mph, for a total of 60 mph of closing
speed.  Then Eric travels $2d/3$ miles on that journey. Thus, his
first journey is 80 miles long.

We now try to describe how far Eric travels on a given journey
between the two players.  Say that on the previous journey, Eric
traveled $d$ miles, by the previous observation that must mean
the two bikes were $3d/2$ apart when Eric set out.

The total time that Eric was traveling is: $d/40$.  In that time, the two
bikes both traveled at 20 mph towards each other for that much time, and
the distance between bikes closes by $40 \cdot x/40 = x$. Thus, the two bikes
are now $3x/2-x=x/2$ miles apart.  Eric meets the other bike in $(x/2)/60$
hours, and travels $(x/2)/60 \cdot 40=x/3$ miles.

So, on every journey Eric travels a third as far as on his previous
journey.  This yields the infinite geometric series:
\begin{equation}\label{s}
80  \sum_{i=0}^\infty \paren{\frac{1}{3}}^i.
\end{equation}
Using the formula for the sum of a geometric series, we conclude that~\eqref{s}
equals $80(3/2) = 120$ miles.
}

\problempart Solve for the total distance that Eric travels \emph{without}
using an infinite series.

\solution{

We know that the Zardosht will bounce off of Paul after exactly 3 hours
from the start of the race.  During that time Eric is always traveling
at 40 mph, and therefore must travel a total of 120 miles before they
colide.

There's a famous story about John von Neumann, a physicist and
mathematician:

Another mathematician knew the quick solution to a similar problem, and
wanted to see von Neumann struggle with it. He posed the question, and von
Neumann responded with the right answer in a few seconds.

"Interesting," said the first mathematician. "Most people try to sum the
infinite series."

"What do you mean?" von Neumann replied. "That's how I did it."

Taken from:
\texttt{http://www.geocities.com/cscience\_sky/trainsandflie.htm}
}
\end{problemparts}
\end{problem}


\begin{problem}
Suppose you deposit \$100 into your MIT Credit Union account
today, \$99 in one month from now, \$98 in two months from now, and so on.
Given that the interest rate is constantly 0.3\% per month, how long will
it take to save \$5,000?

\solution{
First note that you will certainly manage to have saved \$5,000
\emph{some} day, since, even without your earnings from the interest,
you will have $100+99+\cdots+1=100\times 101/2 = 5,050$ dollars after
99~months. 

But fewer months will be needed: After the first deposit you will have
\$100. After the second deposit, you will have \$$(100\times 1.003 +
99)$. After your third deposit, your saved money will be \$$\bigl(
(100\times 1.003 + 99)\times 1.003 + 98) =$ \$$\bigl( 100\times
(1.003)^2 + 99\times 1.003 + 98\bigr)$, and so on. So, after the $n$th 
deposit,  
$$
S_n = \sum_{i=0}^{n-1} (100 - i) (1.003)^{n-i-1}
$$
dollars will be in your account. Substituting $j=n-i-1$, we can
rewrite this as  
$$
\sum_{j=0}^{n-1} \bigl( 100 - (n-j-1)\bigr) (1.003)^{j};
$$
and then as 
$$
(101-n) 
\Bigl( \sum_{j=0}^{n-1} (1.003)^{j}   \Bigr)+
\Bigl( \sum_{j=0}^{n-1} j (1.003)^{j} \Bigr).
$$
Using the closed forms from Course Notes~6, we can finally write $S_n$
as 
\[
(101-n)
\Bigl( \frac{1-1.003^n}{1-1.003} \Bigr)+
\Bigl( \frac{1.003-n1.003^n+(n-1)1.003^{n+1}}{(1-1.003)^2} \Bigr).
\]
Solving 
$$
S_n \geq 5,000
$$ 
for $n$, we get $n\geq 67$. That is, you'll need more than 5.5~years
to save~\$5,000.
}
\end{problem}



\begin{problem}
Books Books and more Books! If the 6.042 staff is to stand a chance
at the Book Extension Stacking Challenge, we have to consider all
the angles!

Recall the basic book stacking challenge from the course notes where
you have an unlimited supply of books to stack that are all the same
weight.
\begin{problemparts}

\problempart

What if instead of all books weighing the same, you have a book that
weighs 1 pound, a book that weighs $\frac{1}{2}$ pounds, a book that
weighs $\frac{1}{4}$ pounds, where each successive book weighs half as
much as the previous book. Say you had $n$ such books, and also that the
you have a duplicate of the lightest book. How far out can you stack the
books? Note that all books are still the same size, just different
weights.  \hint Where should the heaviest books be?

\solution{
The lightest books will be on top. Notice that every time you
add a heavier book to the bottom, it's weight will equal the weight of all
the books already in the stack. Thus, you can model this problem as
stacking two books of equal weight.

Every time you add a heavier book to the bottom, you can extend the 
stack out by the same constant amount. The top of the stack will have
its center of gravity at the edge of the new bottom book, and the
whole stack will have its center of gravity at the edge of the
table. Thus, the bottom book will stick out 1/4 of its length past
the edge of the table. Every book you add will add 1/4 of a book
length to the extension of the stack!
}

\problempart
What if you had to stack such that the lightest books were on the
bottom of the stack and the heaviest books were on top of the stack.
How far out can you stack an infinite number of books where each
book is twice as heavy as the book below it (we're looking for
either infinitely far or finitely far)? Justify your answer.

\solution{

Books can only be stacked finitely far. Start with the original book of
weight 1.  Note that this book weighs as much as the rest of the books
combined.  For contradiction, assume that its center of gravity could be
more than a half a book length past the edge of the table. We know that
the center of gravity of the whole system must be before the edge of the
table, so we know that at least as much weight must be strictly half a
book length behind the edge of the table (since the total weight available
is only equal to the weight of the first book).  However, that would
require that all the other books are fully on the table without overhang,
and the top book can't possibly be on top of another book.  }

\problempart

What if the books were Harmonically weighted: 1, $\frac{1}{2}$,
$\frac{1}{3}$, \etc, \etc, and the heaviest book had to be on top.  Would
it be possible for the top of the stack to be arbitrarily far past the
edge of the table?

\solution{Yes.

We know that if all books weighed the same that it would be possible to
stack infinitely far past the end of the table. We also know that we can
stack books on top of eachother until they way an arbitrary amount because
the Harmonic Series diverges. Therefore, we can stack enough books
together such that each stack weighs at least twice as much as the
previous stack. Treating each stack like a book, part a of this problem
illustrates how you can stack arbitrarily far out from the edge of the
table.  }

\end{problemparts}

\end{problem}

\iffalse


\begin{problem} 
Determine the flaw in the following reasoning and explain your answer.

\[
\left( \sum_{j=1}^n a_j \right) \left( \sum_{k=1}^n 1/a_k \right) =
\sum_{j=1}^n \sum_{k=1}^n a_j/a_k =
\sum_{k=1}^n \sum_{k=1}^n a_k/a_k =
\sum_{k=1}^n \sum_{k=1}^n 1 =
\sum_{k=1}^n n = n^2
\]

\solution{ Here the problem is taking the second step. It is incorrect to
change the variable of the first summation to k since the second summation
uses that variable. By doing this change of variables, we change the
meaning of the double summation.  }

\end{problem}

\fi

\begin{problem}
Use the Integral Method to find a $\Theta$ bound for $\sum_{k=1}^n k^6$.

\solution{
\begin{eqnarray*}
\int_0^n x^6 \ dx \leq \sum_{k=1}^n k^6 \leq \int_0^n (x+1)^6 \ dx \\
\frac{n^7}{7} \leq \sum_{k=1}^n k^6 \leq \frac{(n+1)^7}{7} - \frac{1}{7}
\end{eqnarray*}

From which we see that  $\sum_{k=1}^n k^6 = \Theta(n^)7$.

\begin{optional}
An alternative approach not using the Integral Method goes as follows: let
$\sum_{k=1}^n k^6 = S_n$.  There are $n$ terms in $S_n$ and each term is
at most $n^6$, so $S_n \leq n \cdot n^6 = n^7 = O(n^7)$. So $S_n=O(n^7)$.

On the other hand, at least $(n-1)/2$ of the terms are as large as $[(n-1)/2]^6$, 
so 
\begin{eqnarray*}
S_n &\geq & ((n-1)/2) \cdot [(n-1)/2]^6\\
    & = & [(n-1)/2]^7 \\
    & \geq & (n/3)^7
\end{eqnarray*}
for $n>3$, so $n^7 \leq 3^7 \cdot S_n$.  In other words, $n^7 = O(S_n)$.
Since we've shown $S_n=O(n^7)$ and $n^7 = O(S_n)$, we know that $S_n =
\Theta(n^7)$.

\end{optional}
}

\end{problem}


\begin{problem}
% problem 4, problem set 5, fall 1997

\bparts

\ppart Given that $f(x) = O(g(x))$, prove that $f(x)^2 = O(g(x)^2)$

\solution{Since $f(x) = O(g(x))$,
\[
\exists x_0,c\; \forall x \geq x_0, \abs{f(x)} \leq c\abs{g(x)}.
\]
So, $\forall x \geq x_0\, [f(x)^2 \leq c^2g(x)^2]$.  Therefore, there
exist $x_0' \eqdef x_0$ and $c' \eqdef c^2$ such that $\forall x \geq
x_0'\, [f(x)^2 \leq c'g(x)^2]$.  So $f(x)^2 = O(g(x)^2)$.}

\ppart Let $f(x) \eqdef 2x$ and $g(x) \eqdef x$, so $f(x) = O(g(x))$.
Prove that  $2^{g(x)} = o(2^{f(x)})$, so $2^{f(x)} \neq O(2^{g(x)})$.

\solution{Now $2^{f(x)} = 2^{2x} = 4^x$, and $2^{g(x)} = 2^x$.  So
$2^{g(x)}/2^{f(x)} = 2^x/4^x = 2^{-x}$, so the ratio goes to zero as $x$
goes to infinity, proving that $2^{g(x)} = o(2^{f(x)})$.  But $h_1=o(h_2)$
implies $h_2 \neq O(h_1)$ for any functions $h_1,h_2$, so $2^{f(x)} \neq
O(2^{g(x)})$.}

\ppart Prove that the relation, $R$, on functions such that $fRg$ iff $f = o(g)$
is a strict partial order.
\solution{
We must show that the relation $R$ is irreflexive, transitive, and 
anti-symmetric. 

$fRg$ is irreflexive. Assume there exists an $f$ such that $fRf$. This
would imply that $f = o(f)$, which implies that 
$$\lim_{x \rightarrow \infty} f(x)/f(x) = 0$$

However, since we know that $f(x)=f(x)$ for all $x$, this is clearly
a contridiction and $fRg$ is irreflexive.

$fRg$ is transitive. Assume we know $fRg$ and $gRh$. This implies
that $\lim_{x \rightarrow \infty} f(x)/g(x)=0$ and 
$\lim_{x \rightarrow \infty} g(x)/h(x) = 0$. So, we know that:
\begin{align*}
0 &= 0 \cdot 0\\
 &= [\lim_{x\to \infty} f(x)/g(x)] \cdot [\lim_{x\to \infty} g(x)/h(x)]\\
 &= \lim_{x\to \infty} [f(x)/g(x)] \cdot [g(x)/h(x)]\\
 &= \lim_{x\to \infty} f(x)/h(x),
\end{align*}
Thus, we have $fRh$.

$fRg$ is anti-symmetric. Assume $fRg$. Then we know 
$\lim_{x \rightarrow \infty} f(x)/g(x)=0$. For contradiction,
assume that $gRf$ is also true. This implies that: 
$\lim_{x \rightarrow \infty} g(x)/f(x)=0$. This clearly contradicts
the original statement because $g(x)/f(x) = 1/(g(x)/f(x))$ which 
approaches $\infty$ as $x$ approaches $\infty$.

Thus, the relation $R$ is a strict partial order.

}


\eparts
\end{problem}

\iffalse


\begin{problem}
Prove that $f \sim g$ iff $f = g + h$ for some function $h = o(f)$.
\end{problem}
\fi

\iffalse

\begin{problem}
  You don't need to give proofs for this problem.

  \begin{problemparts}
    \problempart Find functions $f_1$, $f_2$, $g_1$, and $g_2$, such
    that
    \begin{align*}
      f_1(n) &= \Theta(f_2(n)),\\
      g_1(n) &= \Theta(g_2(n)),\\
      \neg [f_1(g_1(n)) &= \Theta(f_2(g_2(n)))].\\
    \end{align*}

    \solution{$f_1(n) = f_2(n) = 2^n$, $g_1(n) = n$, $g_2(n) = 2n$.}


    \problempart Find functions $f$ and $g$ such that
    \begin{gather*}
      f(n) = O(g(n)), \text{ but } \neg [g(n) = O(f(n))];\\
      f(g(n)) = \Theta(g(f(n))).
    \end{gather*}

    \solution{$f(n) = n^2$, $g(n) = n^3$.}


    \problempart Find functions $f$ and $g$ such that
    \begin{alignat*}{3}
      f(n) &= O(g(n)), &\text{ but } &&\neg [g(n) &= O(f(n))];\\
      f(g(n)) &= O(g(f(n))),  &\text{ but } &&\neg [g(f(n)) &=
      O(f(g(n)))].\\
    \end{alignat*}

    \solution{$f(n) = n^2$, $g(n) = 2^n$.}


    \problempart Find functions $f$ and $g$ such that
    \begin{alignat*}{3}
      f(n) &= O(g(n)), &\text{ but } &&\neg [g(n) &= O(f(n))];\\
      g(f(n)) &= O(f(g(n))), &\text{ but } &&\neg [f(g(n)) &= O(g(f(n)))].\\
    \end{alignat*}

    \solution{$f(n) = 2^n$, $g(n) = 2^{2 n}$. Then $f(g(n)) = 2^{2^{2
          n}}$, while $g(f(n)) = 2^{2^{n+1}}$.}
  \end{problemparts}

\end{problem}
\fi


\end{document}


