HMMT 二月 2011 · TEAM1 赛 · 第 6 题
HMMT February 2011 — TEAM1 Round — Problem 6
题目详情
- [ 10 ] Prove that whenever the player must choose the side of a coin, the optimal strategy is to choose heads if more coins have been determined tails than heads and to choose tails if more coins have been determined heads than tails.
解析
- [ 10 ] Prove that whenever the player must choose the side of a coin, the optimal strategy is to choose heads if more coins have been determined tails than heads and to choose tails if more coins have been determined heads than tails. Solution: Let q ( k ) be the probability that, with n turns left and | H − T | = k , the player wins n playing the optimal strategy. Note that k is always even. We prove by induction on n that with n turns left in the game, this is the optimal strategy, and that q ( k ) ≥ q ( k + 2). n n Base Case: n = 1, if there is one more turn in the game, then clearly if we flip 3 coins and get | H − T | ≥ 3 then our play does not matter. If we get | H − T | = 1 then the optimal strategy is to pick the side so that | H − T | = 0. So this is the optimal strategy. 3 1 1 Now q (0) = , q (2) = , q (4) = and q (2 k ) = 0 for k ≥ 3. So q ( k ) ≥ q ( k + 2) for all k . 1 1 1 1 1 1 4 2 8 Induction Step: Assume the induction hypothesis for n − 1 turns left in the game. With n turns left in the game, since q ( k ) decreases when k = | H − T | increases, a larger value of | H − T | is never n − 1 more desirable. So picking the side of the coin that minimizes | H − T | is the optimal strategy. 1 3 3 1 Now for k ≥ 2, q (2 k ) = q (2 k − 4) + q (2 k − 2) + q (2 k ) + q (2 k + 2), and it is clear, n n − 1 n − 1 n − 1 n − 1 8 8 8 8 by the induction hypothesis that q (2 k ) ≥ q (2 k + 2) for all k ≥ 2. Similar computations make it clear n n that q (0) ≥ q (2) ≥ q (4). This completes the induction step. n n n