% 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}

%Why don't you use '\today'?

\begin{document}

\maketitle
\newpage

\section*{Exercises}

\begin{enumerate}

\item No written 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 $32$ is $100000$ (6 digits), $3$ times more digits.

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.

The base $2$ representation of $1023$ is $1111111111$ (10 digits), $2.5$ times more digits.

%I probably used too many examples.

\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{3}{10}$.  Going in the other direction, we multiply the exponent by a factor of $\frac{10}{3}$.

This is a good shortcut to quickly determine how many digits a large power of $2$ has, in base $10$.  For example, in base $10$, how many digits does $2^{100}$ have?  Recall that converting from base $2$ to $10$ means multiplying the exponent by $\frac{3}{10}.$   $(100)(\frac{3}{10})=30.$  Using a calculator, $2^{100}\approx 1.267* 10^{31},$ so we were only off by $1$.  Our approximation was less than the actual, because we were using $1000$ instead of $1024$.

%I thought this would be a good example to motivate the CS students to learn the trick.

\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 $10^{y}=(2^{x})^{y} = 2^{xy} = 2,$ so $xy=1.$

%If you think some students might be confused by the chain of equalities, I can provide a more detailed justification.

\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.$  Incidentally, since $(k^{n})^2=(k)^{2n}=(k^{2})^n,$ then this is also number of $n$ letter words on a $k^{2}$ letter alphabet.
  
%Feel free to drop the 'incidental' comment if you think it's confusing or irrelevant to the topic.
  
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, we'll demonstrate both 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 ...

% Actually, isn't this 90!*C(100,10), since we have to count the permutations of the other 90 numbers?

\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.$
\footnote{Note that since $\frac{100}{16}=6.25$, $\frac{1}{16} =.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.}

%I thought this was a 'fun fact', but if you think it's irrelevant, please delete it.

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. 
  
There is no right or wrong answer for this question, since the exact answer is unknowable.  I'm just looking for your ability make an estimation based on reasonable assumptions.
  
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 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}
