HMMT 二月 2011 · 冲刺赛 · 第 11 题

英文解析

11. [ 8 ] Rosencrantz and Guildenstern play a game in which they repeatedly flip a fair coin. Let a = 4,
    a = 3, and a = a + a for all n ≥ 3. On the n th flip, if the coin is heads, Rosencrantz pays 1
    2 n n − 1 n − 2
    Guildenstern a dollars, and, if the coin is tails, Guildenstern pays Rosencrantz a dollars. If playn ncontinues for 2010 turns, what is the probability that Rosencrantz ends up with more money than hestarted with?
    1 1
    Answer: −
    1341
    2 2
    Since Rosencrantz and Guildenstern have an equal chance of winning each toss, both have the sameprobability of ending up with a positive amount of money. Let x denote the probability that they both
    1 − xend up with zero dollars. We wish to find .
    We have x is equal to the probability that 2
    s := i a + i a + · · · i a = 0 ,
    2010 1 1 2 2 2010 2010
    where i has an equal probability of being either 1 or − 1.
    We claim that s = 0 if and only if i = − i = − i for all n ≤ 670. We start with then
    2010 3 n 3 n − 1 3 n − 2
    following lemma.
    n − 3
    ∑
    Lemma. We have a > a for all n ≥ 4.
    n kk =1
    Proof: For the case n = 4, a = a + a = 2 a + a > a . In case n > 4, we have
    4 3 2 2 1 1
    n − 4 n − 3 n − 3
    ∑ ∑ ∑
    a = a + a > a + a = a + a > a .
    n n − 2 n − 1 n − 2 k n − 4 k kk =1 k =1 k =1
    It suffices to show that s = 0 only if i = − i = − i for all k ≤ n . The triangle inequality
    3 n 3 k 3 k − 1 3 k − 2
    implies the following:
    ∣ ∣
    ∣ ∣ ∣ ∣
    ∣ ∣
    ∣ ∣ ∣ ∣
    0 ≤ i a + s − i a + i a ≤ | s | = 0
    ∣ ∣
    3 n − 2 3 n − 2 3 n − 3 3 n − 1 3 n − 1 3 n 3 n 3 n
    ∣ ∣
    ∣ ∣ ∣ ∣
    ∣ ∣
    ∣ ∣ ∣ ∣
    0 ≤ i a + s − i a + i a ≤ | s | = 0
    ∣ ∣
    3 n − 1 3 n − 1 3 n − 3 3 n − 2 3 n − 2 3 n 3 n 3 n
    Guts Round
    By the lemma, we have
    3 n − 3
    ∑
    a + a < a + a < a + a
    3 n − 2 k 3 n − 2 3 n 3 n − 1 3 nk =1
    3 n − 3
    ∑
    a + a < a + a + a + a = a + a
    3 n − 1 k 3 n − 1 3 n − 3 3 n − 4 3 n − 2 3 n − 2 3 nk =1
    ∣ ∣ ∣
    3 n − 3
    ∑
    ∣ ∣ ∣ ∣ ∣
    ∣ ∣ ∣ ∣ ∣
    i = i implies a + a < i a + i a and i = i implies a +
    3 n 3 n − 1 3 n − 2 k 3 n − 1 3 n − 1 3 n 3 n 3 n 3 n − 2 3 n − 1
    ∣ ∣ ∣
    k =1
    ∣
    3 n − 3
    ∑
    ∣ ∣ ∣
    ∣ ∣ ∣
    a < i a + i a , which are both contradictions; therefore, we must have i = − ik 3 n − 2 3 n − 2 3 n 3 n 3 n 3 n − 1
    ∣
    k =1
    and i = − i .
    3 n 3 n − 2
    ( )
    1 1 1 1 − x 1 1670
    The probability that i = − i = − i is , so x = = , and = − .
    3 n 3 n − 1 3 n − 2 1340 1341
    4 4 2 2 2 2