6・113 Let the sequence $a(n), n=1,2,3, \cdots$, be defined as follows:
$a(1)=0$, and for $n>1$,
$$a(n)=a\left(\left[\frac{n}{2}\right]\right)+(-1)^{\frac{n(n+1)}{2}} .$$
(a) Find the maximum and minimum values of $a(n)$ for $n<1996$, and provide all values of $n$ at which these extrema are attained.
(b) For $n<1996$, how many terms of $a(n)$ are equal to 0?
[Solution] For $n>1$,
$$a(n)=a\left(\left[\frac{n}{2}\right]\right)+(-1)^{\frac{n(n+1)}{2}},$$

we can derive that for $n \geqslant 1$,
$$\begin{aligned}
a(2 n) & =a(n)+(-1)^{n(2 n+1)} \\
& =a(n)+(-1)^{n} \\
a(2 n+1) & =a(n)+(-1)^{(2 n+1)(n+1)} \\
& =a(n)+(-1)^{n+1} .
\end{aligned}$$

Assume that for $n \geqslant 2$, the binary representation of $n$ is
$$\left(\alpha_{1} \alpha_{2} \cdots \alpha_{l}\right)_{2}$$

where $\alpha_{i}=0$ or $1, i=1,2, \cdots, l$. Consider the $l-1$ pairs of digits
$$\left(\alpha_{1}, \alpha_{2}\right),\left(\alpha_{2}, \alpha_{3}\right), \cdots,\left(\alpha_{l-1}, \alpha_{l}\right)$$

Let $f(n)$ be the number of pairs where $a_{k}=a_{k+1}$, and $g(n)$ be the number of pairs where $a_{k} \neq a_{k+1}$, for $k=1,2, \cdots, l-1$. Clearly,
$$f(n)+g(n)=l-1$$

We will prove by induction that for $n \geqslant 2$,
$$a(n)=f(n)-g(n)$$

In fact, $a(2)=a(1)+(-1)^{1}=-1$.
$$a(3)=a(1)+(-1)^{2}=1$$

Also, $f(2)=0, g(2)=1, f(3)=1, g(3)=0$. Therefore, (1) holds for $n=2,3$.

Assume that for some $k \geqslant 3$, (1) holds for $2 \leqslant n \leqslant k$. Consider the case when $n=k+1$.
$$\begin{array}{l}
\text { Let } k+1=\left(\alpha_{1} \alpha_{2} \cdots a_{l}\right)_{2}, l \geqslant 3 \text {. Then } \\
\begin{aligned}
a(k+1)= & a\left(\left(\alpha_{1} \alpha_{2} \cdots \alpha_{l}\right)_{2}\right) \\
= & a\left(\left(\alpha_{1} \alpha_{2} \cdots \alpha_{l-1}\right)_{2}\right)+(-1)^{\left(\alpha_{1} \alpha_{2} \cdots a_{l-1}\right)_{2}+\alpha_{l}} \\
= & f\left(\left(\alpha_{1} \alpha_{2} \cdots \alpha_{l-1}\right)_{2}\right)-g\left(\left(\alpha_{1} \alpha_{2} \cdots \alpha_{l-1}\right)_{2}\right) \\
& +(-1)^{\alpha_{l-1}+\alpha_{l}}
\end{aligned}
\end{array}$$

If $\alpha_{l-1}=\alpha_{l}$, then
$$\begin{array}{l}
f(k+1)=f\left(\left(\alpha_{1} \alpha_{2} \cdots \alpha_{l-1}\right)_{2}\right)+1 \\
g(k+1)=g\left(\left(\alpha_{1} \alpha_{2} \cdots \alpha_{l-1}\right)_{2}\right)
\end{array}$$

Thus,
$$\begin{aligned}
a(k+1) & =f\left(\left(\alpha_{1} \alpha_{2} \cdots \alpha_{l-1}\right)_{2}\right)-g\left(\left(\alpha_{1} \alpha_{2} \cdots \alpha_{l-1}\right)_{2}\right)+1 \\
& =f(k+1)-g(k+1) .
\end{aligned}$$

If $\alpha_{l-1} \neq \alpha_{l}$, then
$$\begin{array}{l}
f(k+1)=f\left(\left(\alpha_{1} \alpha_{2} \cdots \alpha_{l-1}\right)_{2}\right) \\
g(k+1)=g\left(\left(\alpha_{1} \alpha_{2} \cdots \alpha_{l-1}\right)_{2}\right)+1
\end{array}$$

Thus,
$$\begin{aligned}
a(k+1) & =f\left(\left(\alpha_{1} \alpha_{2} \cdots \alpha_{l-1}\right)_{2}\right)-g\left(\left(\alpha_{1} \alpha_{2} \cdots \alpha_{l-1}\right)_{2}\right)-1 \\
& =f(k+1)-g(k+1)
\end{aligned}$$

Therefore, (1) also holds for $n=k+1$.
(a) Since $(1995)_{10}=(11111001011)_{2}$, and by (1), $a(n)$ reaches its maximum value 9 when $n=(1111111111)_{2}=1023$, and its minimum value -10 when $n=(10101010101)_{2}=1365$.
(b) Let $n=\left(\alpha_{1} \alpha_{2} \cdots \alpha_{l}\right)_{2}, n \geqslant 2$. Then $a(n)=0$ if and only if $f(n)=g(n)$. In this case,
$$l-1=f(n)+g(n)=2 f(n)$$

is even, so $l$ is odd.
For $2 \leqslant n \leqslant 1995$, $l$ can only be $3,5,7,9,11$.
For a fixed $l \in\{3,5,7,9,11\}$. When $2^{l-1} \leqslant n \leqslant 2^{l}-1$, the binary representation of $n$ is $\left(\alpha_{1} \alpha_{2} \cdots \alpha_{l}\right)_{2}$, and $\alpha_{1}=1$. Therefore, $a(n)=0$ if and only if exactly $\frac{l-1}{2}$ pairs $\left(\alpha_{k}, \alpha_{k+1}\right)$ satisfy $\alpha_{k}=\alpha_{k+1}$. Thus, for $2^{l-1} \leqslant n \leqslant 2^{l}-1$, there are $C_{l-1}^{\frac{l-1}{2}}$ values of $a(n)$ that are 0. Therefore, for $2 \leqslant n \leqslant 2^{11}-1$, the number of values of $a(n)$ that are 0 is
$$C_{2}^{1}+C_{4}^{2}+C_{6}^{3}+C_{8}^{4}+C_{10}^{5}=350 \text { (terms). }$$

For $1996 \leqslant n \leqslant 2^{11}-1$, it is easy to see that $a(n)=0$ only for the values
$(11111101010)_{2},(11111011010)_{2},(11111010110)_{2}$,
$(11111010010)_{2},(11111010100)_{2}$.
These 5 values.
Thus, for $2 \leqslant n \leqslant 1995$, there are 345 values of $a(n)$ that are 0. Since $a(1)=0$, there are 346 values of $a(n)$ that are 0 for $n<1996$.