HMMT 二月 2013 · COMB 赛 · 第 10 题

英文解析

10. Rosencrantz and Guildenstern each start with $2013 and are flipping a fair coin. When the coincomes up heads Rosencrantz pays Guildenstern $1 and when the coin comes up tails Guildenstern pays
    Rosencrantz $1. Let f ( n ) be the number of dollars Rosencrantz is ahead of his starting amount aftern flips. Compute the expected value of max { f (0) , f (1) , f (2) , . . . , f (2013) } .
    ∞
    2013
    ∑
    (1007)
    ( ) − 1 1006
    Answer: + We want to calculate Γ = i · P (max profit= i ), where we consider
    2012
    2 2
    i =0
    the maximum profit Rosencrantz has at any point over the first 2013 coin flips. By summation by
    2013
    ∑
    parts this is equal to P (max profit ≥ a ).
    a =1
    Let p be the probability that Rosencrantz’ max profit is at least a and let E be the set of sequencesa n,a + −
    of flips such that Rosencrantz first reaches a profit of a on exactly the n th flip. Let Q , Q , Q be theaa asets such that after all 2013 flips Rosencrantz’ final profit is (respectively) greater than, less than, orequal to a .
    Then,
    2013
    ∑
    Γ = P (max profit ≥ a )
    a =1
    2013 2013
    ∑ ∑
    = P ( E )
    n,aa =1 n = a
    2013 2013
    ∑ ∑

• −
  = P ( E ∩ Q ) + P ( E ∩ Q ) + P ( E ∩ Q ) .
  n,a n,a n,a aa aa =1 n = a + − +
  By symmetry, P ( E ∩ Q ) = P ( E ∩ Q ) because, for any sequence in E ∩ Q , we can reversen,a n,a n,aa a aall the flips after the n th flip to get a sequence in E ∩ Q , and vice-versa.−
  n,aa
  Combinatorics Test
  2013 2013
  ∑ ∑

Furthermore, P ( E ∩ Q ) = P ( Q ) and P ( E ∩ Q ) = P ( Q ).
n,a n,a a aa an = a n = a
So we have
2013 2013
∑ ∑
( )
P (max profit ≥ a ) = P ( Q ) + 2 P ( Q ) .+
a =1 a =1 aa
2013
∑
Since by symmetry P ( Q ) = P ( Q ) and we have an odd number of flips, we have P ( Q ) = .1
a − a aa =12
( )
2013
∑
1 2013
Also P ( Q ) = .+
2013 a
2 k
2014+ ak =
⌈ ⌉
So the rest is just computation. We have:2
( )
2013 2013
∑ ∑
1 1 2013
Γ = +
2012
2 2 k
2014+ aa =1
k =
⌈ ⌉
( )2
2013 2 k − 2014
∑ ∑
1 1 2013 = +
2012
2 2 ka =1
k =1008
( )
2013
∑
1 1 2013 = + ( k + k − 2013 − 1)
2012
2 2 kk =1008
( ) ( ) ( )
2013
∑
1 1 2012 2012 2013 = + 2013 − 2013 −
2012
2 2 k − 1 k kk =1008
( ) ( )
2012 2013
2012
2013 − 2 +
1007 10071 = +
2012
2 2
( )
2013
(1007) − 1
1006 = + .
2012
2 2
2013
(1007)
( ) − 1 1006
So the answer is + (for reference, approximately 35 . 3).
2012
2 2
Combinatorics Test