HMMT 二月 2013 · 冲刺赛 · 第 22 题

英文解析

22. [ 14 ] Sherry and Val are playing a game. Sherry has a deck containing 2011 red cards and 2012 blackcards, shuffled randomly. Sherry flips these cards over one at a time, and before she flips each cardover, Val guesses whether it is red or black. If Val guesses correctly, she wins 1 dollar; otherwise, sheloses 1 dollar. In addition, Val must guess red exactly 2011 times. If Val plays optimally, what is herexpected profit from this game?
    Answer: We will prove by induction on r + b that the expected profit for guessing if there 1
    4023
    2( r − b )
    are r red cards, b black cards, and where g guesses must be red, is equal to ( b − r ) + g . It is
    ( r + b )
    not difficult to check that this holds in the cases ( r, b, g ) = (1 , 0 , 0) , (0 , 1 , 0) , (1 , 0 , 1) , (0 , 1 , 1). Then,
    suppose that this is true as long as the number of cards is strictly less than r + b ; we will prove that it also holds true when there are r red and b blue cards.
    Let f ( r, b, g ) be her expected profit under these conditions. If she guesses red, her expected profit isr b 2( r − b )
    (1 + f ( r − 1 , b, g − 1)) + ( − 1 + f ( r, b − 1 , g − 1)) = ( b − r ) + g.
    r + b r + b ( r + b )
    Similarly, if she guesses black, her expected profit isr b 2( r − b )
    ( − 1 + f ( r − 1 , b, g )) + (1 + f ( r, b − 1 , g )) = ( b − r ) + g.
    r + b r + b ( r + b )
    Plugging in the our starting values gives an expected profit of .1
    4023
    °