HMMT 二月 2004 · COMB 赛 · 第 10 题

英文解析

10. In a game similar to three card monte, the dealer places three cards on the table: thequeen of spades and two red cards. The cards are placed in a row, and the queenstarts in the center; the card configuration is thus RQR. The dealer proceeds to move.
    With each move, the dealer randomly switches the center card with one of the twoedge cards (so the configuration after the first move is either RRQ or QRR). What isthe probability that, after 2004 moves, the center card is the queen?
    2003
    Solution: 1 / 3 + 1 / (3 · 2 )
    If the probability that the queen is the center card after move n is p , then the probnability that the queen is an edge card is 1 − p , and the probability that the queennis the center card after move n + 1 is p = (1 − p ) / 2. This recursion allows usn +1 n
    1 1 3 5 11
    to calculate the first few values of p . We might then notice in 1 , 0 , , , , , , · · · ,
    2 4 8 16 32 nthat the value of each fraction is close to 1 / 3, and getting closer for larger n . In fact
    2 1 1 1 1 1
    subtracting 1 / 3 from each fraction yields , − , , − , , − , · · · . This suggests the
    3 3 6 12 24 48
    1 2 1 nformula p = + ( − ) , and one can then prove that this formula is in fact correct
    3 3 2 n
    1 2 1 1 1
    2004
    by induction. Thus, p (2004) = + ( − ) = + .
    2003
    3 3 2 3 3 · 2
    The recurrence can also be solved without guessing — by generating functions, forexample, or by using the fundamental theorem of linear recurrences, which ensuresthat the solution is of the form p = a + b ( − 1 / 2) for some constants a, b .nn 4