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

\parskip1.5ex
\parindent0pt

\begin{document}

\tutorial{tutorial10}{Problems 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.


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

