\documentclass[11pt, twoside]{article}
\input{macros-course}
\usepackage{graphicx}
\renewcommand{\implies}{\longrightarrow}
\newcommand{\ignore}[1]{}
\askaboutsolutions
\begin{document}
\pset{7}{April 3, 2001}{2:35pm in lecture, April 10, 2001}
\renewcommand{\labelenumi}{\bf (\alph{enumi})}
\renewcommand{\labelenumii}{\bf (\roman{enumi})}
\textbf{Be sure to indicate your TA's name clearly on the solutions
you turn in}.

\paragraph{Reading}
Rosen, \textit{Discrete Mathematics and Its Applications},
Sections 4.1, 4.3, 5.5, and 5.6.


\vspace{-.25in}

\paragraph{Policy on collaboration}
If you collaborated with someone on the problem sets, you should
mention their names on top of the problem set. If you did not
collaborate with anyone, you should explicitly say so. As a reminder,
the write-up of your solutions should be entirely your own.

\paragraph{Self-study}

The following exercises are \emph{optional;} do them if you think you
need the practice. The mini-quiz in tutorial on Friday will draw
(only) from these problems.

Exercises from Rosen (answers in the back of the book): 
Section 4.3: 1, 5, 13; Section 5.1: 1, 5, 11.


\medskip
\begin{problems} 
                     
\problem
\begin{enumerate}
\item There are 49 students in a class at MIT who either understand mathematical 
equations, exercise regularly, or love school. Of these:

\noindent
20 students understand mathematical equations.

\noindent
20 students exercise regularly.

\noindent
26 students love school.

\noindent
36 students understand mathematical equations or exercise regularly.

\noindent
38 students understand mathematical equations or love school.

\noindent
40 students exercise regularly or love school.

\vspace{1mm}

\noindent
How many students understand mathematical equations AND exercise
regularly AND love school?

\solution{
\medskip
\textbf{Solution:}
\medskip
  
Let $A$ denote the set of students who understand mathematical
equations, $B$ denote the set of students who exercise
regularly, and $C$ denote the set of students who love school.
Then we are given that $ | A\cup B\cup C | = 49$, 
$| A |=20$, $| B |=20$, $| C |=26$, 
$| A\cup B |=36$, $| A\cup C |=38$, and $| B\cup C |=40$.
\begin{eqnarray*}
| A\cap B\cap C | & = & 
      | A\cap B | +| C | - | (A\cap B)\cup C |\\
& = & | A | + | B | - | A\cup B | + | C | 
      - | (A\cup C) \cap (B\cup C) |\\
& = & | A | + | B | - | A\cup B | + | C | 
      - | (A\cup C) | - | (B\cup C) | + | (A\cup B \cup C) |\\
& = & 20 + 20 - 36 + 26 - 38 - 40 + 49\\
& = & 1
\end{eqnarray*}
In line 1 we apply inclusion-exclusion, in line 2 we apply inclusion-exclusion
and distributive laws, and in line 3 we apply inclusion-exclusion.
}    
\item Show that there are fewer than 
50,000 prime numbers less than or equal to 210,000. \hint they are actually far fewer than 50,000 (about 19,000)

\solution{\medskip
\textbf{Solution:}
\medskip
        
Since natural numbers are either composite or prime, we can instead
show that there are at least $210,000 - 50,000 = 160,000$ composite
numbers less than or equal to $210,000$.  

Let's count composite
numbers by counting the multiples of $2, 3, 5$, and $7$. Notice that in the calculation below, we need to subtract 1 each time because $2, 3, 5$, and $7$ should not be counted as composites since they are prime!

\[\begin{array}{llr}
\mbox{multiples of }2: &\lfloor 210,000/2 \rfloor -1 &= 105,000-1\\
\mbox{multiples of }3: &\lfloor 210,000/3 \rfloor -1&= 70,000-1\\
\mbox{multiples of }5: &\lfloor 210,000/5 \rfloor -1&= 42,000-1\\
\mbox{multiples of }7: &\lfloor 210,000/7 \rfloor -1&= 30,000-1\\
\hline
  &&+ 246,996
\end{array}\]

However, we have double counted the numbers which are multiples of two
of $\{2, 3, 5, 7\}$.  So, using inclusion/exclusion, we subtract these
back out\footnote{Notice that we do not subtract 1 from each result since 6, 10, 14 etc are composites} :

\[\begin{array}{llcr}
\mbox{multiples of }\{2,3\}: & \lfloor 210,000/6\rfloor   &= &  35,000\\
\mbox{multiples of }\{2,5\}: & \lfloor 210,000/10\rfloor  &= &  21,000\\
\mbox{multiples of }\{2,7\}: & \lfloor 210,000/14\rfloor  &= &  15,000\\
\mbox{multiples of }\{3,5\}: & \lfloor 210,000/15\rfloor  &= &  14,000\\
\mbox{multiples of }\{3,7\}: & \lfloor 210,000/21\rfloor  &= &  10,000\\
\mbox{multiples of }\{5,7\}: & \lfloor 210,000/35\rfloor  &= &   6,000\\
\hline
  &&& - 101,000
\end{array}\]

Now, we must add back in the numbers which are multiples of three of
$\set{2, 3, 5, 7}$:

\[\begin{array}{llcr}
\mbox{multiples of }\{2,3,5\}: & \lfloor 210,000/30\rfloor  &=& 7,000\\
\mbox{multiples of }\{2,3,7\}: & \lfloor 210,000/42\rfloor  &=& 5,000\\
\mbox{multiples of }\{2,5,7\}: & \lfloor 210,000/70\rfloor  &=& 3,000\\
\mbox{multiples of }\{3,5,7\}: & \lfloor 210,000/105\rfloor &=& 2,000\\
\hline
 &&& +  17,000
\end{array}\]

And subtract out the multiples of $2\cdot3\cdot5\cdot7 = 210$:

\[\begin{array}{llr}
\mbox{multiples of }\{2,3,5,7\}: & \lfloor 210,000/210\rfloor &=  1,000\\
\hline
 &&-  1,000
\end{array}\]

Totaling, we get $246,996 - 101,000 + 17,000 - 1,000 = 161,996$, which is
more than the $160,000$ composite numbers whose existence we needed to
establish.

} 
\end{enumerate}


\ignore{
%pset7 problem3 spring98
%inclusion-exclusion
\problem{\mbox{}}

A positive integer is called {\em square-free} if it is not
divisible by the square of any positive integer greater than 1.
For example $35 = 5 \cdot 7$ is square-free but $18 = 2 \cdot 3^2$
is not. $1$ is square-free.
Find the number of square-free positive integers which are less than
or equal to 150.

\solution{\medskip
\textbf{Solution:}
\medskip
        
We use inclusion-exclusion as done in lecture for the case
of prime numbers. We first compute the number of positive
integers less than 150 that are not square free.

Let $A_2$ (respectively, $A_3$, $A_5$, $A_7$, $A_{11}$) 
be the set of multiples of $2^2$ (respectively, $3^2$, $5^2$, $7^2$, $11^2$)
less than 150. The cardinality of the union of these sets is given by

\begin {eqnarray*}
 |A_2 \cup A_3 \cup A_5 \cup A_7 | & = &
|A_2| + |A_3| + |A_5| + |A_7| + |A_{11}|
- |A_2 \cap A_3 | - |A_2 \cap A_5|\\
& = & \lfloor 150/2^2 \rfloor +  \lfloor 150/3^2 \rfloor + \lfloor 150/5^2 \rfloor
+ \lfloor 150/7^2 \rfloor + \lfloor 150/11^2 \rfloor\\
& &  - \lfloor 150/(2^23^2) \rfloor
- \lfloor 150/(2^25^2) \rfloor\\
& = & 37 + 16 + 6 + 3 + 1 -4-1\\
& = & 58
\end {eqnarray*}
Therefore the number of square-free positive integers less than
150 is

\[ 150 - 58 = 92 \ . \]
}
}
          
\problem 
%\textbf{Inclusion-exclusion}
%basic permutations
%number of different bijections between two sets

A certain company wants to have security for their computer
systems.  So they have given everyone a name and password.  The 
passwords are exactly 10 letters long.

\bparts

\ppart If all the passwords must satisfy the following rules, how many
possible passwords are there :
\begin{enumerate}
\item[1.] The passwords must be permutations of the 
    letters (a, d, f, i, l, o, p, r, s, t)
\item[2.] No password can contain the sequence "fail"
\item[3.] No password can contain the sequence "drop"
\end{enumerate}

\solution{
\medskip
\textbf{Solution:}
\medskip
The possible passwords = total number of permutations - ``illegal" permutations (containing ``fail" or ``drop"). The total number of permutations of the letters is $10!$. According to the inclusion-exclusion principle, the number of permutations containing either ``fail" or ``drop" is: 

permutations containing "fail" - permutations containing "drop" + permutations
containing "fail" and "drop".

The number of permutations that contain the sequence "fail" can be seen as
finding the number of permutations of the following 7 elements : \{d,o,
p, r, s, t, \fbox{fail}\} which is $7!$.  A similar argument holds for the number
of permutations with "drop", so these are also $7!$.

The number of permutations with both "fail" and "drop" is
the same as finding the number of permutations of the following 4
elements \{ \fbox{drop}, \fbox{fail}, s, t\} = $4!$

Thus possible = $10! - 7! - 7! + 4!$.
}

\ppart Bob is trying to break into the system.  He has obtained
the list of all the passwords and the list of all the names, yet he
doesnt know which passwords go with which names.  If the password file
contains 100 passwords and there are a 100 names, 
how many possible ways can those passwords be
associated with the names? Approximate your answer using Stirling's
approximation.


\solution{
\medskip
\textbf{Solution:}

\medskip
There are 100 possible names for the first password, 99 for the 
second, ... and 1 possible for the last.  Multiplying these possiblities 
together gives you $100!$. By Stirling's approximation this is
approximately $9.32\times 10^{157}$.

Notice that the problem could also be stated as: ``find the number of \emph{bijections} from the set of names to the set of passwords.
}

\ppart When trying to break into the system, Bob doesn't have to
submit an entire matching of the 100 user names with the 100 passwords
at the same time. Instead, he can try individual pairs of names and
passwords, i.e., he can try to login as any of the 100 users with any
of the 100 passwords and see if the login attempt is successful.

Describe a (good) strategy that Bob can use to completely determine
the pairing of names with passwords. How many login attempts does Bob
need to determine the entire matching in the worst case?

\solution{\textbf{Solution:}
\medskip

Bob uses the following strategy: First he figures out the password for
the first name on the list. In the \emph{worst} case, he'll have to try 99 passwords (if he fails the first 99 times, he knows that the last password is correct so he doesn't need to try it). Then, for the second name, there are 99 possible passwords so he needs to try 98 of them in the worst case, and so on. For the 99th password there are 2 possible choices, so he needs to try 1 in the worst case, and he always gets the 100th password for free. 

So, in the worst case, he needs $99 + 98 + 97 + \cdots + 1 = 4,950$ trials.}

\ignore{%
\ppart Bob realizes that trying every possibility from part (b) will
take a long time.  But he is still determined to figure out which
names belong with each password.  He then realizes that names were
mapped to passwords using a single function $f$ chosen by the system manager
in advance from a set of five
functions $\set{f_1,f_2,f_3,f_4,f_5}$, i.e.,
$f(\mathrm{name}_i)=\mathrm{password}_i$.  Can Bob map names to
passwords any faster now? (Note: Bob knows the set of functions and
can compute himself $f_i$ for any $i$).

\solution{ \medskip
\textbf{Solution:}
\medskip

Yes, Bob can map names to passwords faster now.
For each $1\leq i\leq 100$, Bob
goes down the list of names evaluating $f_i(name)$ and checking if the result
allows him to enter the account in question.
If for all names this works, then Bob uses $f_i$ for the mapping from now on.
This takes $500$ trials, as there are $100$ trials per function and
there are $5$ functions. }
}

\eparts            
\problem Your 6.042 tutorial has 12 students, who are supposed to break up into 4 groups of 3 students each. Your TA has observed that the students waste too much time trying to form balanced groups, so he decided to pre-assign students to groups and email the group assignments to his students.

\problempart {\bf 1 point} Your TA is the laziest person on the
planet. He has a list of the 12 students in front of him. How would
he form groups of 3?

\solution{\textbf{Solution:}
\medskip
The TA would divide the list from the top down.}

\problempart {\bf 9 points} How many \emph{different} group
assignments are possible? (Clarification: There is no ``numbering" of
the groups. All that matters is who ends up with whom. Two group
assignments are different if they differ in at least one group.)
\solution{

\textbf{Solution:}
\medskip

Notice the similarity to Problem 2 in Tutorial 8, which asked you to find in how many ways $2n$ students can be divided into $n$ pairs. The answer was $\frac{(2n)!}{2^n\cdot n!}$ where the numerator represents the different permutations of the list of students, and the denominator represents the number of different permutations that give rise to the \emph{same} grouping. 
 
In this problem, say the list is ABCDEFGHIJKL. The lazy TA's policy gives the following grouping: \fbox{ABC}\fbox{DEF}\fbox{GHI}\fbox{JKL}. There are $12!$ different permutations of the list. However, not all permutations result in a different group assignment. For example, if B and C change places, the list is different but the assignment is the same. We will try to see how many different lists represent the \emph{same} group. 

There are $3!$ ways to move the people in \fbox{ABC} around without changing the assignment. The same holds for all other groups. This means that there are $(3!)^4$ ways to move people around within their group.
 
Then, if \fbox{ABC} switches places with \fbox{JKL} we still get the same assignment. There are $4!$ ways to permute the groups without actually affecting the assignment. 

So, there are $4! (3!)^4$ different lists that end up producing the same assignment. 

There are $12!$ possible lists, and each assignment is represented by \emph{exactly} $4! (3!)^4$ different lists so according to the \emph{division rule} there are 
\[
\frac{12!}{4!\cdot(3!)^4}=15400
\]
 different assignments.

\paragraph{Alternative solution} Another way to see this is as follows:

We need to compute the number of partitions of a set of 12~students
into 4~groups of 3~students each. We first compute the number of
partitions given that the groups are numbered. The first group can be
selected in $\binom{12}{3}$ ways, the second in $\binom{9}{3}$ ways,
the third in $\binom{6}{3}$ ways, and the fourth in $\binom{3}{3}$
ways. Therefore, the number of different partitions is
\begin{displaymath}
  \binom{12}{3}\binom{9}{3}\binom{6}{3}\binom{3}{3}
  =
  \frac{12!}{(3!)^4}= 369600.
\end{displaymath}
Now, to account for the fact that the groups are not numbered, we need
to divide $369600$ by the number of permutations of the numbered
groups, $4! = 24$. To conclude, the number of tutorials we can have in
6.042 is at most $369600 / 24 = 15400$.
}


\problem Solve the following counting problems. Give your answers in terms of factorials and binomial coefficients and then evaluate them.
\begin{problemparts}

\problempart A bug starts at position $(0, 0)$ and wants to reach
position $(4, 6)$ in 10 steps.  Each step is either north, south,
east, or west; that is, each step either increments or decrements one
coordinate.  How many different paths can the bug choose from?

\solution{
\medskip
\textbf{Solution:}
\medskip
\[
\binom{10}{4}=210
\]
}

\problempart How many five-card poker hands contain no diamonds?

\solution{\medskip
\textbf{Solution:}
 
\[
\binom{39}{5}=575757
\]
}



\problempart A flush in poker is a hand with all cards from the same
suit.  How many flushes are there?

\solution{
\medskip
\textbf{Solution:}
\medskip  
There are $4$ suits to choose from, and $\binom{13}{5}$ ways to choose 5 cards in the \emph{same} suit. Thus the answer is\[
4\binom{13}{5}=5148
\]
}

\problempart A straight in poker is a hand with 5 consecutive card
values (no wraparound, and suite don't matter).  How many straights
are there?

\solution{
\medskip
\textbf{Solution:}
\medskip
        
So a straight looks like this: A,2,3,\fbox{4,5,6,7,8},9,10,J,Q,F,A. Assuming that an Ace can end a straight, there are 10 ways to choose the \emph{lowest} value (which was 4 in the example). There are 4 ways to choose the suit for each card, which means that there are $4^5$ ways
to choose the suits once you have chosen the lowest value.  Therefore, there are $10 \cdot 4^5=10,240$ such hands.} 

\problempart How many straight flushes are there?

\solution{
\medskip
\textbf{Solution:}
\medskip
        
Like in the previous part, there are 10 ways to choose the lowest value. There are $4$ ways
to choose the suit.  Therefore, there are $10 \cdot 4=40$ such hands.} 

\end{problemparts}        
%pset7 problem6 spring98
\problem
Six women and nine men are on the faculty of a school's
EECS department.  The individuals are distinguishable.
How many ways are there to select a committee of 5
members if at least 1 woman must be on the committee?

\solution{\medskip
\textbf{Solution:}
\medskip
        
\paragraph{First method: (by brute force)}We need to count all possible combinations of people such that there
is at least one woman in every combination, but we must remember not
to count any combinations multiple times.  

We can have committees with 

1 woman, 4 men: $ { 6 \choose 1} {9 \choose 4}$\\
2 women, 3 men: $ { 6 \choose 2} {9 \choose 3}$\\
3 women, 2 men: $ { 6 \choose 3} {9 \choose 2}$\\
4 women, 1 man: $ { 6 \choose 4} {9 \choose 1}$\\
5 women, 0 men: $ { 6 \choose 5} {9 \choose 0}$\\

So there are 
$ { 6 \choose 1} {9 \choose 4} 
+ { 6 \choose 2} {9 \choose 3}
+ { 6 \choose 3} {9 \choose 2}
+ { 6 \choose 4} {9 \choose 1}
+ { 6 \choose 5} {9 \choose 0} = 2877$ different possibilities for
committees.

\paragraph{Second method:}Another way to solve this problem is to say that there are ${15 \choose 5}$
different committees, and ${9 \choose 5}$ committees of just men.  So there
are ${15 \choose 5} - {9 \choose 5}= 2877$ different possibilities for committees. 
\medskip

Note that $6 \cdot { 14 \choose 4} =6006$ is not a correct answer.  
The product rule
only applies when you are choosing two separate sets of items which are
independent of each other.  
In this case, a
woman is chosen and then the remainder of the committee is chosen, but since
there may be women in the last set of $4$ chosen, we will be double counting.
For example, if $A$ and $B$ are women, and $C, D, $ and $E$ are men, then
we will count $A, \{BCDE\}$ as well as $B, \{ACDE\}$.  
}                    

\ignore{
\problem %(10 points)
% Product rule, trees

How many bit strings of length 10 contain either five consecutive $0$s
or five consecutive $1$s?

\solution{
\medskip
\textbf{Solution:}
\medskip

There are $2^{10}$ bit strings of length 10. First, let's see how many of those contain five consecutive $0$'s. The sequence of the 5 $0$'s can start at position $1,2,3,4,5$ or $6$. In each case, the remaining $5$ bits are allowed to be anything, so, as a ``first approximation'', we can say that there are $6*2^5$ different strings of consecutive $0$'s. \par However, if we do this, we are \emph{overcounting} since, for example, the string that has its first $8$ bits equal to $0$ and the last $2$ equal to $1$ (that is, $0000000011$) will be counted as a valid string \emph{four times} by our method:  \fbox{00000}00011, 0\fbox{00000}0011, 00\fbox{00000}011 and 000\fbox{00000}11. We need to eliminate these duplicates, which occur whenever we are dealing with strings that have more than 5 consecutive $0$'s. \par

We can do this by calculating the number of strings with $6$ or more consecutive $0$'s using the same method as above. This will give us $5*2^4$ such strings, and for each sequence of $0$'s, we will be overcounting exactly one time less than we overcounted above: for example, going back to the string of $8$ consecutive $0$'s that was counted 4 times above, we see that this method will count it exactly $3$ times \fbox{000000}0011, 0\fbox{000000}011, 00\fbox{000000}11.  The same will hold for all strings of length $\geq 6$ because the number of allowed starting positions for a sequence of $6$ $0$'s is exactly one less than the number of allowed starting positions for a sequence of $5$ consecutive $0$'s. Thus, it suffices to subtract this number from  the number we got before to get rid of duplicates. Therefore, the number of strings containing 5 or more consecutive $0$'s is  
\[
6*2^5-5*2^4=112\]
By symmetry, there are another 112 strings which contain five consecutive $1$'s. The question was to determine the number of strings that have either 5 $0$'s or 5 $1$'s. So, we are looking for the size of the union of those two sets (the bit strings with 5 $0$'s and the bit strings with 5 $1$'s). The intersection of the 2 sets (i.e, sequences that contain \emph{both} 5 $0$'s and 5 $1$'s) contains 2 elements: $0000011111$ and $1111100000$. Therefore, by the inclusion-exclusion principle, the size of the union of the two sets is $112+112-2=222$

}  
}



\problem
On a set of $n$ elements how many of the following are there?

\ppart binary relations

\solution{
\medskip
\textbf{Solution:}
\medskip

    $2^{n^2}$ since there are this many different $0-1$ matrices of order $n$.
}   
\ppart symmetric binary relations

\solution{
\medskip
\textbf{Solution:}
\medskip
The matrix associated with a symmetric relation is symmetric.  Since there are $2^{n+\binom{n}{2}}$ different symmetric matrices there are an equal number of symmetric relations.
}

\ppart reflexive binary relations

\solution{
\medskip
\textbf{Solution:}
\medskip
The matrix associated with a reflexive relation has $1$'s along the main diagonal . Hence the
number of such matrices, and therefore reflexive relations, is $2^{n^2 - n}$.
}
\ppart symmetric and reflexive binary relations

\solution{
\medskip
\textbf{Solution:}
\medskip
The matrix
  associated with a symmetric and reflexive relation is symmetric and
  has $1$'s along the main diagonal. Hence the number of such
  relations is $2^{\binom{n}{2} }$.}

\ppart symmetric or reflexive binary relations

\solution{
\medskip
\textbf{Solution:}
\medskip
The number of
  symmetric or reflexive relations $=$ the number of reflexive
  relations $+$ the number of symmetric relations $-$ the number of
  reflexive and symmetric relations $= 2^{n^2 - n} + 2^{n+\binom{n}{2}} - 2^{\binom{n}{2}}$.
}
                  

\problem In Professor Karger's folk-dance class, dances are made of
four basic steps: a grapevine, a debka, a Yemenite, and a pivot.
There are some constraints:
\begin{itemize}
\item  A grapevine cannot follow a debka, and a debka cannot follow a
grapevine.  
\item A pivot cannot follow a Yemenite.  
\item Every dance must have at least one Yemenite
\end{itemize}
It \emph{is} permissible to repeat the same step multiple times, but
there must be at least 2 distinct steps in a dance.

How many distinct dances are there made up of a sequence of 4 basic
steps?

\solution{
93. Use a tree diagram to see this. 
}

\end{problems}

\end{document}                            

