% 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
}
\author{Ethan Bolker}
\date{September 1, 2014}

\begin{document}

\maketitle

\noindent
The Preliminaries on this page are due Thursday, September 4.

\noindent
The Exercises on the following pages are due Thursday, September 11.

\section*{Preliminaries}


\begin{itemize}

\item Send me email (to \verb!eb at cs dot umb dot edu!) from the
  email   address you want me to use for the class mailing list. 

\item Complete the questionnaire at
\url{\coursehome/questionnaire.pdf} by editing and compiling the
\LaTeX{} source at \url{\coursehome/questionnaire.tex}. Turn in hard
copy of the pdf that includes \LaTeX{} source -- as does the questionnaire.

Answering the questions is easy. I'm asking more than that. To
answer them in the form I require you'll have to begin to learn \TeX{}
-- in particular, \LaTeX. That typesetting system is the best in the
world for mathematics (and lots of other documents too) and well worth
the (sometimes substantial) effort it may take you to learn it. If you
go on in mathematics or computer science it may well be the most
valuable thing you learn in this course.

To use \TeX{} you need two kinds of software on your computer. The
first is a \TeX{} \emph{distribution}. You can find links to download
one at \url{\coursehome/tex}, where I have listed some \TeX{} resources.

The second is an editor. You can write \TeX{} with any word
processor. I use \verb!emacs!. Even Microsoft Word or Notepad would
do. But I recommend something like TexStudio
(\url{http://texstudio.sourceforge.net/}),
which is a complete
environment for writing, compiling and previewing \TeX{} documents.
You can find more information at \url{\coursehome/tex}.

Once you get started you'll find it fun (I hope). You can ask me
\TeX{} questions, or ask them at
\url{http://tex.stackexchange.com}.

\end{itemize}

\newpage

\section*{Exercises}

Your written mathematics must be

\begin{itemize}
\item logically clear -- of course. Remember that
the point of your argument is not to convince me (I already know) or
even to convince yourself (it may be obvious to you) but to convince
\emph{me} that you have convinced \emph{yourself} for good reasons. 

\item
free of spelling and grammatical errors.

There are lots of good thinkers who are poor spellers. If you are one,
get a good friend who spells well to proofread your work before you
turn it in.

I will make some allowance for non native speakers of English 
(you clearly do better in my language than I could in yours!), but I
expect your English to improve as the semester progresses. 

\item 
honest. If you are confused at some point, say as clearly as you can
what you are confused about. Don't guess -- a lucky correct guess without a
good reason may convince you that you understand the problem when you
don't really. An honest description of what puzzles you will teach
you more, and let me teach you more.

\item uncluttered. The hard copy pdf you turn in should include the
  statements of   the questions you're answering (so you can read it
  without referring back to the assignment)  but not the
  instructions like these. 
\end{itemize}

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

\item Two interesting alphabets.

\begin{enumerate}

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

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

\end{enumerate}

\emph{Note that in the \LaTeX{} source the numbers $2$, $3$ and $10$
  are written in math mode, surrounded by \$ \ldots \$. That ensures
  typographic correctness when fonts change. In particular, they're
  not in italics here, as 2, 3 and 10 would be.
}

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

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

\item Explain why this follows from the value of $\log_2(10)$ or
  $\log_{10}(2)$. (What is the relation between those two numbers?)
\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.

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

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

\end{itemize}

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

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

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

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


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

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

\end{enumerate}

\item Watch this space -- more to come. 

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