From: saxe@src.dec.com (Jim Saxe)
Subject: New Deal Puzzle
Followup-To: rec.puzzles
Summary: An original variant of the infamous Monty Hall puzzle
Organization: DEC Systems Research Center
Date: Fri, 13 Nov 92 03:08:11 GMT

In article <BxI7x2.772@mentor.cc.purdue.edu>, Dave Seaman
(ags@seaman.cc.purdue.edu) writes:
>In article <1992Nov9.193917.2948@lmpsbbs.comm.mot.com>  
>johnson@sleipnir.mnesouth.corp.mot.com ("Johnson") writes:
>> I finally realized it in the shower this morning.  The "balls in the  urn"
>> puzzle is the rec.puzzles version of the "Green Golf Ball Joke," right?
>  [...]
> I suppose this would be the wrong time to bring up the Monty Hall puzzle,  
> then.

At this point I can no longer resist the temptation to unleash on
rec.puzzles the following variant of the Monty Hall puzzle.  I have never
seen this variant discussed on the net.  I believe it is original with me.
It is not only more interesting mathematically than the standard version,
but more subtle logically as well, so be sure to read it carefully and
think twice before posting responses.  I'm sure lots of folks won't heed
this advice, but you can't say I didn't warn you.


        * * * * * THE ITERATED MONTY HALL PUZZLE * * * * *
(As if the standard version hadn't been iterated often enough. :-)

A card game is played according to the following rules by two players,
henceforth called the Dealer and the Guesser, using a standard 52-card
poker deck and a single poker chip.
1. The Dealer begins the game by shuffling the cards and dealing them
   individually face-down onto a table.  The Dealer looks at the face
   of each card before placing it on the table, but the Guesser is not
   allowed to see the faces of the cards as they are shuffled and dealt.
   In particular, the Dealer remembers, but does not reveal to the
   Guesser, the location of the ace of spades.
2. After the Dealer deals out the cards, the Guesser places the poker chip
   on the back of one of the cards.
3. After the Guesser first places the poker chip, play alternates between
   the Dealer and the Guesser as follows, until play ends as described in
   step 4:
   a. When it is the Dealer's turn, he chooses one face-down card that is
      neither the ace of spades nor the card under the poker chip, and
      turns that card face-up.  [Since the Dealer knows which card is the
      ace of spades, and since the rules guarantee that there will always
      be three or more cards still face down whenever it is the Dealer's
      turn, the Dealer is sure to be able to make a legal play.]  It is
      then the Guesser's turn to play.
   b. When it is the Guesser's turn, he chooses either to leave the poker
      chip where it is or to move it onto a different face-down card of his
      choosing.  [Note that the Guesser's options may include moving the
      chip back onto some card from which he removed it in an earlier turn,
      provided said card is still face-down.]  It is then the Dealer's turn
      to play, unless one of the ending conditions given in step 4 applies.
4. Play ends as soon as either or both of the following events occur:
   a. there are only two cards remaining face down after the Guesser's
      play, or
   b. the Guesser, on his turn to play, chooses not to move the poker chip.
   At this point the card under the poker chip is turned up.  If it is
   the ace of spades, the Guesser wins; otherwise, the Dealer wins.

What are the Dealer's and Guesser's optimal strategies and probabilities
of winning?
        * * * * * * * * * * * * * * * * * * * * * * * * * *

I've attempted to state this puzzle as clearly as I could.  If anyone
genuinely finds my description ambiguous, I'll be happy to provide
clarification.  On the other hand, I'm sure the majority of readers will
share my lack of interest in contrived points of "ambiguity" ("blah blah
glass table", "blah blah takes out his business card and blah") devised
by net.nit-pickers.

					--Jim Saxe <saxe@src.dec.com>