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

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

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

\newenvironment{sol}
{\textbf{Solution}\par}
{}

\title{Discrete Mathematics \\
Exam 1 Solutions
}
\author{Ethan Bolker}
\date{October 16, 2014}

\begin{document}

\maketitle

The first question was worth 16 points. Each part of each succeeding
question was worth 12 points, for a total of 100. (I didn't count the
last optional hard question.)

I tried to be reasonably generous with part credit.

Here's the grade distribution, with approximate letter grade
equivalents (you can't take those literally).

\begin{center}
\begin{tabular}{r|cccccccc}
range & 90-99 & 80-89 & 70-79 & 60-69 & 50-59 & 40-49 & 30-39 & 20-29 \\
number & 1 & 1 & 3 & 5 & 3 & 8 & 4 & 5 \\
grade? & A & A & A- & B & C+ & C & C-/D & D/F
\end{tabular}
\end{center}
\begin{enumerate}

\item Consider the word \verb!MISSISSIPPI!. (It's a favorite for this
  kind of problem.) How many ways are there to permute the letters if
  all four  \verb!I!s or all four \verb!S!s are together?
  (\verb!IIII!, \verb!SSSS!) .

I should not have to remind you that in mathematics and in computer
science, ``or'' means ``and/or''. 

\begin{sol}
If I treat  \verb!IIII! as a single letter there are $8!/4!2!$
permutations. The factorials in the denominator take into account the
fact that there are four \verb!S!s and two \verb!P!s.

There are the same number of permutations containing \verb!SSSS!. 

I can add those two answers to find the number of permutations
containing one or the other -- as long as I correct because I've
double counted the permutations that contain both (inclusion-exclusion
principle). There are $5!/2!$ of those, so my answer is
%
\begin{equation*}
2 \times \frac{8!}{4!2!} - \frac{5!}{2!} = 1680 - 60 = 1620 .
\end{equation*}

That's an interesting historical number: it's the year the pilgrims
landed in Plymouth on the Mayflower.

I gave partial credit for knowing how to calculate the number of
permutations when some letters are repeated. I was surprised at how
many students didn't see the need to worry about double counting the
strings in which both blocks appeared. I'd hoped my hint would point
you in that direction.
\end{sol}

\item $18$ people have gathered for dinner. Tables at the restaurant
  seat $6$.

\begin{enumerate}
\item How many ways are there to divide the $18$ people into three
  groups of $6$?

\begin{sol}
I can choose the first group of $6$ in $18!/6!12!$ ways, then the second
group in $12!/6!6!$ ways. The last $6$ people make the last
group. Multiplying these independent choices gives me
$18!/6!6!6!$ ways to choose the groups \emph{in order}.

Now in the problem statement the tables aren't mentioned. They are
clearly indistinguishable. There is no way to assign a particular
group to a particular table. That means choosing
the same three groups in any other order would lead to the same
division, so I need to divide by $3!$. The answer is
\begin{equation*}
\frac{18!}{6!6!6!3!} = 21,237,216
\end{equation*}
(if I did the arithmetic right). On the exam you didn't have a
calculator, so I didn't expect you to do the arithmetic at all.

I was a little concerned about whether I really needed to do that last
division by $3!$ so I checked my answer by thinking about how I would
divide three people into three groups of one person each. Clearly
there's only one way! 

Very few students divided by that last $3!$. I gave partial credit for
the answer $\dbinom{18}{6,6,6}$.

This is similar to the poker hands homework problem, easier since
we're ``dealing out the whole deck'' but harder since the order in
which the groups occur doesn't matter.
\end{sol}

\item If half the $18$ people are women and half men, how many ways
  are there to divide them so that each table has the same number of
  women and men?

\begin{sol}
Using the same logic, I can divide up the women and men each in
$9!/3!3!3!3!$ ways. I need to multiply those together and then multiply
by $3!$ to take into account the different ways to pair triples of
women with triples of men. The answer is
%
\begin{equation*}
\frac{9!}{3!3!3!3!}
\times
\frac{9!}{3!3!3!3!}
\times
3!
 = 235,200 \text{ ways.}
\end{equation*}
%
That's just about one percent of the previous answer.

Here's another way that comes to the same conclusion. After you choose
the three groups of men in $9!/(3!)^4$ ways you choose the groups of
women in $9!/(3!)^3$. You \emph{don't} divide by the extra $3!$ since
it matters which groups of women join which groups of men.
\end{sol}

\item How many ways are there to seat six people at a round table if
  all that matters is who each person's neighbors are?

\begin{sol}
If the six people were in a line there would be $6!$
permutations. Arranging that line in a circle I can no longer tell
where the line started, so there are only $5!$ circular
arrangements. But each of those arrangements can go around the table
either clockwise or counterclockwise without changing who sits next
to whom, so I have to divide by two. The answer is $5!/2 = 60$ ways.
\end{sol}

\end{enumerate}

\item Imagine a test with $20$ questions where each question has two
  possible answers. They are not true/false questions -- one or both or
  neither answer might be correct. Here is an example:

\begin{framed}
Is discrete mathematics fun
\begin{itemize}
\item for mathematics students?
\item for computer science students?
\end{itemize}
\end{framed}

\begin{enumerate}
\item Count the number of possible ways to answer all the questions on
  that test.

\begin{sol}
Each question has four possible answers so there are 
$4^{20}$ possible tests.

Many students thought there were just three possible answers. If you
read the sample question in the box carefully you can see four:
\begin{itemize}
\item Everyone finds discrete math fun.
\item Noone finds discrete math fun.
\item Only math students like it.
\item Only cs students like it.
\end{itemize}

\end{sol}
\item Which of the following is a good estimate of your count?
\begin{equation*}
10^{6} \quad
10^{9} \quad
10^{12} \quad
10^{15} \quad
10^{18} \quad
\text{none of these}
\end{equation*}

\begin{sol}
\begin{equation*}
4^{20} = 2^{40} = (2^{10})^4 \approx (10^{3})^4 = 10^{12}.
\end{equation*}
\end{sol}
\end{enumerate}

Some of you did this with $\log_{10}(2) \approx 0.30103$, which is
correct but overkill.

If you found $3^{20}$ as the (incorrect) answer to the previous
question you could still get full credit here for $10^9$.

If you got a ridiculously small or large wrong answer to the previous
question you could earn free points here for ``none of these''.

\item A parking lot has $n$ spaces in a row. Cars arrive and fill
  spaces at random. Then Auntie Em drives up in her SUV, which needs
  two adjacent spaces. 

\begin{enumerate}

\item If exactly two spaces are free, what is the probability that she
  is able to park? 

\begin{sol}
I need to compute
%
\begin{equation*}
\frac{\text{number of configurations with adjacent empty spaces}}
{\text{number of ways to pick two empty spaces}}.
\end{equation*}

To find the numerator, treat the two empty spaces as one item among
$n-1$. There are $n-1$ places to put that pair. The denominator is
just $\dbinom{n}{2}$ so the answer is
%
\begin{equation*}
\frac{n-1}{\frac{n(n-1)}{2}} = \frac{2}{n}.
\end{equation*}
\end{sol}
\item Suppose $f$ spaces are free. (In the previous question $f=2$.)
  What is the minimum value of $f$ that guarantees that Auntie Em can
  park? (Explain how you know you've answered the question correctly.)

\begin{sol}
Think of the parking lot as a bit string, with $0$ for empty spaces. 

If Auntie Em can't park, then every $0$ must be followed by a $1$,
except possibly at the end. 

If we want as many $0$'s as possible, we don't want two $1$'s
together. That says that the bitstrings $0101 \cdots 01$ and
$101 \cdots 10$ (for $n$ even) and $0101 \cdots 010$ (for $n$ odd)
have the fewest $1$s that can prevent Auntie Em. Therefore $f = 1+n/2$
for $n$ even and $f = 1 + (n+1)/2$ for $n$ odd.

\end{sol}
\item (Optional, hard, take home). Answer the first question if there
  are $f$ empty spaces. (You've just done $f=2$, and found values of
  $f$  that make the probability $1$.) Check that your answer agrees
  with your answer to the first question. Evaluate your expression
  when $n=16$ and $f=4$.

\begin{sol}

To answer this question I counted the configurations where she
couldn't park.  I considered two cases.

\begin{itemize}
\item If the bitstring doesn't end with a $0$ then every $0$ must be
  followed by a $1$. So think of building the string from $f$ copies
  of $(01)$ and the remaining $n-2f$ copies of $1$. That can be done
$\dbinom{n-f}{f}$ ways.

\item For the bitstrings ending with $0$ I need $f-1$ copies of $(01)$
  and $n-2f+1$ more copies of $1$. I can do that in
$\dbinom{n-f}{f-1}$ ways.
\end{itemize}

So Auntie Em can part with probability
%
\begin{equation*}
1 - \frac{\dbinom{n-f}{f} + \dbinom{n-f}{f-1}}{\dbinom{n}{2}}
=
1 - \frac{\dbinom{n-f+1}{f}}{\dbinom{n}{2}} .
\end{equation*}

Checking when $n=2$:

\begin{equation*}
1 - \frac{\dbinom{n-1}{2}}{\dbinom{n}{2}} 
=
1 - \frac{(n-1)(n-2)}{n(n-1)}
= 1 - \frac{n-2}{n} = \frac{2}{n}.
\end{equation*}

Sho Inaba counts the ways Em can't park much more elegantly.
First he observes that there must be at least one
filled space between each of the $f$ free spaces. That uses up $f-1$
filled spaces, so there are $n-2f+1$ more to insert somewhere. There
are $f+1$ possible places to put them -- before the first free space,
between two, or after the last one. Then he sees that this is just the
apples/bananas/cherries problem in disguise, so there are
%
\begin{equation*}
\dbinom{(n-2f+1)+f}{f} = \dbinom{n-f+1}{f} 
\end{equation*}
%
ways she can't park. That's all he needs to finish the problem, pretty
much the way I did from that point.
\end{sol}
\end{enumerate}




\end{enumerate}


\end{document}




