
\problemdata     
{S01-PS7-2}           
{Inclusion-exclusion, sets, basic permutations}              
{} 		
{S01-PS7}
{S01 Karger}


      
\begin{problem}

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 - ``illegal" permutations (containing ``fail" or ``drop"). The total number of permutations of the letters is $10!$. According to the inclusion-exclusion principle, the number of permutations containing either ``fail" or ``drop" is: 

permutations containing "fail" - permutations containing "drop" + permutations
containing "fail" and "drop".

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, \fbox{fail}\} which is $7!$.  A similar argument holds for the number
of permutations with "drop", so these are also $7!$.

The number of permutations with both "fail" and "drop" is
the same as finding the number of permutations of the following 4
elements \{ \fbox{drop}, \fbox{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 Stirling'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 Stirling's approximation this is
approximately $9.32\times 10^{157}$.

Notice that the problem could also be stated as: ``find the number of \emph{bijections} from the set of names to the set of passwords.
}

\ppart When trying to break into the system, Bob doesn't have to
submit an entire matching of the 100 user names with the 100 passwords
at the same time. Instead, he can try individual pairs of names and
passwords, i.e., he can try to login as any of the 100 users with any
of the 100 passwords and see if the login attempt is successful.

Describe a (good) strategy that Bob can use to completely determine
the pairing of names with passwords. How many login attempts does Bob
need to determine the entire matching in the worst case?

\solution{
Bob uses the following strategy: First he figures out the password for
the first name on the list. In the \emph{worst} case, he'll have to try 99 passwords (if he fails the first 99 times, he knows that the last password is correct so he doesn't need to try it). Then, for the second name, there are 99 possible passwords so he needs to try 98 of them in the worst case, and so on. For the 99th password there are 2 possible choices, so he needs to try 1 in the worst case, and he always gets the 100th password for free. 

So, in the worst case, he needs $99 + 98 + 97 + \cdots + 1 = 4,950$ trials.}

\eparts            
\end{problem}
