% Math 320 hw1
%
\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}
\date{September 11, 2014}

\begin{document}

\maketitle
\newpage

\section*{Exercises}


\begin{enumerate}

\item No answer necessary.

\item Two interesting alphabets.

\begin{enumerate}

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

You can think of the two letters as $\{A,B\}, \{0,1\}$, or $\{1,2\}$
if it helps you think about the problem, but the actual letters aren't
important.  The key concept is that there are $2$ choices for each of
the $10$ letters in the word, for a total of $2^{10} = 1024$.  

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

Similarly, there are $10$ choices for each of the $3$ letters, for a total of $10^{3} = 1000$.

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

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

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

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

The base $2$ representation of $128$ is $10000000$ (8 digits), about $2.66$ times more digits.

The base $2$ representation of $255$ is $11111111$ (8 digits), about $2.66$ times more digits.

The base $2$ representation of $256$ is $100000000$ (9 digits), $3$ times more digits.

The base $2$ representation of $511$ is $111111111$ (9 digits), $3$ times more digits.

The base $2$ representation of $512$ is $1000000000$ (10 digits), about $3.33$ times more digits.

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

We saw that $2^{10}$ is relatively close to $10^{3}$, so if we're just
looking for a rough approximation to convert from base $2$ to base
$10$, we multiply the exponent by a factor of $\frac{10}{3}$.  Going
in the other direction, we multiply the exponent by a factor of
$\frac{3}{10}$. 

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

Recall that if $x = \log_{b}(a)$, then x is the number that you raise the base (b) by, to get $a$, which is the same thing as $b^{x}=a$.  If $x=\log_{2}(10),$ then $2^{x} = 10$ and if $y=\log_{10}(2),$ then $10^{y}=2$.  Therefore $(2^{x})^{y} = 2^{xy} = 10^{y} = 2,$ so $xy=1.$

\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.
  
  Using the formula, the number of $n$ letter words on a $k $ letter alphabet is $k^{n}$, so the number of $2n$ letter words on a $k$ letter alphabet is $(k)^{2n} = (k^{n})^2.$  Since $(k^{n})^2=(k)^{2n}=(k^{2})^n,$ then this is also number of $n$ letter words on a $k^{2}$ letter alphabet.
  
  If you don't know the formula for the number of $n$ letter words on a $k$ letter alphabet, then let that number, whatever it is $= x.$  A $2n$ letter word is one $n$ letter word followed by another $n$ letter word, so the answer would be $(x)(x) = x^{2}.$

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

\begin{enumerate}
\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, 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!?

There are two basic approaches: hard or easy.

Hard way: First count the number of ways the $2$ letters can be placed in $6$ slots such that \verb!P! comes before \verb!E!.

\verb!P!\verb!E!xxxx \quad \verb!P!x\verb!E!xxx \quad
\verb!P!xx\verb!E!xx \quad
\verb!P!xxx\verb!E!x \quad
\verb!P!xxxx\verb!E! \quad

x\verb!P!\verb!E!xxx \quad
x\verb!P!x\verb!E!xx \quad
x\verb!P!xx\verb!E!x \quad
x\verb!P!xxx\verb!E! \quad

xx\verb!P!\verb!E!xx \quad
xx\verb!P!x\verb!E!x \quad
xx\verb!P!xx\verb!E! \quad

xxx\verb!P!\verb!E!x \quad
xxx\verb!P!x\verb!E! \quad

xxxx\verb!P!\verb!E!

This can be done in $15$ ways.  The remaining $4$ letters can be arranged in $4!=24$ ways, making for a total of $(15)(24) = 360$ ways.

Easy way: Of all the arrangements of the $6$ letters, since there are no restrictions, then exactly half will have a \verb!P! before an \verb!E!, so the answer is simply $\frac{6!}{2}= 360.$

\end{enumerate}

\item Answer the questions in the last Exercise for the word
  \verb!APPLES!. 
  
  As before, there is a hard and an easy way.
  
  Hard way: Count the number of ways $2$ \verb!P!s can be placed in
  $6$ slots.  This is slightly easier if you noticed that this is the
  same situation as with the previous problem, if you replace the
  \verb!E! with a second \verb!P!, so the answer is also
  $(15)(24)=360.$ 
  
  Easy way: First, pretend the $2$ \verb!P!s are distinct (call them $\verb!P!_{1}$ and $\verb!P!_{2}$ if you want), which gives us $6!$ arrangements.  Since we can swap the $2$ \verb!P!s without changing the result, we've over counted by a factor of the number of ways of arranging $2$ objects = $2!=2,$ so we have to divide by that factor, yielding the previous result of $\frac{6!}{2}=360$ ways.

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

We're counting the number of ways of permuting $100$ distinct objects,
so the answer $=100!$, a very large number! 

We haven't yet learned the formula for the number of ways of counting
the number of $k$ subsets of an $n$ element set, but if we're clever,
we can still find the answer.  
We know there are $100!$ ways of
arranging $100$ distinct elements.  Of those, let's look at how the
subset of $\{1, 11, 21, \ldots,    91\}$ is 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 factor out all the ways that the subset of $10$ elements can be
permuted, so the answer $=\frac{100!}{10!}$. 

Sterling's formula is an approximation for factorials, which states $n!\approx \sqrt{2\pi n}(\frac{n}{e})^{n}.$  

For the first result, letting $n=100,$ Sterling's formula yields
$\sqrt{2\pi (100)}(\frac{100}{e})^{100} \linebreak \approx
9.325*10^{157}.$  Plugging $100!$ directly into a calculator yields
$\approx 9.333*10^{157}$, so this is a pretty good approximation. 

$10!$ isn't that large a number, so calculating directly results in $3,628,800 = 3.628*10^{6}.$

$\dfrac{9.333*10^{157}}{3.628*10^{6}} \approx 2.572*10^{151}.$


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

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

\verb!N! has $10$ valid digits, \verb!N! has $8,$ and \verb!Y! has $2$.  

Therefore, there were $(8)(2)(10)(8)(8)(10)(10)(10)(10)(10)= (2)(8^{3})(10^{6})= (2^{10})(10^{6}) =  1,024,000,000$ telephone numbers, or a little over $1$ billion.

\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 how the frequency of the letter types have changed. \verb!X! increased by $2$, \verb!N! decreased by $1$, and \verb!Y! decreased by $1$.  Therefore, the change from the older to the newer system increased the number of telephone numbers by a factor of $\frac{10^{2}}{(8)(2)} = 6.25.$

In billions, this is $(1.024)(6.25) = 6.4,$ which agrees with our direct count result.

\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 a 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 a sufficient number of 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, this is 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}

\end{document}
