HMMT 二月 2011 · TEAM1 赛 · 第 7 题
HMMT February 2011 — TEAM1 Round — Problem 7
题目详情
- [ 15 ] Let T denote the number of coins determined tails and H denote the number of coins determined heads at the end of the game. Let p ( k ) be the probability that | T − H | = k after a game with 4 m m coins, assuming that the player follows the optimal strategy outlined in problem 6. Clearly p ( k ) = 0 m if 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
解析
- [ 15 ] Let T denote the number of coins determined tails and H denote the number of coins determined heads at the end of the game. Let p ( k ) be the probability that | T − H | = k after a game with 4 m m coins, assuming that the player follows the optimal strategy outlined in problem 6. Clearly p ( k ) = 0 m if 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 to n n +1 n n n the probability that after n turns of the optimal strategy | H − T | = 0 (this is only true for k = 0). It follows that p (0) ≤ p (0). n +1 n 3 Second solution. When we play the game with n + 1 turns, there is a chance that after 1 turn 4 1 | H − T | = 0 and a chance that | H − T | = 2. 4 Now suppose we play the game, and get 2 tails and 1 heads on the first turn. Consider the following 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). n 3 1 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 probability of winning employing Strategy B does not exceed our probability of wining employing Strategy A. So p (0) ≥ p (0). n n +1