HMMT 二月 2011 · TEAM1 赛 · 第 7 题

英文解析

7. [ 15 ] Let T denote the number of coins determined tails and H denote the number of coins determinedheads at the end of the game. Let p ( k ) be the probability that | T − H | = k after a game with 4 mcoins, assuming that the player follows the optimal strategy outlined in problem 6. Clearly p ( k ) = 0 mmif k is an odd integer, so we need only consider the case when k is an even integer. (By definition,
   p (0) = 1 and p ( k ) = 0 for k ≥ 1). Prove that p (0) ≥ p (0) for all nonnegative integers m .
   0 0 m m +1
   Solution:
   3 1
   First solution. Using the sequences q ( k ) defined above, it is clear that q (0) = q (0) + q (2) ≤
   n n +1 n n
   4 4
   q (0). So q (0) ≤ q (0). Now note that for k = 0, p ( k ) = q ( k ), because they are both equal ton n +1 n n nthe probability that after n turns of the optimal strategy | H − T | = 0 (this is only true for k = 0). Itfollows that p (0) ≤ p (0).
   n +1 n
   Second solution. When we play the game with n + 1 turns, there is a chance that after 1 turn 3
   | H − T | = 0 and a chance that | H − T | = 2.14
   Now suppose we play the game, and get 2 tails and 1 heads on the first turn. Consider the following 4
   two strategies for the rest of the game.
   Strategy A: We pick the fourth coin to be heads, and play the optimal strategy for the other n turns.
   Our probability of winning is p (0).
   3 1 n
   Strategy B: We pick the fourth coin to be heads with probability and tails with probability , then
   4 4
   proceed with the optimal strategy for the rest of the game. This is equivalent to throwing the first 3
   coins over again and applying the optimal strategy. Our probability of winning is p (0).
   n +1
   Team Round A
   By the theorem in the previous problem, Strategy A is the optimal strategy, and thus our probabilityof winning employing Strategy B does not exceed our probability of wining employing Strategy A. Sop (0) ≥ p (0).
   n n +1