HMMT 二月 2011 · TEAM1 赛 · 第 6 题

英文解析

6. [ 10 ] Prove that whenever the player must choose the side of a coin, the optimal strategy is to chooseheads if more coins have been determined tails than heads and to choose tails if more coins have beendetermined heads than tails.
   Solution: Let q ( k ) be the probability that, with n turns left and | H − T | = k , the player winsnplaying the optimal strategy. Note that k is always even. We prove by induction on n that with nturns 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 pickthe 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 leftin the game, since q ( k ) decreases when k = | H − T | increases, a larger value of | H − T | is nevern − 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 clearn nthat q (0) ≥ q (2) ≥ q (4). This completes the induction step.
   n n n