HMMT 二月 2010 · COMB 赛 · 第 9 题

英文解析

9. [ 7 ] Rosencrantz and Guildenstern are playing a game where they repeatedly flip coins. Rosencrantzwins if 1 heads followed by 2009 tails appears. Guildenstern wins if 2010 heads come in a row. Theywill flip coins until someone wins. What is the probability that Rosencrantz wins?
   2009
   2 − 1
   Answer: We can assume the first throw is heads (because neither player can win starting
   2008
   3 · 2 − 1
   from a string of only tails). Let x be the probability that Rosencrantz wins. Let y be the probabilitythat Rosencrantz wins after HT.
   Whenever there is a string of less than 2009 tails followed by a heads, the heads basically means thetwo are starting from the beginning, where Rosencrantz has probability x of winning.
   1 1
   We also know that x = y (1 − ). This is because from the initial heads there is a (1 − ) chance
   2009 2009
   2 2
   Rosencrantz doesn’t lose, and in this case the last two flips are HT, in which case Rosencrantz hasprobability y of winning.
   If the first two throws are HT, there is a chance Rosencrantz wins; otherwise, there is eventually 1
   2008
   a heads, and so we are back in the case of starting from a heads, which corresponds to x . Therefore,2
   1 1
   y = + x (1 − ). Putting this together with the previous equation, we get:
   2008 2008
   2 2
   ( ) ( )
   1 1 1
   x = + x (1 − ) 1 −
   2008 2008 2009
   2 2 2
   ( ) ( )
   2008 2009
   1+2 x − x 2 − 1 = ⇒ x =
   2008 2009
   2 2
   ( )
   4017 4017 2009 2008 2009 = ⇒ 2 x = x 2 − 2 − 2 + 1 + 2 − 1
   2009
   2 − 1 = ⇒ x = ,
   2009 2008
   2 +2 − 1
   2009 2009
   2 − 1 2 − 1
   so the answer is = .
   2009 2008 2008
   2 +2 − 1 3 · 2 − 1