Consider a sequence of words consisting of the letters "A" and "B". The first word in the sequence is "A", and the $k$-th word is obtained from the $(k-1)$-th word by the following operation: each "A" is replaced with "AAB", and each "B" is replaced with "A". It is easy to see that each word is the beginning of the next, thus forming an infinite sequence of letters: AABAAABAABAAABAAB...

a) At what position in this sequence will the 1000-th letter "A" appear?

b) Prove that this sequence is non-periodic.
Let the $n$-th word be denoted by $W_{n}$, and the specified operation by $f: W_{n+1}=f\left(W_{n}\right)$. Note that $f(U V)=f(U) f(V)$. We can assume that $W_{0}=$ B. Since $W_{2}=W_{1} W_{1} W_{0}, W_{n+1}=W_{n} W_{n} W_{n-1} \cdot\left(^{*}\right)$

Let $W_{n}$ contain $a_{n}$ letters A and $b_{n}$ letters B. From (*) it follows that $a_{n+1}=2 a_{n}+a_{n-1} \cdot \quad(* *)$

By condition $b_{n+1}=a_{n}$.

a) We compute sequentially: $a_{0}=0, a_{1}=1, a_{2}=2, a_{3}=5, a_{4}=12, a_{5}=29, a_{6}=70, a_{7}=169, a_{8}=408, a_{9}$ $=985$. Therefore, the 1000th letter will appear in the word $W_{10}=W_{9} W_{9} W_{8}=W_{9} W_{5} \ldots=W_{9} W_{4} W_{4} \ldots=$ $W_{9} W_{4} W_{3} W_{3} \ldots=W_{9} W_{4} W_{2} W_{2} \ldots$

The word $W_{9}$ contains $985+408=1393$ letters, the word $W_{4}-12+5=17$ letters, $W_{2} W_{2}=$ AAABAAB (the 1000th letter A is marked). Thus, the 1000th letter A is at the 1414th position ( $1393+17+4=1414$ ).

b) Suppose there exists $\lim _{n \rightarrow \infty} \frac{a_{n}}{b_{n}}=l$. Then $\lim _{n \rightarrow \infty} \frac{a_{n+1}}{a_{n}}=\lim _{n \rightarrow \infty} \frac{a_{n+1}}{b_{n+1}}=l$. Transitioning to the limit in the equality obtained from (**) $\frac{a_{n+1}}{a_{n}}=2+\frac{a_{n-1}}{a_{n}}$, we see that $l$ is a root of the equation $l=2+$ $1 / l$, which is irrational.

Suppose our sequence is periodic, the pre-period contains $c$ letters, the period contains $a$ letters A, $b$ letters B, and fits $k_{n}$ times in the word $W_{n}$. Then $k_{n} a \leq a_{n}<c+\left(k_{n}+1\right) a, k_{n} b \leq b_{n}<c+\left(k_{n}+1\right) b$, hence, $\frac{k_{n}}{k_{n}+\frac{b+c}{b}} \cdot \frac{a}{b}<\frac{a_{n}}{b_{n}}<\frac{k_{n}+\frac{a+c}{a}}{k_{n}} \cdot \frac{a}{b}$. This implies that $\frac{a_{n}}{b_{n}}$ tends to a rational number $\frac{a}{b}$. Contradiction.

## Answer

a) At the 1414th position.