The sequence $a_{n}$ is defined as follows: $a_{1}=1, a_{2 n}=a_{n}, a_{2 n+1}+a_{n}=1$. What is $a_{2006}$?
I. solution.

$$
\begin{aligned}
a_{2006} & =a_{1003}=1-a_{501}=1-\left(1-a_{250}\right)=a_{125}=1-a_{62}=1-a_{31}= \\
& =1-\left(1-a_{15}\right)=a_{15}=1-a_{7}=1-\left(1-a_{3}\right)=a_{3}=1-a_{1}=0
\end{aligned}
$$

II. solution. We will show that the sequence $a_{n}$ is equal to the sequence $b_{n}$ defined by the following rule:

$$
b_{n}= \begin{cases}1, & \text { if } n \text { has an odd number of 1s in its binary representation; } \\ 0, & \text { otherwise. }\end{cases}
$$

Clearly, $b_{1}=1$, since the representation of 1 requires a single 1. The binary representation of $2n$ can be obtained from the binary representation of $n$ by appending a zero to the sequence of digits; the number of 1s does not change, so $b_{2n}=b_{n}$. Finally, the binary representation of $(2n+1)$ can be obtained by adding 1 to the binary representation of $2n$; the latter, as we have seen, ends in a zero, so adding 1 changes the last zero digit to 1, increasing the number of 1s by one, and the parity of the number of 1s will be the opposite. Thus, $b_{2n+1}=1-b_{2n}=1-b_{n}$. The sequence $b_{n}$ satisfies the same recursion and initial condition as the sequence $a_{n}$, so $a_{n}=b_{n}$ for all $n$. The binary representation of 2006 is 11111010110, so $a_{2006}=b_{2006}=0$.