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

\def\bparts{\begin{problemparts}}
\def\eparts{\end{problemparts}}
\def\ppart{\problempart}

\renewcommand{\reading}
{\href{http://theory.lcs.mit.edu/classes/6.042/spring02/handouts/lectures/ln7.pdf}{Week 7 Notes}, Rosen \S 4.1-2 }
\renewcommand{\coursecopyrightnames}{Dr.~Radhika~Nagpal}

%\hidesolutions         
%\showsolutions

\begin{document}
\problemset{7}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%SOURCE:  FALL 01, Pset
%TOPIC:  Counting by Tree Diagram
\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}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%SOURCE: FALL 00, Practice Final #4
%TOPIC: generalized pigeonhole principle
\begin{problem} \textbf{Mall Mania}

For their annual convention, the members of the MIT Antisocial League
rent out the cafeteria at the CambridgeSide Galleria.  The cafeteria
is an $n\times n$ grid of cells, each cell containing exactly one
table and a \textit{single} associated chair.  A chair can be
positioned around its table to face in one of four directions,
corresponding to the axes of the grid.

Due to space considerations, every attendee must sit at a chair.  But,
since this is the Antisocial League, no seated person can directly
face another occupied table (i.e., there can be no one sitting at a
table in a person's direct line of sight).  Use the pigeonhole
principle to prove that this requirement cannot be satisfied if $4n+1$
members attend.

\solution{
  We use the pigeonhole principle to prove the theorem.
  Orient a representation of the grid in some canonical way with one
  axis pointing left-right, and the other pointing up-down.
  
  There are four directions in which people can face.  As a result, by
  the generalized pigeonhole principle, at least $n+1$ people must be
  facing in some direction.  Without loss of generality, assume this
  is downwards.
  
  Create $n$ pigeonholes from the columns of the grid.  By the PP, if
  there are $n+1$ attendees facing downwards, at least two must be in
  the same column, so clearly one must be directly facing another
  occupied table.
  
  It is likely that equality is not achieved (which would be proved by
  demonstrating an arrangement of $4n$ people in which no one directly
  faced another occupied table).  This suggests a stronger theorem can
  be proven.  The best we can do so far is $4n-4$; try to figure out
  such a solution.}

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 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.

All the passwords must be permutations of the letters (a, d, f, i, l, o, p, r, s, t).

\begin{problemparts}
\problempart
How many 10 character passwords are there?
\solution{The total number of permutations of the letters is $10!$.}

\problempart
How many do NOT contain ``fail''?
\solution{We can solve this by substracting the number of passwords that do contain ``fail'' from our answer in part a.  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!$.  Therefore, the number of passwords that do not contain ``fail'' is $10!-7!$.}

\problempart
How many do NOT contain ``drop''?
\solution{Similar to the previous part, the answer is $10!-7!$.}

\problempart
How many contain neither ``fail'' nor ``drop''?
\solution{In order to compute this, we will subtract the number of passwords that contain either ``fail'' or ``drop'' from the number of total passwords.  To figure out the number that contain either ``fail'' or ``drop'', we can use the inclusion-exclusion principle:  $|$passwords that contain ``fail'' or ``drop''$| = |$passwords that contain ``fail''$| + |$passwords that contain ``drop''$| - |$passwords that contain ``fail'' \emph{and} ``drop''$|$.  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!$.  Therefore, the number of passwords with ``fail'' or ``drop'' is $7!+7!-4!$.

Now, we can subtract this quantity from the number of total passwords to arrive at $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}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% SOURCE: Spring 00,TUTORIAL 8, problem 1 
% TOPICS:  product rule and function counting

\begin{problem} \textbf{Counting Functions}

Let $\set{0,1}^n$ be the set of all bit strings of length n.

\begin{problemparts}
\problempart
How many functions are there with domain $\set{0,1}^m$ and codomain $\set{0,1}^n$?
\solution{ There are $2^m$ elements in the domain.   There are $2^n$ choices in the codomain.  For each element in the domain, we have $2^n$ choices for what we can map it to.  Therefore, by the product rule, there are $(2^n)^{2^m}$ possible functions.}

\problempart
A value $x$ is called a \emph{fixed point} of a function $f$ if $f(x) = x$.  How many functions from $\set{0,1}^n$ to $\set{0,1}^n$ have \emph{no} fixed points?
\solution{To count all the function without fixed points, we observe that such a function could map each element of the domain to any element but itself, that is, to any one of the remaining $2^n-1$ elements in the codomain.  There are $2^n$ elements in the domain so by the product rule, there are $(2^n-1)^{2^n}$ such functions with no fixed points.}

\problempart
How many functions from $\set{0,1}^n$ to $\set{0,1}^n$ have \emph{at least one} fixed point?
\solution{There are $(2^n)^{2^n}$ functions, and $(2^n-1)^{2^n}$ have no fixed point.  Therefore, the remaining $(2^n)^{2^n} - (2^n-1)^{2^n}$ have at least one fixed point.}

\problempart
How many functions from $\set{0,1}^n$ to $\set{0,1}^n$ have \emph{exactly one} fixed point?
\solution{Let's fix a particular point for our fixed point.  Now, let's consider where the remaining $2^n-1$ points can be mapped.  Each one can be mapped to any spot but itself - thus it can be mapped to exactly $2^n-1$ possible spots.  So by the product rule, there are $(2^n-1)^{2^n-1}$ functions with exactly this particular fixed point and no other.  Now, there are $2^n$ possible choices for this particular fixed point, so by the sum rule, the total number of functions with exactly one fixed point is $2^n(2^n-1)^{2^n-1}$.}

\end{problemparts}
\end{problem}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% SOURCE:  FALL 00, PSET 8 #3
% TOPIC:  Inclusion-exclusion, product rule
\begin{problem}{\bf Counting strings}

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

\solution{
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:  \underline{00000}00011, 0\underline{00000}0011, 00\underline{00000}011 and 000\underline{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 \underline{000000}0011, 0\underline{000000}011, 00\underline{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$

}
\end{problem}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}





