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)^{\frac{n(n+1)}{2}} . \quad(\text{Here }[t]=\text{ the greatest integer } \leq t .) \]
(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
$$
a(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 $a(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}{k / 2}$ ways. Thus the number of positive integers $n<2^{11}=2048$ with $a(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{11111010010}_{2}$, $2004=\overline{11111010100}_{2}$, $2006=\overline{11111010110}_{2}$, $2010=\overline{11111011010}_{2}$, $2026=\overline{11111101010}_{2}$. Therefore there are 346 numbers $n \leq 1996$ for which $a(n)=0$.