PUMaC 2008 · 团队赛 · 第 9 题

PUMaC 2008 — Team Round — Problem 9

(7 points) 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.

解析

Suppose that the roots of the quadratic x + ax + b are α and β . Then α and β are the roots of 2 some quadratic x + cx + d. Find c in terms of a and b . 3 ( ANS: a − 3 ab . 3 3 We know that a = − α − β and b = αβ . We wish to find c = − α − β . Now observe 3 3 2 2 2 2 3 c = − α − β = − ( α + β )( α − αβ + β ) = − ( α + β )(( α + β ) − 3 αβ ) = − ( − a )(( − a ) − 3 b ) = a − 3 ab . CB: NS, JP, ACH, IAF)