\problemdata       % Takes 5 *mandatory* arguments
        {counting-23}             % latex-friendly label for the prob.
        {counting, inclusion-exclusion}  % The topic(s) of the problem content.
        {}               % Source (if known)
        {F99 PS8-4;} % Usage (list ones you are aware of).
        {Jack Kwok, S02}        % Last revision info (author, date).

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






