MathDB

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_n

be the probability that Lishkov guesses the nth digit correctly. Find

P_{2009}

. Write your answer in the form

x + yRe(\rho^k)

, where

x

and

y

are rational,

\rho

is complex, and

k

is a positive integer

Problem Statement