PUMaC 2008 · 团队赛 · 第 10 题
PUMaC 2008 — Team Round — Problem 10
题目详情
- (7 points) Consider the sequence s = (1 , 2008). Define new sequences s inductively by inserting 0 i the sum of each pair of adjacent terms in s between them—for instance, s = (1 , 2009 , 2008). i − 1 1 For some n , s has exactly one term that appears twice. Find this repeated term. n 2
解析
- Alex Lishkov is trying to guess sequence of 2009 random ternary digits (0, 1, or 2). After he guesses each digit, he finds out whether he was right or not. If he guesses incorrectly, and k was the correct answer, then an oracle tells him what the next k digits will be. Being Bulgarian, Lishkov plays to maximize the expected number of digits guessed correctly. Let P be the probability that n k Lishkov guesses the n th digit correctly. Find P . Write your answer in the form x + y Re( ρ ), 2009 where x and y are rational, ρ is complex, and k is a positive integer. ( ANS: We can prove by induction on the number of digits remaining that it is best for Alex to guess 0 when he doesn’t know the digit and give the correct answer when he does. The base cases where he has 3 or fewer digits left can easily be checked by hand. For the other cases, If he doesn’t know the answer, he guesses 0 because it maximizes the number of digits he will find out if he is wrong (except at the very last digit, where it doesn’t matter what he guesses). If he does know the answer, by guessing correctly and following the given strategy, he can guarantee himself an 19 expected value of at least and possibly some knowledge over the next three digits. By guessing 9 incorrecly, he finds out at most two digits, which, by the inductive hypothesis, guarantees him an expected value of 2 over those three digits, and no knowledge at the end. So it is strictly better to guess correctly. With this strategy, let a , b , and c be the probability that he gets the nth digit right given that n n n it is a 0, 1, or 2, respectively. He always gets zeroes right, so a = 1. He gets a 1 or a 2 only when n he knows it ahead of time, so it doesn’t matter whether it’s a 1 or a 2: b = c . The only time he n n can guess a 1 correctly is when he knows it, for which there are three mutually exclusive possibilities: He guessed incorrectly on a 1 or a 2 one step ago, or he guessed incorrectly on a 2 2 1 2 1 two steps ago. b = (1 − b ) + (1 − b ) = 1 − b − b . (Here we take b = 1 for n n − 1 n − 2 n − 1 n − 2 k 3 3 3 3 3 Team 2 1 k ≤ 0) So taking B = b − 1 / 2, we get B = − B − B . So, if r and r are the roots of n n n n − 1 n − 2 + − 3 3 √ − 1 ± − 2 2 1 1 1 1 2 n n x = − x − , then B = A r + A r . r = , and B = , B = − . So = A + A n + − ± 0 1 + −
- − 3 3 3 2 2 2 √ √ √ − 1+ − 2 − 1 − − 2 1 ± − 2 1 and − = A + A . So A = . Note that A = A and r = r , so
- − ± − + − + 2 3 3 4 ( ) n n n n n A r = A r . So, B = A r + A r = 2Re A r . So, − − n + − + − − + − + ( ) ( ) ( ) ( ) √ √ √ 2009 2008 1+ − 2 − 1+ − 2 − 1+ − 2 1 B = 2Re = − Re . So the probability of guessing 2009 4 3 2 3 ( ) ( ) √ 2008 − 1+ − 2 1 2 2 1 correctly on the 2009th digit is (1 + 2 b ) = (1 + B ) = − Re 2009 2009 3 3 3 3 3 CB: AM) 3