\documentstyle[12pt,twoside,amsfonts,amstex]{article}
\input{macros-course-tutorials}

\parskip1.5ex
\parindent0pt

\begin{document}

\tutorial{tutorial10}{Solutions for Tutorial 10}{April 28, 1997}

\begin{problems}

\problem
$N$ people leave their hats in a coatroom. On the way out the person
in charge of the coatroom hands their hats back to them in an arbitrary
order. Use inclusion-exclusion to count the total number of ways in
which the hats can be handed back to them such that no person gets
his/her own hat back.

First, start with the number of ways of giving back all the hats: $n!$.
Now, what we want to do is to subtract all the ways of getting
exactly $i=1, 2 \ldots n$ hats back correctly, but we can't easily determine
these numbers easily, so let's subtract ${ n \choose 1} \cdot (n-1)!$ which is
the number of ways to set one hat correctly in it's place times the
number of ways to rearrange the  rest of the hats.

$n! - { n \choose 1} \cdot (n-1)!$

Now unfortunately we've overcounted the number of ways of giving back
exactly 2, 3 ... n  hats correctly.  When we set one hat to be correct and rearranged
the rest, we double count depending on which of the two hats were set
correctly.  For example, we set hat 1 correctly, but have a permutation where
only hat 1 and 4 are correct.  Later, we set hat 4 correctly, and again
come across this permutation with hat 4 and 1 correct.  We have overcounted.  
In fact, for any $i$ hats set correctly, we overcounted $i$
times--once for each of the times we chose one of the $i$ hats to be correct
and then rearranged the rest.

Well, to compensate for the doubled counting of exactly 2 correct, let's add
${ n \choose 2} \cdot (n-2)!$--the number of ways of choosing exactly
two correct and rearranging the rest.

If we keep up this pattern we get:

\[ n! - { n \choose 1} \cdot (n-1)! +{ n \choose 2} \cdot (n-2)! + \ldots
{ n \choose n} \cdot (n-n)!  = \sum_{i=0}^n { n \choose i} \cdot (n-i)!
\]

Notice that for the $i$th term, we overcount exactly $k$ hats placed correctly
${k \choose i }$ times for $k \geq i$.

If we look at how many times we add (or subtract) exactly $k$ hats correctly, 
(including in our initial count of how many ways there are of returning
all the hats ($n!$)) we get:

\[
\sum_{i=0}^k (-1)^{i} { k \choose i} = (1 - 1)^{k} =0
\]

So we have summed up 0 instances of the total number of ways to return
exactly $k \geq 1$ hats correctly. Which leaves us with all the hats
returned incorrectly.

\[ \sum_{i=0}^n { n \choose i} \cdot (n-i)! \]

%\problem 
%
%Consider playing the {\it Lets Make a Deal}, where there are three prizes:
%a ``Gift Certificate'' from Toscanini, a ``Nerd Pocket Protector'', and a 
%``Nerd Pride Button''. Your goal is to win the gift certificate. 
%
%\bparts
%\ppart
%Suppose you (the contestant) happen
%to know that Carol always reveals the ``Nerd Pocket Protector'', if you 
%did not choose the box covering it. \\
%Does this additional information change the odds of winning for you? 
%Is there a better strategy? By how much (if any) does this information
%increase your chances of winning?
%\ppart
%You are playing according to the original assumptions, but before
%you make your initial choice, you happen to see Carol placing a 
%``Nerd Pride Button'' underneath Box~1.  What should you do to try to win 
%the prize (the ice cream)?  What is the probability that you win?
%\eparts
%
%% \problem
%% Consider playing the {\it Lets Make a Deal} game with the following
%% additional information.
%% \bparts
%% \ppart
%% Suppose Monty is determined to make you lose. 
%% In particular, if you initially choose a losing door, 
%% he decides to end the game right there, opening your door to reveal
%% the nerd item you have ``won'', never giving you the chance to switch doors.
%% What is the probability of winning if you play the ``don't-switch strategy''?  
%% What if you play the ``switch strategy''?
%% \ppart
%% Now suppose that if you initially choose a loosing door, Monty decides to end
%% the game with (known) probability $p$.  What is your optimal strategy for
%% each value of $p$?  What is the corresponding probability of winning?
%% \ppart Suppose the scenario is the same as in the previous part, but you are 
%% using  randomized strategy.  In particular, you decide to switch with 
%% probability $p_s$. Can you do better?  What should the value of $p_s$ be 
%% for every value of $p$?
%% \eparts
%% 
%% \newpage
%% 
%% %\problem
%% %Let's play another game. Monty shows you two cards, each lying face
%% %down on a table. He tells you there's a number from the range
%% %$\{1,\ldots, n\}$ written on the face of each. You pick a card, and
%% %Monty shows you the number written on it.  He now tells you that you
%% %can either choose to stay with that number, or switch to the number
%% %written on the other card. You {\em win} if the number you end up with
%% %is the biggest of the two (that is, if either you originally picked
%% %the biggest and decided to stay, or if you originally picked the
%% %smallest and decided to switch). A randomized strategy for this game
%% %is a function that, for each number $i$, assigns a probability $p_i$
%% %of switching {\em given} that the first card you picked was $i$. Can
%% %you find a randomized strategy for playing this game that gives you
%% %more than an even chance of winning, given that Monty {\em knows} what
%% %strategy you are using (and thus can pick the numbers he presents to
%% %you in a malicious way)?\\ 
%% %
%% %\problem
%% %\begin{itemize}
%% %\item Now suppose the numbers from the problem above are drawn from
%% %  the set of natural numbers, $\naturals$. Can you find a strategy for
%% %  playing this game that gives you more than an even chance of
%% %  winning?
%% %\item Now suppose the numbers from the problem above are drawn from
%% %  the set of integers, $\integers$. Can you find a strategy for
%% %  playing this game that gives you more than an even chance of
%% %  winning?
%% %\end{itemize}
%
\end{problems}

\end{document}
%
