\documentclass[11pt,twoside]{article}
\usepackage{amsmath}
\usepackage{graphics}
\input{/pub/www/classes/6.042/fall99/inputs/macros-course}

\renewcommand{\solution}[1]{}
%\renewcommand{\solution}[1]{\bigskip {\bf Solution:}\\ #1\bigskip}

\newcommand{\kignore}[1]{}

\begin{document}
\pset{8}{1999 October 28}{start of tutorial, 1999 November 5}

\textbf{Reading}: F97 Lec Notes 14, Rosen 5.5-6, 4.3

{\large
Remember to include a \textbf{collaboration statement} on the front page
of your solutions (see Handout 2, \emph{Course Information}).}


\begin{problems}

\problem \textbf{Enumeration, permutations, and derangements}

\bparts

\ppart Lars Beefcake is manager of the MIT Chess Club.  After a long
and grueling match, the players have gone home, leaving Lars to put
the players' unlabelled chess sets back in their lockers.  If there
are $n$ players/lockers and $n$ chess sets, how many ways could Lars
place chess sets in lockers such that there is exactly one chess set
in each locker, disregarding the correctness of such placement?

\solution{We can formulate this as a function-counting problem.  Since
there are $n$ chess sets and $n$ lockers, we can assign each chess set a
unique number between 1 and $n$ inclusive, and do the same for the
lockers.  Then, we are looking for an injective function from
$\set{1,\ldots,n}\rightarrow \set{1,\ldots,n}$.

Note that the first element of the domain has $n$ possible mappings;
the second has $n-1$ possible mappings (i.e., all but the first
element); the third has $n-2$ possible mappings (i.e., all but the
first two); and so on, for all $n$ elements of the domain.  This is
simply $n!$, the number of permutations of $\set{1,\ldots,n}$.}

\ppart This begs the question: how many ways can Lars achieve the feat
of placing every chess set in the wrong locker?  Give an expression
for general $n$ and then approximate the value for $n=10$.

\solution{This is the number of \textit{derangements} of the set of
$n$ elements.  We do not know a closed form for this number, so we
denote it by $D_n$ as derived in  Rosen, \S 5.6.  
To approximate $D_{10}$ we will use Sterling's approximation,
$D_{10}\approx$ something
=)}

\ppart Say Lars recognizes Dexter's chess set, so he can place that
one correctly, but recognizes none of the other chess sets.  How many
possible ways can Lars place chess sets in lockers assuming he at
least gets Dexter's right?

\solution{We function count, as before.  Without loss of generality,
assign Dexter's chess set and locker the number 1, and set $f(1)=1$ in
our function.  We can now create an injective function on the
remaining elements; by part (a), this is simply $(n-1)!$.  }

\ppart Say Lars really resents Dexter's brainpower, and decides to get
even by putting Dexter's chess set in another student's locker.  How
many ways can he place chess sets in lockers assuming he does not
place Dexter's chess set into Dexter's locker?

\solution{Again, we function count.  (Notice a pattern?)  Without loss
of generality, assign Dexter's chess set and locker the number 1, as
before.  We can first choose an element $j\not=1$ from the domain to
map to $1$ ($(n-1)$ ways).  Then, we note that we have $n-1$ elements
of the domain and $n-1$ elements of the codomain in which we want an
injection, which we can choose in $(n-1)!$ ways from part (a).  This
gives us $(n-1)(n-1)!$, which makes sense since, from part (b),
$(n-1)(n-1)!+(n-1)!=n!$.}

\ppart Lars has a sudden change of heart and decides to be
nice to Dexter.  At this time, he also realizes that Frohike has
conscientiously written his name on the outside of his chess set, so
now Lars knows the correct destinations of two chess sets.  How many
arrangements are there now?

\solution{As in part (b), we can simply create an injective function
on the remaining elements, which gives us $(n-2)!$.}

\ppart Say Lars is taking mind-altering drugs and has again changed
his mind about Dexter.  Still being able to discern Dexter's and
Frohike's chess sets---but wishing to ill-place Dexter's---Lars can
place chess sets in lockers in how many ways?

\solution{Assign 1 to Dexter's locker and chess set, and 2 to
Frohike's locker and chess set.  We know that $|A\cap
B|=|A|-|A\cap\bar B|$, so if we take $A$ to be the set of functions
with $f(2)=2$ and $B$ to be the set of functions with $f(1)\not=1$,
then we know $|A|$ and $|A\cap\bar B|$, the latter of which is the
solution to the previous part; so, the answer is
$(n-1)!-(n-2)!=(n-2)(n-2)!$. 
}

\eparts

\problem \textbf{Pigeonhole principle}

Skipped

\kignore{
\bparts

\ppart Prove that if we have $P(n,k)+1$ distinct permutations of the
numbers $1,\ldots,n$, we must have at least one in which the elements
$1,\ldots,k$ are in order.

\solution{We can imagine creating the set $A$ of permutations with
$1,\ldots,k$ in order by choosing a starting position for the
length-$k$ subsequence (between $1$ and $n-k+1$) and then permuting
the rest of the elements arbitrarily around them (in $(n-k)!$ ways).
This gives us a total of $(n-k+1)(n-k)!$ permutations with
$1,\ldots,k$ in order.

If we divide the space of $n!$ permutations into $(n-k+1)(n-k)!$
buckets, each with exactly one permutation from $A$, the we note that
if we choose \[ \frac{n!}{(n-k+1)(n-k)!} + 1 = \frac{P(n,k)}{n-k+1} +
1 \] permutations, we are guaranteed to have at least two from one
bucket.  Since $P(n,k)\geq \frac{P(n,k)}{n-k+1}$, the theorem
follows.}

\eparts
}


\problem \textbf{Sieving}

Consider the {\it medieval puzzle} of the woman and the eggs. On her
way to the market to sell her eggs, a horseman knocks the old woman
down by accident, causing all the eggs to be broken. He offers to
pay the damages and wants to know how many eggs she had. She says she
does not remember the exact number, but when she took them 2 at a
time, 1 was left over. One was also left over when she took them
3,4,5,6, at a time; however when they were taken 7 at a time, it came
out even.

\bparts

\ppart
If the woman had less than 1000 eggs, how many
possibilities are there for the exact number of eggs she had?


\solution{
We first realize that the woman could have N eggs if and only if N was
simultaneously $1\bmod k$ for $k=2,3,4,5,6$ and $0\bmod 7$.
Set  $A_i$ to be the set of integers between 1 and 1000 which are congruent to
$1\bmod {i-1}$ for $i=2\ldots 6$  and $A_6$ be the set of integers
between 1 and 1000 congruent to $0\bmod 7$.

The number of exact eggs the woman may have had is the
intersection of all the sets $A_i$ for $i=1,\ldots,6$.
Use the formula for the inclusion-exclusion principle on page 359 of
Rosen to compute the cardinality of this intersection plugging in
numerical values for the cardinality of the above  sets and their
various intersections necessary for the computation.}

\ppart
Describe a procedure whereby the old woman can determine all values less than
1000 that are possibilities for the exact number of eggs she may
have had, using a sieve.

(Hint: This can be solved in a manner analogous to the {\it sieve of
  Eratosthenes} for enumerating all primes upto
$N^2$ in which we remove all numbers $k$ between $1$ and
$N^2$ that simultaneously satisfy the following constraints:
$k\equiv 0\bmod 2, k\equiv 0\bmod 3,k\equiv 0 \bmod 5,\ldots,k\equiv
0\bmod p $ where p is the largest prime less than or equal to $N$.
Here you need to figure out a strategy for removing numbers of eggs
less than a 1000 from the list so what remains are candidates for the
exact numberof eggs.)

\solution{
As above, we use the observation that
the woman could have N eggs if and only if N was
simultaneously $1\bmod k$ for k=2,3,4,5,6 and $0\bmod 7$.
This leads to the following sieving strategy.
List all numbers from 1 to 1000. First cross out all numbers which
are congruent to 0 mod 2, then cross out all those congruent to
0 or 2 mod 3, then all those congruent to 0,2 or 3 mod 4,
then all those congruent to 0,2,3,4,5 mod 6  and finally those
congruent to 1,2,3,4,5,6 mod 7.  Whats left are the choices
for the exact number of eggs the woman had. Note that 
if you write a short computer
program to implement your process, you may check your
answer to part (a) using this method.}

\eparts

\problem \textbf{Inclusion-exclusion}

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{
The possible passwords = total number of permutations - permutations
containing "fail" - permutations containing "drop" + permutations
containing "fail" and "drop".

The total number of permutations of the letters is $10!$.  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, fail) which is $7!$.  The same can be seen with the number
of permutations with "drop" = $7!$.

The number of permutations with both "fail" and "drop" is
the same as finding the number of permutations of the following 4
elements (drop, 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 Sterling's
approximation.


\solution{
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 Sterling's approximation this is
approximately $9.32\times 10^{157}$.
}

\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{ Yes, Bob can map names to passwords faster now.
For each $1\leq i\leq 100$, Bob
goes down the list of names evaluating $candidate-password= f_i(name)$ and checking if the resulting
$candidate-password$ 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. }
\eparts

\problem \textbf{Coloring}

There are 4 people looking for companies to work for: Alice, Bob, 
Chris, and Dave.  Alice refuses to work for the same company as any of 
the guys.  Dave also doesnt want to work for the same company as any 
of the other people. 

\bparts

\ppart How could you represent the constraints on who is willing to
work with other people as a graph coloring problem ?

\solution{
This can be represented as a graph with nodes representing
the people, and edges representing people who do not want to work
together. Assigning a color to a node would correspond to assigning
a company to a person. Thus your graph could look like :

\begin{figure}[h]
\centerline{\resizebox{!}{1.5in}{\includegraphics{ps5-p5.eps}}}
\end{figure}
}
\ppart How many ways from $n$ possible companies(where $n >=4$ and
more than one person can work for each company) can these people work
and still be happy ?

\solution{
The graph can be colored using either 4 colors or 3 colors. 

You have to figure out the number of ways to color the graph
when $n$ colors ($n$ possible jobs) are available, using 4 colors.  
This is just equal to the number of permutations : $P(n,4)$.

Then the number of possible ways to color the graph using 3
colors from $n$ colors.  This is $P(n,3)$.

Total = $P(n,3) + P(n,4)$.
}

\eparts

\kignore{
\problem \textbf{Inclusion-exclusion}

\bparts

\ppart Let $S$ be a set with $n$ elements.  Fix a constant $k$.  How
many sequences $(T_1,T_2,\ldots,T_k)$ of subsets of $S$ are there such
that $T_1\subseteq T_2\subseteq \cdots\subseteq T_k$?  Note that the
subset relation is not strict.

\solution{For each element $x\in S$, we can choose the set $T_i$ in
which it first appears, after which it appears in all $T_j$ for $j\geq
i$; there are $k+1$ choices for each ($k$ sets plus one for the choice
in which it never appears), so there are $(k+1)^n$ such sequences.}

\ppart Suppose Dana answers the previous question correctly, and is
feeling confident enough to tackle the variant where the subset
relations are strict (i.e., $T_1\subset T_2\subset \cdots\subset
T_k$).  She proceeds by describing an enumeration strategy.

She first chooses a $(k-1)$-sized subset $Q\subseteq S$ and permutes
those elements into a sequence $(e_2,e_3,\ldots,e_k)$ such that
$\forall i,j$ where $j\leq i$, $e_j\in T_i$ but $e_j\not\in T_{i-1}$;
then, for each of the remaining elements $x\in S-Q$, she chooses an
$i$ such that either $i=k+1$ or $x\in T_i$ but $x\not\in T_{i-1}$,
effectively introducing $x$ into the sequence of sets at position $i$.

Fox tells her that her enumeration strategy miscounts.  Who is right,
and why?

\solution{Dana is overcounting.  Suppose $n\geq k$; fix $S$ and
$Q$.  Then, $\exists x\in S-Q$, since $|S|>|Q|$.  If we place $x$ in
the same set with $e_2$ (i.e., $T_2$), then we can choose a new $Q'$
and sequence $(x,e_3,\ldots,e_k)$ with associated sets
$(T_1,T_2',T_3,\ldots,T_k)$.  Now, choose to place $e_2$ (which is not
in our sequence) into $T_2'$, so $T_2=T_2'$ with all other sets the
same; clearly, we are then counting this sequence twice.}

\eparts
}

\end{problems}

\newpage

\section*{Topics for Week of November 1st, 1999}

\subsection*{Counting I\\
F97 Lec Notes 14, Rosen 5.5-6, 4.3}

\begin{itemize}
\item 
Computing the cardinality of unions of sets 
\begin{itemize}
\item
Disjoint Sets (the sum rule)
\item
Overlapping Sets (inclusion-exclusion principle for n sets)
\end{itemize}
\item
Computing the cardinality of products of sets(the product rule)
\item
Combination of sum and product rules (tree diagrams)
\item 
Permutations 
\item
Using permutations to lower bound the running time of algorithms 
\item
$r$-permutations 
\item
Sieve of Eratosthenes
\item
Derangements
\end{itemize}

\end{document}

\problem \textbf{Sieving}
Recall the Fibonacci numbers $(0,1,1,2,3,5,8,13,21,\ldots)$ defined by
\begin{enumerate}
\item $F(0) = 0$
\item $F(1) = 1$
\item $F(n) = F(n-1)+F(n-2)$
\end{enumerate}

\bparts

\ppart Which Fibonacci numbers are multiples of 2 ? of 3? of 5?

\solution{
Every 3rd Fibonacci number is a multiple of 2.

Every 4th Fibonacci number is a multiple of 3.

Every 5th Fibonacci number is a multiple of 5.
}

\ppart Find a generalization of part (a).

\solution{
Every kth Fibonacci number is a multiple of $F(k)$.
}

\ppart How many fibonacci numbers less than $F(100)$ are not multiples
of 3 or 8 or 13?

\solution{
Every 4th Fibonacci number is multiple of 3
Every 6th Fibonacci number is multiple of 8
Every 7th Fibonacci number is multiple of 13

Total = 101 (since fibonacci numbers start with index 0)

The number of multiples of 3 = 101/4 

multiples of 8 = 101/6

multiples of 13 = 101/7

multiples of 3 and 8 = 101/12  (since 12 is lcm(4,6))

multiples of 3 and 13 = 101/28 (since 28 is lcm(4,7))

multiples of 8 and 13 = 101/42 (since 42 is lcm(6,7))

multiples of 3 and 8 and 13 = 101/84 (since 84 is lm(4,6,7))

Plugging in all the values leaves you with 

Total - multiples of 3 - multiples of 8 - multiples of 13 
     + multiples of 3 and 8 + multiples of 3 and 13 + multiples of 8 and 13
     - multiples of 3 and 8 and 13

$=101 - 101/4 - 101/6 - 101/7 + 101/12 + 101/28 + 101/42 - 101/84$

$=101 - 25 - 16 - 14 + 8 + 3 + 2 - 1$

$=58$
}

\eparts


\end{document}




