XXX OBM

Let $f(n)$ be the maximum number of prophetic words of length $n$. Obviously, $f(1)=2$, $f(2)=4$ and $f(3)=7$. Moreover, since there are exactly $2^3=8$ 3-letter words, each letter being $A$ or $E$, there is a forbidden substring $W$ of length three. So we can estimate $f(n)$ from above: in fact, each of the $n$-letter words belongs to exactly one of three sets: the set of words whose last letter is different from the last letter of $W$; the set of words whose penultimate letter is different from the second letter of $W$ and whose last letter is equal to the last letter of $W$; the set of words whose third-to-last letter is different from the first letter of $W$ and whose two last letters are equal to the two last letters of $W$. There are exactly $f(n-1)$, $f(n-2)$ and $f(n-3)$ words in these sets, respectively (notice the last letter, two last letters and three last letters of the words in the respective sets are determined and that they don't impose any restriction on the other letters). So $f(n)\le f(n-1)+f(n-2)+f(n-3)$. If $W=AAA$ it's not hard to prove that $f(n)$ is actually equal to $f(n-1)+f(n-2)+f(n-3)$. Just construct the words without a substring $AAA$ using all words that fit the description above. Substituting, we get $f(10)=504$ and now it remains to prove that there is a Zabrubic word satisfying the conditions of the problem, but this isn't hard, too: first, concatenate all 504 10-letter prophetic words, separate them with an $E$ and complete the word with $10000-504\cdot 11$ $E$'s. So the maximum number of 10-letter prophetic words is 504.