9. A9 (POL) Let the sequence $a(n), n=1,2,3, \ldots$, be generated as follows: $a(1)=0$, and for $n>1$,
$$
a(n)=a([n / 2])+(-1)^{n+1} \text {. (Here }[t]=\text { the greatest integer } \leq t \text {.) }
$$
(a) Determine the maximum and minimum value of $a(n)$ over $n \leq 1996$ and find all $n \leq 1996$ for which these extreme values are attained.
(b) How many terms $a(n), n \leq 1996$, are equal to 0 ?
9. From the definition of $a(n)$ we obtain
$$
\alpha(n)-a([n / 2])=\left\{\begin{array}{r}
1 \text { if } n \equiv 0 \text { or } n \equiv 3(\bmod 4) ; \\
-1 \text { if } n \equiv 1 \text { or } n \equiv 2(\bmod 4) .
\end{array}\right.
$$

Let $n=\overline{b_{k} b_{k-1} \ldots b_{1} b_{0}}$ be the binary representation of $n$, where we assume $b_{k}=1$. If we define $p(n)$ and $q(n)$ to be the number of indices $i=0,1, \ldots, k-1$ with $b_{i}=b_{i+1}$ and the number of $i=0,1, \ldots, k-1$ with $b_{i} \neq b_{i+1}$ respectively, we get
$$
a(n)=p(n)-q(n) .
$$
(a) The maximum value of $\alpha(n)$ for $n \leq 1996$ is 9 when $p(n)=9$ and $q(n)=0$, i.e., in the case $n=\overline{1111111111_{2}}=1023$.
The minimum value is -10 and is attained when $p(n)=0$ and $q(n)=$ 10, i.e., only for $n=\overline{10101010101}_{2}=1365$.
(b) From (1) we have that $a(n)=0$ is equivalent to $p(n)=q(n)=k / 2$. Hence $k$ must be even, and the $k / 2$ indices $i$ for which $b_{i}=b_{i+1}$ can be chosen in exactly $\binom{k / 2}{k / 2}$ ways. Thus the number of positive integers $n<2^{11}=2048$ with $\alpha(n)=0$ is equal to
$$
\binom{0}{0}+\binom{2}{1}+\binom{4}{2}+\binom{6}{3}+\binom{8}{4}+\binom{10}{5}=351 .
$$

But five of these numbers exceed 1996 : these are $2002=\overline{1111010010_{2}}$, $2004=\overline{11111010100}, 2006=\overline{11111010110_{2}}, 2010=\overline{1111011010_{2}}$, $2026=\overline{11111101010}_{2}$. Therefore there are 346 numbers $n \leq 1996$ for which $a(n)=0$.