Letting $ n\mapsto 2n$ and $ n\mapsto 2n + 1$ we can define the sequence as \[ a(2n) = a(n) + ( - 1)^n,\quad a(2n + 1) = a(n) + ( - 1)^{n + 1} \] for all $ n$. Or equivalently, \[ a(2n + \epsilon) = a(n) + ( - 1)^{n\bmod 2 + \epsilon}\qquad(*) \] where $ \epsilon\in\{0,1\}$. Let $ n = \overline{a_ka_{k - 1}\dots a_1a_0} = 2^ka_k + 2^{k - 1}a_{k - 1} + \dots + 2a_1 + a_0$, where $ a_i\in\{0,1\}\forall i$ and $ a_k = 1$, be the binary representation of $ n$. We get using $ (*)$, \begin{align*}a(n) & = a(\overline{a_ka_{k - 1}\dots a_1a_0}) \\ & = a(2^ka_k + 2^{k - 1}a_{k - 1} + \dots + 2a_1 + a_0) \\ & = a(2^{k - 1}a_k + 2^{k - 2}a_{k - 1} + \dots + 2a_2 + a_1) + ( - 1)^{a_1 + a_0} \\ & = a(\overline{a_ka_{k - 1}\dots a_1}) + ( - 1)^{a_1 + a_0}\end{align*} And an inductive argument shows that \[ a(\overline{a_ka_{k - 1}\dots a_1a_0}) = ( - 1)^{a_k + a_{k - 1}} + ( - 1)^{a_{k - 1} + a_{k - 2}} + \dots + ( - 1)^{a_1 + a_0} \] Now to find $ \max\{a(i)\}$, we need to have $ a_i + a_{i + 1}\equiv 0\pmod 2$ for $ i = 0,1,\dots,k - 1$. Since $ a_k = 1$, we conclude that $ a_0 = a_1 = \dots = a_{k - 1} = 1$, and thus $ a(n)$ is maximum for $ n = 1 + 2 + 2^2 + \dots + 2^k = 2^{k + 1} - 1$ in which case $ a(n) = a(2^{k + 1} - 1) = k$. Therefore for $ n\le 1996$ we conclude $ a(2^{10} - 1) = a(1023) = 9$ is maximum. Similarly, for the minimum we must have $ a_i + a_{i + 1}\equiv 1\pmod 2$ for the same values of $ i$ as before, and with $ a_k = 1$ we get $ a_{k - 1} = 0,a_{k - 2} = 1,\dots$, with alternating $ 0$'s and $ 1$'s. Hence $ n = 2^{k} + 2^{k - 2} + \dots = \frac {2^{k + 2} - 1}{3}$ for even $ k$, and $ \frac {2^{k + 2} - 2}{3}$ for odd $ k$, and in these cases $ a(n) = - k$. Therefore $ n\le 1996$ implies for even $ k$, $ a(n) = a\left(\frac {2^{12} - 1}{3}\right) = a(1365) = - 10$, or for odd $ k$, $ a(n) = a\left(\frac {2^{11} - 2}{3}\right) = a(682) = - 9$. Therefore, in conclusion, the intended maximum is $ a(1023) = 9$, and the minimum is $ a(1365) = - 10$. For the second part of the problem, we need half of the elements of $ \{a_k + a_{k - 1},a_{k - 1} + a_{k - 2},\dots,a_1 + a_0\}$ to be even, and the remaining ones odd. In that case $ k$ must be even. Also, given such a sequence $ a_k,a_{k-1},\dots,a_{k-i}$ there is only one choice for $ a_{k-i-1}$. Hence we have a bijection with the number of ways to choose $ k/2$ arbitrary elements from a $ k$ element set, which is $ \binom{k}{k/2}$. Again, since $ 1996_2 = 11111001100$, we get $ k\le 10$. Hence the intended number of ways is \[ \binom{10}{5} + \binom{8}{4} + \binom{6}{3} + \binom{4}{2} + \binom{2}{1} = 350 \] and with $ a(1) = 0$, the total number of $ i$'s not exceeding $ 1996$ such that $ a(i) = 0$ is $ 351$. Ps. Solution might contain calculation mistakes.