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

HMMT February 2013 — Guts Round — Problem 22

[ 14 ] Sherry and Val are playing a game. Sherry has a deck containing 2011 red cards and 2012 black cards, shuffled randomly. Sherry flips these cards over one at a time, and before she flips each card over, Val guesses whether it is red or black. If Val guesses correctly, she wins 1 dollar; otherwise, she loses 1 dollar. In addition, Val must guess red exactly 2011 times. If Val plays optimally, what is her expected profit from this game? ◦

解析

[ 14 ] Sherry and Val are playing a game. Sherry has a deck containing 2011 red cards and 2012 black cards, shuffled randomly. Sherry flips these cards over one at a time, and before she flips each card over, Val guesses whether it is red or black. If Val guesses correctly, she wins 1 dollar; otherwise, she loses 1 dollar. In addition, Val must guess red exactly 2011 times. If Val plays optimally, what is her expected profit from this game? 1 Answer: We will prove by induction on r + b that the expected profit for guessing if there 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 is r 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 is r 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 ) 1 Plugging in the our starting values gives an expected profit of . 4023 ◦