HMMT 二月 2013 · COMB 赛 · 第 10 题

10. Rosencrantz and Guildenstern each start with $2013 and are flipping a fair coin. When the coin comes 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 after n 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 sequences a n,a

• − of flips such that Rosencrantz first reaches a profit of a on exactly the n th flip. Let Q , Q , Q be the a a a sets such that after all 2013 flips Rosencrantz’ final profit is (respectively) greater than, less than, or equal to a . Then, 2013 ∑ Γ = P (max profit ≥ a ) a =1 2013 2013 ∑ ∑ = P ( E ) n,a a =1 n = a 2013 2013 ∑ ∑
• − = P ( E ∩ Q ) + P ( E ∩ Q ) + P ( E ∩ Q ) . n,a n,a n,a a a a a =1 n = a
• − + By symmetry, P ( E ∩ Q ) = P ( E ∩ Q ) because, for any sequence in E ∩ Q , we can reverse n,a n,a n,a a a a − all the flips after the n th flip to get a sequence in E ∩ Q , and vice-versa. n,a a Combinatorics Test 2013 2013 ∑ ∑

Furthermore, P ( E ∩ Q ) = P ( Q ) and P ( E ∩ Q ) = P ( Q ). n,a n,a a a a a n = a n = a So we have 2013 2013 ∑ ∑ ( ) + P (max profit ≥ a ) = P ( Q ) + 2 P ( Q ) . a a a =1 a =1 2013 ∑ 1 Since by symmetry P ( Q ) = P ( Q ) and we have an odd number of flips, we have P ( Q ) = . a − a a 2 a =1 ( ) 2013 ∑ 1 2013 + Also P ( Q ) = . a 2013 2 k 2014+ a k = ⌈ ⌉ 2 So the rest is just computation. We have: ( ) 2013 2013 ∑ ∑ 1 1 2013 Γ = + 2012 2 2 k 2014+ a a =1 k = ⌈ ⌉ 2 ( ) 2013 2 k − 2014 ∑ ∑ 1 1 2013 = + 2012 2 2 k a =1 k =1008 ( ) 2013 ∑ 1 1 2013 = + ( k + k − 2013 − 1) 2012 2 2 k k =1008 ( ) ( ) ( ) 2013 ∑ 1 1 2012 2012 2013 = + 2013 − 2013 − 2012 2 2 k − 1 k k k =1008 ( ) ( ) 2012 2013 2012 2013 − 2 + 1 1007 1007 = + 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