% Math 320 hw1 solution
%
\documentclass{article}
\pagestyle{empty}
\usepackage[textheight=10in]{geometry}

\usepackage{amsmath}
\usepackage{hyperref}
\usepackage{graphicx}
\usepackage{verbatim}

\newcommand{\coursehome}
{http://www.cs.umb.edu/~eb/320}

\title{Discrete Mathematics \\
Homework 1 Solutions
}
\author{Ethan Bolker \\ Matt Lehman}

\begin{document}

\maketitle

\section*{Exercises}

\emph{When you study these answers, look at the \TeX{}
  too. There are some nice idioms here to learn.}

\begin{enumerate}

\item How do the writing hints above apply particularly to
  you? (The point of this question is to force you to \emph{read}
  those hints, rather than just skip them and start on the
  mathematics.)

No common answer here. I may paste in some student responses.

\item Two interesting alphabets.

\begin{enumerate}

\item How many $10$ letter words can be written with a $2$ letter
  alphabet?

We derived a formula for this problem, so all you need to do is apply
it: 

With a $2$ letter alphabet you can write  $2^{10} = 1024$ words
$10$ letters long. 

\emph{Note that this answer is a complete English sentence, not just a
  number.}

You can also easily think through the answer from first
principles. The alphabet might be $\{A,B\}$ or $\{0,1\}$ or any other
two element set. The key idea is that there are $2$ choices for each of
the $10$ letters in the word, for a total of $2^{10} = 1024$. You do
need to remember our convention that ``words'' may have repeated
``letters''.

\item How many $3$ letter words can be written with a $10$ letter alphabet?

With a $10$ letter alphabet you can write 
 $10^{3} = 1000$ words $3$ letters long.

\end{enumerate}

\item A number written in base $2$ has about $3$ times as many binary
  digits (bits) as the number of (decimal) digits in its base $10$
  representation. 

\begin{enumerate}

\item Check this for a few interesting numbers.

\begin{itemize}

\item Here are three small examples.

The base $2$ representation of $63$ is $111111$ (6 digits), $3$ times
as many binary digits.

The base $2$ representation of $64$ is $1000000$ (7 digits), $3.5$
times as many binary digits.

The base $2$ representation of $127$ is $1111111$ (7 digits), about
$2.33$ times as many binary digits.


\item $1024_{10} = 10000000000_{2}$.
\footnote{
Subscripts are a standard convention indicate the base. The subscripts
are base $10$.
}
That's a four digit number in
base $10$ that takes $11$ digits in base $2$. If you think a little
bit more about this example you'll note that $1024_{10}$ is just a
little bit larger than the last three digit number, $999_{10}$, while 
$2^{10}$ is just $1$ more than the last binary nine digit number. So
``three times as many digits'' is a very good approximation here.

\end{itemize}

\item Explain why this follows from the answer to the  previous
  question. 

We saw there that $2^{10}$ is relatively close to $10^{3}$ -- the
error is just $0.24\%$. (``Kilo'' in the metric system is 1,000 while
``kilo'' in computer science is 1,024, and the difference hardly ever
matters.)

A big number in base $10$ is usually written this way
%
\begin{verbatim}
               XXX,XXX,XXX,..., XXX,XXX
\end{verbatim} .
%
Each three digit piece is an integer between $000$ and $999$, so can
be thought of as a number in base $1000$. Each of those three digit
peices will take about $10$ digits in base $2$, so if
we're just looking for a rough approximation to convert from base $10$ to base
$2$, we multiply the number of digits by $10/3 \approx 3$.  Going
in the other direction, we multiply the number of digits by 
$3/10 \approx 1/3$. 

\item Explain why this follows from the value of $\log_2(10)$ or
  $\log_{10}(2)$. (What is the relation between those two numbers?)

$\log_{10}(2) \approx 0.30103$. (That's a nice
  palindrome, easy to 
  remember.)
$\log_{2}(10) \approx 3.32 \approx 3\frac{1}{3}$, also easy to remember.

Each of those numbers is the reciprocal of the other -- a fact you
should know (from now on). How would you prove it?

In this problem what's important is the fact that
%
\begin{quotation}
The number of base $b$ digits of $n$ is (approximately) $\log_b(n)$.
\end{quotation}
%
Then
%
\begin{equation*}
\log_{2}(n) = \log_{2}(10) \times \log_{10}(n) \approx 3.32 \log_{10}(n)
\end{equation*}
%
finishes the explanation.
\end{enumerate}

\item Why is the number of $2n$ letter words on a $k$ letter alphabet
  the square of the number of $n$ letter words? You should be able to
  answer this two ways, one using a known formula, the other which works
  even if you have \emph{no idea} what the formula is for $n$ letter words.

First answer, using the formula. 
% this commented line prevents the start of a new paragraph
\begin{align*}
\text{number of } 2n \text{ letter words}& = k^{2n} \\
& = (k^n)^2 \\
& = (\text{number of } n \text{ letter words})^2 .
\end{align*}

Second answer.  If you don't know the formula for the number of $n$
letter words on a $k$ letter alphabet (or know it but don't want to
use it), then let that number, whatever it is, be $W$.  A $2n$ letter
word is one $n$ letter word followed by another $n$ letter word, so
the answer would be $W \times W = W^{2}$.

\item Consider the word \verb!APFELS!. 
\footnote{That's ``apples'' in German.}

\begin{itemize}
\item How many ways are there to rearrange these $6$ letters?

Each of the $6$ letters is different, so this is the same as the
number of $6$ letter words on a $6$ letter alphabet without
repetitions, or the number of permutations of $6$ things,
so the answer is $6!= 720.$ 

\item How many ways are there to rearrange these $6$ letters so that
  a \verb!P! comes before an \verb!E!?

Here are three ways to answer this question. I'll save the cleverest
for last.

\begin{itemize}

\item There are $6 \times 5 / 2 = 15$ ways to choose the two places
  for the \verb!P! and the \verb!E!. For each of those choices there
  are $4! = 24$ ways to arrange the other four letters. That means
  there are $15 \times 24 = 360$ ways to arrange all $6$ as required.

\item If the \verb!P! is first there are $5$ places to put the
  \verb!E!. 

If the \verb!P! is second (third, fourth, fifth)  there
  are $4$ ($3$, $2$, $1$) places for the \verb!E!.

In each case there are  and $4! = 24$ ways to fill in the other four
letters, for a total of $(5 + 4 + 3 + 2 + 1) \times 24 = 360$ words.

\item There are $6! = 720$ words altogether. In just half of them the
  \verb!P! precedes the \verb!E!. That's $360$ words.
\end{itemize}
\end{itemize}

\item Answer the questions in the last Exercise for the word
  \verb!APPLES!. 

There are $6!/2 = 360$ permutations of the letters. 
There are three equally likely patterns for the two \verb!P!'s and the
\verb!E!, independent of how the other letters are arranged:
\verb!P.P.E!, 
\verb!P.E.P! and
\verb!E.P.P!. 
A \verb!P! precedes an \verb!E! in two of them.
That means $2/3$ of the $360$, so $240$ words meet the requirements.


\item How many permutations are there of the numbers $\{0, 1, \ldots,
  99\}$? In how many of these do the numbers $\{1, 11, 21, \ldots,
  91\}$ appear in order? Use Stirling's formula to estimate each of
  these counts.

% this is just C(100,10), derived a new way ...

We're counting the number of ways of permuting $100$ distinct
objects. There are $100!$, a very large number! 

In each of those, let's look at how the subset of $\{1, 11, 21,
\ldots,91\}$ might be  arranged.  There are $10$
elements in that subset, so there are $10!$ ways of permuting those
elements \emph{with respect to each other}, only one of which gives us
the desired result.  Recall the second part of problem \#5.  We have
to divide by the number of (equally likely)
 ways that the subset of $10$ elements can be
permuted, so the answer is $100!/10!$. 

For $n=100$ Stirling's formula tells us
%
\begin{equation*}
100! \approx \sqrt{2\pi (100)}\left(\frac{100}{e}\right)^{100} \approx
9.325*10^{157} .
\end{equation*}
%
Plugging $100!$ directly into a calculator yields
\begin{equation*}
100! \approx 9.333*10^{157}
\end{equation*}
 so Stirling's is a pretty good approximation. 

$10!$ isn't that large, so we don't need Stirling's formula to find
 it:
%
\begin{equation*}
10! = 3,628,800 = 3.628*10^{6}
\end{equation*}
%
so
\begin{equation*}
  \frac{100!}{10!} \approx \frac{9.333*10^{157}}{3.628*10^{6}} \approx
  2.572*10^{151} .
\end{equation*}

\item Counting valid phone numbers.

\begin{enumerate}

\item In the 1960s a valid (North American) ten digit telephone
  number had the form \verb!NYX NNX XXXX! where

\begin{itemize}
\item \verb!X! is one of the digits $0, 1, \ldots 9$,
\item \verb!N! is one of the digits $2, 3, \ldots 9$,
\item \verb!Y! is one of the digits $0, 1$.
\end{itemize}

How many valid telephone numbers were there then?

There were 
%
\begin{align*}
(8)(2)(10)(8)(8)(10)(10)(10)(10)(10) & = (2)(8^{3})(10^{6}) \\
& = (2^{10})(10^{6}) \\
& =  1,024,000,000
\end{align*}
%
 telephone numbers, or a little over $1$ billion. I hope you didn't
 need a calculater to do that arithmetic.

\item Now the form is \verb!NXX NXX XXXX!.
How many valid numbers are there now? 

By direct count there are $(8^{2})(10^{8})= 6,400,000,000$, or $6.4$
billion.

\item If you answered the previous question by a direct count, answer
  it again by thinking about how much larger it should be than the
  answer to the first question. If you did it that way first, answer
  it again with a direct count.

If we compare the two strings: \verb!NYX NNX XXXX! with
\verb!NXX NXX XXXX!, we only care about the places where the letter
type has changed. In the second place the change from \verb!Y! to
\verb!X! increases the count by a factor of $10/2$. In the fifth place
the change  from \verb!N! to \verb!X! increases the count by a factor
of $10/8$. The overall increase is by a factor of
$(10/8) \times (10/2) = 100/16 = 6.25$. 
\footnote{Note that since $\frac{100}{16}=6.25$, $\frac{1}{16} =0.0625
  = 6.25\%$ which is the current Massachusetts sales tax.  If you buy
  something for $\$16$ (more likely $\$15.95$ or $\$15.99$), the sales
  tax will be exactly $\$1$.  Massachusetts sales tax used to be
  $5\%$, which was much easier to calculate in your head.} 

\item Were there enough numbers then? Are there enough numbers? Will
  there   always be enough numbers? Write a paragraph or two about
  these questions. Use a round estimate for the population of North
  America. 

In the $1960$s, there were about 300 million people living in North
America.  If each household had a phone and there were an average of
$4$ people living in each household, only about $75$ million numbers
were needed for households.  We also have to take into account
businesses and pay phones, so if we want to be generous, we can
probably round that figure to $200$ million, so there were more than
enough phone numbers. 

Today, the population of North America is a little over $500$
million. If every person has $2$ phone numbers (cell phone and
landline), this gives us a billion numbers.  If we're generous and
give everyone an average of $3$ phone numbers, that's still only
$1.5$ billion, just $25\%$ of the total available.  It seems unlikely
that the population of North America will exceed a billion, and it
also seems unlikely that everyone would need an average of more than
$4$ phone numbers, so it seems that this should be sufficient. 

\end{enumerate}

\end{enumerate}

\newpage

Here is the \LaTeX{} source for this document. You can cut it from the
pdf and use it to start your answers. I used the \verb!\jobname! macro
for the source file name, so you can call your file by any name you like.

\verbatiminput{\jobname}

\end{document}
