HMMT 二月 2018 · 冲刺赛 · 第 21 题
HMMT February 2018 — Guts Round — Problem 21
题目详情
- [ 12 ] You are the first lucky player to play in a slightly modified episode of Deal or No Deal! Initially, there are sixteen cases marked 1 through 16. The dollar amounts in the cases are the powers of 2 from 1 16 2 = 2 to 2 = 65536, in some random order. The game has eight turns. In each turn, you choose a case and claim it, without opening it. Afterwards, a random remaining case is opened and revealed to you, then removed from the game. At the end of the game, all eight of your cases are revealed and you win all of the money inside them. However, the hosts do not realize you have X-ray vision and can see the amount of money inside each case! What is the expected amount of money you will make, given that you play optimally?
解析
- [ 12 ] You are the first lucky player to play in a slightly modified episode of Deal or No Deal! Initially, there are sixteen cases marked 1 through 16. The dollar amounts in the cases are the powers of 2 from 1 16 2 = 2 to 2 = 65536, in some random order. The game has eight turns. In each turn, you choose a case and claim it, without opening it. Afterwards, a random remaining case is opened and revealed to you, then removed from the game. At the end of the game, all eight of your cases are revealed and you win all of the money inside them. However, the hosts do not realize you have X-ray vision and can see the amount of money inside each case! What is the expected amount of money you will make, given that you play optimally? Proposed by: Kevin Sun 18 7 · 2 + 4 1835012 Answer: (or ) 15 15 Firstly, note that it is always optimal for you to take the case with the largest amount of money. To prove this rigorously, consider a strategy where you don’t - then change the first move where you deviate to taking the maximal case. This can only increase your return. We calculate the probability f ( n, k ) that, if there are n cases numbered 1 , · · · , n in increasing order k − 1 of value, that you will take case k in the course of play. We claim that f ( n, k ) = and prove this n − 1 by induction on n/ 2 ( n always even). The base case n = 2 is true because you will always take case 2 and leave case 1. Then, for the general n , you will always take case n (so f ( n, n ) = 1). Afterward, n − 1 − k one case at random will be removed. When calculating f ( n, k ) there is a probability a case n − 1 numbered greater than k is removed, which inductively gives a probability f ( n − 2 , k ). Also, there k − 1 is a probability a case numbered less than k is removed, which inductively gives a probability n − 1 f ( n − 2 , k − 1). We can compute n − 1 − k k − 1 f ( n, k ) = f ( n − 2 , k ) + f ( n − 2 , k − 1) n − 1 n − 1 n − 1 − k k − 1 k − 1 k − 2 = · + n − 1 n − 3 n − 1 n − 3 k − 1 = ( n − 1 − k + k − 2) ( n − 1)( n − 3) k − 1 = n − 1 as desired. ∑ 16 i − 1 Finally, we must find f (16 , i )2 . Using standard procedures, we get i =1 16 15 ∑ ∑ i i − 1 i f (16 , i )2 = 2 15 i =1 i =1 15 ∑ i 17 i +1 = (2 − 2 ) 15 i =1 ( ) 15 ∑ 1 1 17 i +1 = (15)(2 ) − 2 15 15 i =1 1 17 17 = 2 − (2 − 4) 15 17 14 · 2 + 4 = 15