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

\parskip1.5ex
\parindent0pt

\begin{document}

\tutorial{tutorial9}{Problems for Tutorial 9}{November 25, 1996}

\section {More Games with Monty}

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)?\\ 

\section{Monty Goes Infinite}

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