HMMT 二月 2004 · COMB 赛 · 第 10 题
HMMT February 2004 — COMB Round — Problem 10
题目详情
- In a game similar to three card monte, the dealer places three cards on the table: the queen of spades and two red cards. The cards are placed in a row, and the queen starts 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 two edge cards (so the configuration after the first move is either RRQ or QRR). What is the probability that, after 2004 moves, the center card is the queen? 2
解析
- In a game similar to three card monte, the dealer places three cards on the table: the queen of spades and two red cards. The cards are placed in a row, and the queen starts 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 two edge cards (so the configuration after the first move is either RRQ or QRR). What is the 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 prob- n ability that the queen is an edge card is 1 − p , and the probability that the queen n is the center card after move n + 1 is p = (1 − p ) / 2. This recursion allows us n +1 n 1 1 3 5 11 to calculate the first few values of p . We might then notice in 1 , 0 , , , , , , · · · , n 2 4 8 16 32 that 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 n formula p = + ( − ) , and one can then prove that this formula is in fact correct n 3 3 2 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, for example, or by using the fundamental theorem of linear recurrences, which ensures n that the solution is of the form p = a + b ( − 1 / 2) for some constants a, b . n 4