返回题库

HMMT 二月 2018 · 冲刺赛 · 第 21 题

HMMT February 2018 — Guts Round — Problem 21

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. [ 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 acase and claim it, without opening it. Afterwards, a random remaining case is opened and revealed toyou, 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 eachcase! What is the expected amount of money you will make, given that you play optimally?
解析

英文解析

  1. [ 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 acase and claim it, without opening it. Afterwards, a random remaining case is opened and revealed toyou, 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 eachcase! What is the expected amount of money you will make, given that you play optimally?
    Proposed by: Kevin Sun
    7 · 2 + 4 183501218
    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 youdeviate 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 orderk − 1
    of value, that you will take case k in the course of play. We claim that f ( n, k ) = and prove thisn − 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 − kone case at random will be removed. When calculating f ( n, k ) there is a probability a casen − 1
    numbered greater than k is removed, which inductively gives a probability f ( n − 2 , k ). Also, therek − 1
    is a probability a case numbered less than k is removed, which inductively gives a probabilityn − 1
    f ( n − 2 , k − 1). We can computen − 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.
    ∑
    i − 116
    Finally, we must find f (16 , i )2 . Using standard procedures, we geti =1
    16 15
    ∑ ∑
    i − 1 iif (16 , i )2 = 2
    i =1 i =115
    ∑15
    17 i +1 i = (2 − 2 )
    i =115
    ( )
    ∑15
    1 1
    17 i +1 = (15)(2 ) − 2
    15 15
    i =1
    17 171 = 2 − (2 − 4)
    1715
    14 · 2 + 4
    15=