\documentclass[11pt,twoside]{article}   
\usepackage{latex-macros/course}

\renewcommand{\reading}{ \href{http://theory.lcs.mit.edu/classes/6.042/spring02/handouts/lectures/ln4.pdf}
{Week 7 Notes}, Rosen \S 7 }

%\hidesolutions         
%\showsolutions

\begin{document}
\inclassproblems{7M}
         
%this file prepared by Jack on March 13, 2001

%%%%%%%%%%%%%%%%%%%%%%% PROBLEM %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
%------------------------------------------------
% source: pset6 fall 01 pset 8 problem 2
% topic: 
% last used:

\begin{problem} {\bf In a Bostonian field of dreams...}

In some imaginary world, the Boston Red Sox are playing the New York Yankees
for the World Series Championship title.  In fact, they've already won the first
game of the series, and there is great enthusiasm in Beantown at the prospect
of winning the whole thing.  People in the sports bars talk excitedly about 
the different ways Boston could win (will they sweep it?  will they lose the 
second game but come back and take the next three? ...), but they are all a 
little too inebriated
to figure out all the possibilities.  Wielding your tree diagram method and
your smart MIT brainpower, 
calculate for them
the many many different ways the Red Sox could actually take home the title!  
(For those
of you unfamiliar with baseball, the World Series is a best of seven tournament, 
i.e. the first team to win four games wins the title.)

\solution{The required
\href{http://theory.lcs.mit.edu/classes/6.042/fall01/figures/tree-psol8.jpg}{tree
diagram} is attached.

Alternatively, one can
count the number of ways the Red Sox could win using the combinatorics we have
covered since last week.  We need to choose three games out of six remaining for
the Red Sox to win.  After each third game is played in which the Red Sox win, 
the series is considered over.  Thus, there are $C(6,3) = 20$ possibilities.
}


\end{problem} 


%%%%%%%%%%%%%%%%%%%%%%% PROBLEM %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
%------------------------------------------------
% source: pset6 fall 01 pset 8 problem 4
% topic: Bijection mapping
% last used:


%%

\begin{problem} {\bf The Pig Walk}

Suppose that Theory Pig wants to take a walk on his neighborhood grid to location
$(n, n)$.  He starts at position $(0, 0)$.  At any
time, he can step North (incrementing the first coordinate) or step East
(incrementing the second coordinate).  In this problem, we'll use the Division
Rule to count how many different ways he can reach position $(n, n)$, for
$n \in \nats$.

\begin{problemparts}

\problempart Let's take a mapping that maps a length $2n$ sequence, $p$, 
of the integers $1, 2,
\ldots, 2n$, into a sequence, $p'$, in which odd numbers remain in the same
positions and even numbers remain in the same positions, but the odd and
even numbers are each sorted into increasing order.  This map is $k$ to
one for what $k$?  Explain.

\solution{$k=n!^2$.  Let's look at the even numbers in $p'$ first.  
How many different
ways can we re-order them so as to get strings $p$?  
Take the first even number and consider the
locations we can put it in.  There are $n$ choices, corresponding to the locations
where even numbers occur in string $p'$.  The next even number in $p'$ has $n-1$
choices, etc... so we have $n \times n-1 \times \cdots \times 1 = n!$ possible
re-orderings.  Similarly, there are $n!$ re-orderings for the odd numbers, and so
we have a total of $n!^2$ re-orderings for both the odd and even numbers together,
by the Product Rule.  Since each re-ordering corresponds to a $p$ that maps to
the same $p'$, the given map must be a $n!^2$ to 1 mapping. 
}

\problempart How many different ways are there to list the numbers $1, 2,
\ldots, 2n$ such that the even numbers appear in increasing order and the
odd numbers appear in decreasing order?

\solution{There are $(2n)!$ ways to list the numbers $1, 2, \ldots, n$.
Mapping any such list, $p$, into, $p'$, defines a $n!^2$-to-1 mapping that
takes an arbitrary listing to a listing in which the odd and even numbers
are sorted in increasing order.  Thus, by the Division Rule, there are
$(2n)!/n!^2$ listings in which the odd and even numbers appear in
increasing order.}

\problempart Explain why the number of paths Theory Pig can follow is the
same as the answer to part~(b).

\solution{Each time Theory Pig takes a step North, write down an even
number, starting with 2 and working up.  Each time Theory Pig takes a
step East, write down an odd number, starting with $2n-1$ and working down.

Note that if we use binomial coefficients, to be introduced next week,
then the solution is easy: Theory Pig must take $2n$ steps in total.  Of
these, he must choose a subset of $n$ to be North steps.  This gives
$\binom{2n}{n}$ different ways to reach $(n, n)$.}

\end{problemparts}
\end{problem}


%%%%%%%%%%%%%%%%%%%%%%% PROBLEM %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
%------------------------------------------------
% source: 
% topic: Pigeon Principle
% last used:




\begin{problem} {\bf The Pig Principle}

Having reached $(n,n)$ successfully but having been pooped on by a pigeon
along the way, Theory Pig now has a new beef.  He complains that the name
``Pigeonhole Principle'' is verbose and awkward and proposes the following
``Pig Principle'' that he finds much more relevant to his life:

Suppose that $m$ pigs are lined up, and each pig is given some number of
tasty treats.  Theory Pig asserts that there is always a sequence of one
or more consecutive pigs in the lineup who receive a total number of
treats which is a multiple of $m$.

For example, suppose there are $m = 5$ pigs, and that they
receive 1, 6, 2, 12, and 7 treats respectively.  Then the claim holds
in this case, because the second, third, and fourth pigs received $6 +
2 + 12 = 20$ treats altogether, and 20 is a multiple of 5.

Prove that Theory Pig's Pig Principle is correct.  In the process, you may
have to use the Pigeonhole Principle one last time.  \iffalse (Optionally,
you may want to think about whether the two principles are actually
equivalent, or whether Theory Pig has just proposed a weaker principle to
replace the Pigeonhole Principle.)\fi

\solution{Let $t_i$ be the total number of treats given out to the first
$i$ pigs in the lineup.  There are two cases.

In the first case, suppose that at least one of $t_1, t_2, \ldots, t_m$ is
congruent to 0 modulo $m$.  In particular, suppose that $t_j$ is congruent
to 0 modulo $m$.  This implies that the number of treats received by the
first $j$ pigs is a multiple of $m$, and so the claim holds.

In the second case, suppose that none of $t_1, t_2, \ldots, t_m$ is
congruent to 0 modulo $m$.  Then each of the $m$ terms $t_1, t_2, \ldots,
t_m$ is congruent to one of the $m-1$ values $1, 2, \ldots, m-1$ modulo
$m$.  By the Pigeonhole Principle, there are at least two terms $t_j$ and $t_k$
that are congruent to the same value modulo $m$.  Thus pigs $j+1, j+2,
\ldots, k$ received a total of $t_k - t_j$ treats, which is a multiple of
$m$.}

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%% PROBLEM %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
%------------------------------------------------
% source: pset6 fall 01 pset 8 problem 6
% topic: Inclusion-Exclusion
% last used: fall 01

%%  Inclusion-Exclusion, s98 : ps7, prob 3; Spring '01, Tutorial 8

\begin{problem} {\bf Square-Free}

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.  Use inclusion-exclusion to find the
number of square-free positive integers strictly less than 151.

\solution{We use Inclusion-Exclusion as was done for
\hyperref{http://theory.lcs.mit.edu/classes/6.042/fall01/lectures/l8.pdf}{rule}{count-primes}{counting
prime numbers} in Notes and Rosen.  So we compute the number of positive
integers less than 150 that are \emph{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 union of these sets is the set of all numbers less than 150
which are not square-free, \ie have some square divisor in them.
The reader should take a moment to think through why this assertion
is true (why only primes? why stop at 11?).

The cardinality of this set can be computed by the Inclusion-Exclusion
Principle.  Since $2^2 7^2 > 150$ and $3^25^2 > 150$, it follows that $A_i
\intersect A_j = \emptyset$ unless $\set{i,j}=\set{2,3}$ or $\set{2,5}$,
so

\begin {eqnarray*}
\card{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.
\]
}

%\iffalse

\end {problem}


%%%%%%%%%%%%%%%%%%%%%%% PROBLEM %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
%------------------------------------------------
% source: tutorial 8 fall 01
% topic: Inclusion-Exclusion
% last used: fall 01


\begin{problem} State the Principle of Inclusion-Exclusion for the case of three
sets $A_1,A_2,A_3$ (without looking it up first, if possible).

\solution{
$\card{A_1 \union A_2 \union A_3} =  \card{A_1} + \card{A_2} + \card{A_3} -
\card{A_1 \intersect A_2} - \card{A_1 \intersect A_3} - \card{A_2
\intersect A_3} + \card{A_1 \intersect A_2 \intersect A_3}$.
}
\end{problem}


%%%%%%%%%%%%%%%%%%%%%%% PROBLEM %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
%------------------------------------------------
% source: tutorial 8 fall 01
% topic: Pigeon-hole
% last used: fall 01

% 

\begin{problem} 

Let $S$ be the set of numbers $7, 77, 777, \ldots$. Prove that there
is an element of $S$ that is divisible by $2001$.

\solution{We use the pigeonhole principle.
Let the pigeons be the elements $s \in S$, and
the holes be the numbers $0 \ldots 2000$.  Let $s$ be placed in
$s \bmod 2001$.

Since there are more than 2001 elements of $S$, some hole must have
two numbers, say $s_i$ and $s_j$, with $i$ and $j$ 7's respectively.
Without loss of generality, assume that $i<j$.

Then,
$s_j - s_i = 77 \ldots 700\ldots0$ where there are $j-i$ 7's and $i$ 0's.
So, $s_j - s_i = s_{j-i} \cdot 10^i$.
Since $s_j \bmod 2001 = r = s_i \bmod 2001$,
$s_j - s_i \bmod 2001 = 0$, so $2001 \mid (s_j - s_i)$.  But
$gcd(2001,10^i) = 1$, so 2001 must divide $s_{j-i}$.

}


%\iffalse
\end{problem}

%%%%%%%%%%%%%%%%%%%%%%% PROBLEM %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
%------------------------------------------------
% source: fall99 pset 8 problem 4
% topic: Inclusion-exlcusion
% last used: fall99


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

\begin{problemparts}

\problempart 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!$.
}

\problempart 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}$.
}

\problempart 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. }
\end{problemparts}

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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

\begin{problemparts}

\problempart 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}}}
\end{figure}
}
\problempart 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).
}

\end{problemparts}

\end{problem}

%\kignore{
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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

\begin{problemparts}

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

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

\end{problemparts}
}

\end{problem}




\end{document}                            





