\problemdata                                                             
        {counting-24} % latex-friendly label for the prob.
        {Counting, Permutations} % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S02 cp7W; S00 PS7} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem} Jack is manager of the MIT Chess Club.  After a long and
grueling match, the players have gone home, leaving Jack to put the
players' unlabeled chess sets back in their lockers.

\begin{problemparts}

\problempart If there are $n$ players/lockers and $n$ chess sets, how
many ways could Jack place chess sets in lockers such that there is
exactly one chess set in each locker, disregarding the correctness of
such placement?

\solution{$n!$. 
  Since there are $n$ chess sets and $n$ lockers, there are $n$ chess sets
  that can be place in the first locker.  $n-1$ chess sets to choose from for the second 
  locker, $n-2$ chess sets for the third... etc.  Therefore there are $n!$ possible ways.       
  }

% \problempart 
% This begs the question: how many ways can Jack 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}$ we will use Stirling's approximation, $D_{10}\approx$
%   something =) }

\problempart 
Say Jack recognizes Tina's chess set, so he can place that
one correctly, but recognizes none of the other chess sets.  How many
possible ways can Jack place chess sets in lockers assuming he at
least gets Tina's right?

\solution{The answer is $(n-1)!$.  After placing Tina's chess set in the 
right locker, we are left with $(n-1)$ chess sets and $(n-1)$ lockers. Thus there are
$(n-1)!$ ways to place the remaining sets. 
}

\problempart 
However Jack really resents Tina's chess prowess, and decides to get
even by putting Tina's chess set in another student's locker.  How
many ways can he place chess sets in lockers assuming he does not
place Tina's chess set into Tina's locker?

\solution{The answer is the total number of ways to
  place the chess sets minus the number of ways that place Tina's chess set
  correctly. This gives $n! - (n-1)!$.
}
\problempart Jack suddenly finds two more unlabelled chess sets. Now
he has $n+2$ chess sets and only $n$ lockers. He's given up worrying
about Tina now. How many ways can he place $n+2$ chess sets in $n$
lockers?

\solution{ 
The answer is $P(n+2,n)$.  There are $n+2$ chess sets to choose $n$ sets from and 
to be placed into $n$ lockers.  
$P(n+2,n)$ is the number of ways to permute $n$ objects out of $n+2$ objects which
corresponds exactly to the situation here.
}

\problempart Its been a late night, Jack gives up and goes home. Later
on Tina comes by and decides that she will put the away the $n$ chess
sets and discard the two extra checkers sets (Jack was tired). After
putting her own set into her locker
, she notices that Christos and
Ashish actually wrote their names on their sets. For reasons known
only to Tina, she decides to place the all the sets in the lockers
without regard for who they belongs to, so long as Christos's and
Ashish's sets are not in adjacent lockers (assume the lockers are
arranged in a line and tina's locker is the firstr on the line). 
How many ways can she place the chess sets?

\solution{ The
number of ways in which Christos's set and Ashish's set are next to each other can be 
counted by treating Christos-Ashish as one unit. Tina has n-1 chess sets (all minus her
own set which was put inside her locker) to start rearrange with. 
Treating Christos-Ashish as a unit she now has n-2 sets to
rearrange. The total number of rearrangements where Ashish is right before Christos is (n-2)! and 
similarly, the total number of rearrangements where Christos is right before Ashish is (n-2)!.
Adding these two numbers, the total number of rearrangements where Ashish and Christos are 
adjacent is  2.(n-2)!. 
Subtracting the total number of arrangements from that gives the number of
arrangements where Christos and Ashish are not adjacent :  (n-1)! - 2.(n-2)!.}


% \problempart 
% Jack has a sudden change of heart and decides to be nice to
% Tina.  At this time, he also realizes that Christos has
% conscientiously written his name on the outside of his chess set, so
% now Jack knows the correct destinations of two chess sets.  How many
% arrangements are there now?

% \solution{As in part (b), we can simply create an injective function
%   on the remaining elements, which gives us $(n-2)!$.}

% \problempart Say Jack is taking mind-altering drugs and has again
% changed his mind about Tina.  Still being able to discern Tina's
% and Christos's chess sets---but wishing to ill-place Tina's---Jack
% can place chess sets in lockers in how many ways?

% \solution{Assign 1 to Tina's locker and chess set, and 2 to
%   Christos's locker and chess set.  We know that $|A\cap
%   B|=|A|-|A\cap\bar B|$, so if we take $A$ to be the set of functions
%   with $f(2)=2$ and $B$ to be the set of functions with $f(1)\not=1$,
%   then we know $|A|$ and $|A\cap\bar B|$, the latter of which is the
%   solution to the previous part; so, the answer is
%   $(n-1)!-(n-2)!=(n-2)(n-2)!$.  }


\end{problemparts}
\end{problem}

                                 