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

\newcommand{\kignore}[1]{}

\begin{document}
\psol{8}{1999 November 6}

\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
\textit{unique} number between 1 and $n$ inclusive, and do the same
for the lockers.  Thus, we are looking for an injective function $f$
from $\set{1,\ldots,n}\rightarrow \set{1,\ldots,n}$, since we want
that no two chess sets are mapped to the same locker (i.e., we want
that $f(x)=f(y)\Rightarrow x=y$ for all $x,y\in\set{1,\ldots,n}$.)

Note that the first element of the codomain has $n$ possible
preimages; the second has $n-1$ possible mappings (i.e., all but the
first preimage); the third has $n-2$ possible mappings (i.e., all but
the first two preimages); and so on, for all $n$ elements of the
codomain.  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}$, use Sterling's approximation. This gives us approximately 
$1.33\times 10^6$.}

\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 count functions, as before.  We note that since we want
Dexter's chess set (give it number $a$) to appear in Dexter's locker
(give it number $b$), it must be that $f(a)=b$ in the function we are
constructing.  The first remaining element of the codomain then has
$n-1$ choices of preimage (since Dexter's chess set can't go into more
than one locker!), the second remaining element of the codomain has
$n-2$ choices of preimage, and so forth.

This gives us $(n-1)!$ possible configurations of chess sets.  We can
also get here by employing symmetry and using part (a).  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?)  The opposite
of the solution to part (c), we want $f(a)=c$ for some $c\not=b$; we
can therefore choose $c$ in $n-1$ ways.  Then, since we don't care
where the other chess sets go, we have $n-1$ possible preimages for
the first remaining element of the codomain, $n-2$ possible preimages
for the second remaining element of the codomain, and so forth.  This
gives us $(n-1)\times(n-1)!$ ways to arrange the chess sets.

This should make sense since, from part (c), $(n-1)(n-1)!+(n-1)!=n!$,
the total number of arrangements of $n$ chess sets into $n$ lockers.}

\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{This is basically the same as part (c).  Say Frohike's chess
set is $c$ and his locker is $d$; then, we want $f(a)=b$ and
$f(c)=d$.  The first remaining element of the codomain has $n-2$
possible preimages, the second remaining element of the codomain has
$n-3$ possible preimages, and so forth.  This gives us $(n-2)!$
possible ways to arrange chess sets in lockers.}

\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{This is inclusion exclusion on parts (c) and (e). We know
that $|A\cap B|=|A|-|A\cap\bar B|$, so if we take $A$ to be the set of
functions with $f(a)=b$ and $B$ to be the set of functions with
$f(c)\not=d$, then we know $|A|$ and $|A\cap\bar B|$, the latter of
which is the solution to part (e); so, the answer is
$(n-1)!-(n-2)!$.  }

\eparts

\problem \textbf{Cancelled}

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

{\bf 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$. But this
is equivalent to saying that $k | (N-1)$ for $k=2,3,4,5,6$ and $7 |
N$. Notice that the first condition, $k | (N-1)$ for $k=2,3,4,5,6$, is
equivalent to $\lcm(2,3,4,5,6) | (N-1)$, where $\lcm$ is the least
common multiple. 
Therefore, we want to find out possible values of $N<1000$
such that $60 | (N-1)$ and $7 | N$, 
as $\lcm(2,3,4,5,6)=60$. This is the same as finding values
of $j$ such that $60 j + 1 < 1000$ and $7 | (60 j + 1)$. The latter
condition just reduces to requiring that $7 | (4 j + 1)$, and the
possible values of $j$ that satisfy the above conditions are $5$ and
$12$. Therefore $N=301$ and $721$ are the possible values for
the exact number of eggs she had.

Alternatively, set  $A_i$ to be the set of integers 
between 1 and 1000 which are congruent to
$1\bmod {(i+1)}$ for $i=1\ldots 5$  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.

A simple computer program could also be used to generate the result. A
version of C++ code is given below.

\begin{verbatim}
#include<iostream.h>

int main(){

// returns the number of possibilities for the exact number of eggs the
// woman had. It also displays those values.

  #define MAXEGGS 1000
  int temp;
  int possibleValues = 0;
  for (temp=1; temp<MAXEGGS; temp++)
    if ((temp%2 == 1) && (temp%3 == 1) && (temp%4 == 1) && 
        (temp%5 == 1) && (temp%6 == 1) && (temp%7 == 0)){
      cout<<temp<<"\n";
      possibleValues++;}
  cout<<"The "<<possibleValues<<" values above are the 
        possiblities for the exact number of eggs she had.\n";
  return possibleValues;
}
\end{verbatim}
This produces the output:
\begin{verbatim}
301
721
The 2 values above are the possiblities for the exact number of eggs she had.
\end{verbatim}

{\bf endsoln}

\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 $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 \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. Namely, there is an edge between Alice and every one else
and between Dave and every one else. 
Assigning a color to a node would correspond to assigning
a company to a person. 
Recall that a legal graph coloring does
not allow edges to connect nodes of same color, thus a legal coloring
of the graph would imply an assignment of people to jobs respecting
their wishes. 
Thus your graph could look like :

\begin{figure}[h]
\centerline{\resizebox{!}{1.5in}{\includegraphics{H58-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{
To solve the problem, all that remains is to figure out is
the possible colorings of the graph that exist. 
There are 4 nodes, thus it is possible for the graph to be
colored with 4 separate colors.  In other words, assign a 
different company to each person.  The number of
ways to assign 4 colors to the nodes from n possible
colors, is equal to the number of 4-permutations of the n colors
which equals P(n,4) = n!/(n-4)!

The graph can also be colored with 3 colors.  This is because
there is no edge connecting nodes Bob and Chris, and therefore they may be
colored the same color.  Thus, the number of ways to color the
graph with 3 colors, from $n$ possible colors equals $P(n,3)=n!/(n-3)!$.

The graph can not be colored with fewer colors due to the constraints
represented by the edges, in addition it cannot be colored with more than
4 colors, since there are only 4 nodes.  Thus the total possible assignments
of companies equals
P(n,4) + P(n,3) = n!/(n-4)! + n!/(n-3)! = (n)(n-1)(n-2)(n-2).
}

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




