home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / rec / puzzles / 7427 < prev    next >
Encoding:
Text File  |  1992-11-21  |  8.9 KB  |  234 lines
  1. Newsgroups: rec.puzzles
  2. Path: sparky!uunet!elroy.jpl.nasa.gov!decwrl!cache.crc.ricoh.com!james
  3. From: james@crc.ricoh.com (James Allen)
  4. Subject: Re: 52-card Monty
  5. Message-ID: <1992Nov21.200205.1998@crc.ricoh.com>
  6. Sender: james@crc.ricoh.com (James Allen)
  7. Organization: RICOH California Research Center
  8. Date: Sat, 21 Nov 92 20:02:05 GMT
  9. Lines: 223
  10.  
  11.  
  12. I lost the original posting by Jim Saxe; here is the problem reworded:
  13.  
  14. ===============================================================
  15. Monty and Waldo play a game with N closed boxes.  Monty hides a
  16. dollar in one box; the others are empty.  Monty opens the empty boxes
  17. one by one.  When there are only two boxes left Waldo opens either box;
  18. he wins if it contains the dollar.  Prior to each of the N-2 box
  19. openings Waldo chooses one box and locks it, preventing Monty from opening
  20. it next.  That box is then unlocked and cannot be so locked twice in a row.
  21.  
  22. What are the optimal strategies for Monty and Waldo and what is the
  23. fair price for Waldo to pay to play the game?
  24. ===============================================================
  25.  
  26. I posted a poor effort on this earlier; let me try to make amends.
  27. The fair price for large N is $0.6321205588285576784; I will offer
  28. a proof along with optimal strategies.
  29.  
  30. Denote the game as G_N().  After (N-M) rounds of play, the game will have
  31. the same form as G_M().  Depending on the strategies each of the M boxes
  32. will have a probability p_i of containing the dollar.  Let Waldo lock
  33. the M'th box (renumbering the boxes if necessary).  Denote the game and
  34. Waldo's expected winnings in the game by
  35.         G_M(p_1, p_2, ..., p_M)                [1]
  36. In the solution we will need consider only the case
  37.         p_2 = p_3 = p_4 = ... = p_M
  38. We abbreviate this case by
  39.         G_M(b) = G_M(1 + b - Mb, b, b, b, b, ..., b)    [2]
  40. Of course the probabilities must sum to one; also since
  41. probabilities are not negative:
  42.         1 + b - Mb >= 0, or
  43.         0 <= b <= 1 / (M-1)                [3]
  44. In fact we will need to consider only the case
  45.         b >= 1 / M                    [4]
  46. We will refer to constraints [2] and [4] below.
  47.  
  48. Induction is used for one of the theorems, so we'd better solve G_2 and G_3
  49. for our basis.
  50.         G_2(p_1, p_2) = max (p_1, p_2)
  51.         G_3(p_1, p_2, p_3) = max (p_1 + p_2, p_3)
  52. since after Monty opens box #1, box #2 will have probability (p_1 + p_2)
  53. and vice versa.  With constraints [2], [4]
  54.         G_2(b) = G_2(1-b, b) = b
  55.         G_3(b) = G_3(1-2b, b, b) = 1 - b
  56.  
  57. The proof of Theorem 1 is based on the probability p_i that box #i
  58. contains the dollar.  (Of course this is Waldo's perceived probability:
  59. Monty's probability would be 0 or 1.)  It may seem wrong for Waldo to
  60. "forget" the game history and remember only the computed p_i.  For
  61. example he may have previously locked some but not all of the boxes
  62. and this fact is ignored except in the calculation of p_i.  Or Monty may
  63. have some higher level "plan" which mightn't seem to translate directly
  64. into probabilities.  But probability algebra obeys some simplifying
  65. linearity rules and, if Monty keeps a "poker face", the probability model
  66. is the only thing Waldo has to act on.
  67.  
  68. Especially paradoxical is the derivation of Waldo's p_i in his trivial
  69. strategy below: he can adopt inferior but "correct" p_i to simplify the
  70. analysis.
  71.  
  72. Theorem 1)
  73.     If   b >= 1/M   then
  74.     G_M(b) = G_[M-1]( (1-b) / (M-2) )            [5]
  75.  
  76. Proof)
  77.     We will show that Monty and Waldo each have a strategy in G_M(b) to
  78.     reduce the game to G_[M-1](b, q, q, ..., q) where q = (1-b) / (M-2)
  79.     and where the boxes have been renumbered so that box #1 was box #M
  80.     (the one Waldo locked) from the prior round and the new box #(M-1)
  81.     is the one Waldo locks next.  Note that if Monty indeed arranges
  82.     the probability mixture G_[M-1](b, q, q, q, q, ..., q) it won't
  83.     matter which box Waldo locks (Box #1 has the only non-equal
  84.     probability but Waldo cannot lock the same box twice in a row);
  85.     this is a typical property of "saddlepoint" strategy.
  86.  
  87.     The following applies to any G_M(p_1, p_2, p_3, ..., p_M).
  88.     To achieve the saddlepoint Monty need simply assure that each box
  89.     available for Waldo to lock has equal probability of containing
  90.     the dollar.  Using the numbering of G_M() let R(i,j) be the
  91.     joint probability that Box #i contains the dollar and Box #j
  92.     is opened by Monty in G_M().  Clearly,
  93.         R(i, j) >= 0
  94.         R(i, i) = 0            [ M equations ]
  95.         R(i, M) = 0, i < M        [ M-1 equations ]
  96.         sum_over_j R(i,j) = p_i        [ M equations ]
  97.     and to achieve constraint [2] (nearly all probabilities equal)
  98.     in G_[M-1],
  99.         R(1, j) = R(k, j)        [ M^2 - 5M + 6 equations]
  100.             for 1 < j,k < M and j != k
  101.         R(2, 1) = R(k, 1)        [ M-3 equations ]
  102.             for 2 < k < M
  103.     and to make G_[M-1] be independent of Monty's play
  104.         R(M, j)/R(1, j) = R(M, 2)/R(1, 2)  [ M-3 equations ]
  105.             for 2 < j < M
  106.         R(M, 2)/R(1, 2) = R(M, 1)/R(2, 1)  [ 1 equation ]
  107.  
  108.     Viewing R(i, j) as M*M unknowns, the above gives M*M linear
  109.     equations so there is a simple unique solution:
  110.  
  111.         R(i, j) = (1 - p_M) / (M - 2)  - p_j        [6]
  112.             for i,j < M and i != j
  113.         R(M, j) = p_M - p_j * p_M / (1 - p_M)        [7]
  114.             for j < M
  115.  
  116.     Monty can arrange for this solution if and only if R(i,j) >= 0;
  117.     as seen that is equivalent to
  118.         p_j * (M-2) + p_M <= 1  , from [6]
  119.         p_j + p_M <= 1          , from [7]
  120.  
  121.     When constraint [2] is satisfied (p_M = b and p_j = b or (1+b-Mb) )
  122.     this becomes,
  123.         b  <=  1 / (M - 1)
  124.         b  >=  (M - 3) / (M^2 - 3M + 1)  >=  1 / M
  125.     The first inequality was shown above and the second is somewhat
  126.     weaker than constraint [4] ( b >= 1/M ).  Hence Monty can transpose
  127.     G_M(b) into G_[M-1]( (1-b) / (M-2) ) whenever b >= 1/M and M >= 3.
  128.  
  129.     And of course
  130.         R(2,1) / sum R(i,1) = (1-b) / (M-2)
  131.     so after the next round the result is always
  132.         G_[M-1]( (1-b) / (M-2) )
  133.  
  134.     It should be easy to argue that this strategy is optimal for Monty,
  135.     but we want to derive Waldo's best strategy anyway and if it
  136.     guarantees the same value we know we're at the "saddlepoint".
  137.     If Waldo knows Monty has a non-optimal strategy he can take
  138.     advantage of it, but we will just derive a strategy good enough
  139.     to achieve the saddle-point value.
  140.  
  141.     In the game G_[M+1](p_1, p_2, ..., p_M, Q) Waldo has locked
  142.     box #(M+1) which has probability Q.  After Monty's next move
  143.     Waldo has the choice of (M-1) boxes; he should simply lock
  144.     each box with probability 1/(M-1).  That box will contain the
  145.     dollar with mean probability (1-Q)/(M-1).  The other (M-2)
  146.     available boxes must have the same average probability (1-Q)/(M-1)
  147.     since the box Waldo just unlocked still has probability Q.
  148.     Thus Waldo can take the view that he has constructed the game
  149.         G_M(Q, r, r, r, ..., r),  for r = (1-Q)/(M-1)
  150.     which is precisely the game Monty constructed with his optimal
  151.     strategy!
  152.  
  153.     In the above Waldo set his probability estimates to each be
  154.         p_2 = (p_2 + p_3 + ... + p_[M-1]) / (M - 2)
  155.         p_3 = (p_2 + p_3 + ... + p_[M-1]) / (M - 2)
  156.           et cetera
  157.     If Waldo "knows" more than this, he can pretend he doesn't!
  158.     For example he can ask Monty to secretly shuffle the boxes.
  159.  
  160.     Thus either player can reduce
  161.         G_M(b), b >= 1/M
  162.     to
  163.         G_[M-1]((1-b)/(M-2))
  164.     so this must be the saddlepoint.
  165.     Q.E.D.
  166.  
  167. Theorem 2)
  168.     If   b >= 1/M   then
  169.     G_M(b) = 1 - 1/2! + 1/3! - ... - (1-b)(-1)^M/(M-2)!
  170.         = sum (-1)^i/i! - (1-b)(-1)^M/(M-2)!        [8]
  171.     where the sum is over i = 1, 2, 3, ..., M-3
  172.  
  173. Proof)
  174.     The proof is by induction.  We know the theorem holds for M = 3
  175.     and we will assume it holds for (M-1).  Set
  176.         c = (1-b) / (M-2)
  177.     and note that since b <= 1/(M-1) from [3], we have
  178.         c = (1-b)/(M-2) >= (1 - 1/(M-1)) / (M-2)
  179.     or simply
  180.         c >= 1/(M-1)
  181.     so the condition of the inductive hypothesis is satisfied and
  182.         G_[M-1](c) = 1 - 1/2! + 1/3! - ... - (1-c)(-1)^M/(M-3)!
  183.     But from Theorem 1
  184.         G_M(b) = G_[M-1](c)
  185.     and from the definition of c,
  186.         c/(M-3)! = (1-b)/(M-2)!
  187.     which establishes the theorem.
  188.  
  189. Theorem 3)
  190.     G_M(1/M) = G_M(1/M, ..., 1/M) = 1 - 1/2! + 1/3! - ... -(-1)^M/M!
  191.  
  192. Proof)
  193.     This follows directly from Theorem 2 and the observation that
  194.         (1/M)/(M-2)! = 1/(M-1)! - 1/M!
  195.  
  196. For large M, G_M(1/M) approaches (1 - 1/e).  It will be a little bigger
  197. when M is odd and a little smaller when M is even.  I've appended the
  198. numeric values below.
  199.  
  200. Obligatory puzzle:  What property does this poem have?
  201.  
  202.         Ouija ionic, cameo aeons,
  203.         Usual ennui there.
  204.         Miaou.
  205.  
  206. James
  207.  
  208. % dc
  209. [[Solution for M =]Plb1+pdsb]sy
  210. 65k1sa1sblyx2sc[la1lc/-dsaplclyx*scla1lc/+dsaplclyx*sclzx]dszx
  211. Solution for M =2
  212. 0.50000000000000000000000000000000000000000000000000000000000000000
  213. Solution for M =3
  214. 0.66666666666666666666666666666666666666666666666666666666666666666
  215. Solution for M =4
  216. 0.62500000000000000000000000000000000000000000000000000000000000000
  217. Solution for M =5
  218. 0.63333333333333333333333333333333333333333333333333333333333333333
  219. Solution for M =6
  220. 0.63194444444444444444444444444444444444444444444444444444444444445
  221. Solution for M =7
  222. 0.63214285714285714285714285714285714285714285714285714285714285714
  223. Solution for M =8
  224. 0.63211805555555555555555555555555555555555555555555555555555555556
  225. Solution for M =9
  226. 0.63212081128747795414462081128747795414462081128747795414462081129
  227. Solution for M =10
  228. 0.63212053571428571428571428571428571428571428571428571428571428572
  229.     . . .
  230. Solution for M =52
  231. 0.63212055882855767840447622983853913255418886896823216549216319831
  232. ^C
  233.  
  234.