9.90 To color some of the squares in a $2 \times n$ strip of squares such that no $2 \times 2$ square is completely colored, let $P_{n}$ denote the number of different coloring methods that satisfy this condition. Prove that $P_{1989}$ is divisible by 3, and find the highest power of 3 that divides $P_{1989}$.
Let $a_{n}$ denote the number of different coloring methods for a $2 \times n$ strip that satisfy the conditions of the problem and have the last two cells colored.
Let $b_{n}$ denote the number of coloring methods where the last two cells are not both colored, then we have
$$
P_{n}=a_{n}+b_{n}.
$$

By the conditions of the problem, no $2 \times 2$ block of four cells can be all colored, so we have the recurrence relation
$$
a_{n}=b_{n-1}.
$$

Also,
$$
b_{n}=a_{n-1}+a_{n-1}+a_{n-1}+b_{n-1}+b_{n-1}+b_{n-1},
$$

which simplifies to
$$
b_{n}=3\left(a_{n-1}+b_{n-1}\right).
$$

From (2) and (3), we get
$$
a_{n}=b_{n-1}=3\left(a_{n-2}+b_{n-2}\right),
$$

so
$$
\begin{array}{l}
a_{n}=3\left(a_{n-2}+a_{n-1}\right) \\
b_{n}=3\left(b_{n-2}+b_{n-1}\right).
\end{array}
$$

From (1), (4), and (5), we get
$$
\begin{array}{l}
P_{n}=3\left(a_{n-1}+a_{n-2}\right)+3\left(b_{n-1}+b_{n-2}\right) \\
P_{n}=3\left(P_{n-1}+P_{n-2}\right).
\end{array}
$$

It is easy to see that $P_{1}=4, P_{2}=15$.
Thus, by (6), we can recursively compute the value of $P_{n}$.
For $n \geqslant 3$, $P_{n}$ is always a multiple of 3.
In particular,
$$
3 \mid P_{1989}
$$

Because
$$
\begin{array}{l}
P_{1}=4, P_{2}=15, P_{3}=3 \times 19 \\
P_{4}=3(3 \times 19+15)=3^{2}(19+5)
\end{array}
$$

Thus, $3 \times P_{1}, 3\left|P_{2}, 3\right| P_{3}$ and $9 \times P_{3}, \quad 9 \mid P_{4}$.
Therefore, we can prove by mathematical induction:

And
$$
3^{k-1} \mid P_{2 k-1},
$$
$$
\begin{array}{l}
3^{k} \mid P_{2 k-1}, \\
3^{k} \mid P_{2 k}.
\end{array}
$$
$$
k=1,2, \cdots\}
$$

Since (7) holds for $k=2$.
Assume (7) holds for $k=m$.
Then for $k=m+1$, by (6),
$$
\begin{array}{l}
P_{2 m+1}=3\left(P_{2 m}+P_{2 m-1}\right), \\
P_{2 m+2}=3\left(P_{2 m+1}+P_{2 m}\right).
\end{array}
$$

By the induction hypothesis, the first equation in (7) holds for $k=m+1$, and using this result and the induction hypothesis, we can also prove that the second equation in (7) holds for $k=m+1$.
Thus, (7) holds for all $k$.
For $k=1989$,
$$
1989=2 \times 994+1,
$$

Therefore, the highest power of 3 that divides $P_{1989}$ is $3^{994}$.