21. N4 (FRA) For any positive integer $x_{0}$, three sequences $\left\{x_{n}\right\},\left\{y_{n}\right\}$, and $\left\{z_{n}\right\}$ are defined as follows:
(i) $30=4$ and $z_{0}=1$;
(ii) if $x_{n}$ is even for $n \geq 0, x_{n+1}=\frac{x_{n}}{2}, y_{n+1}=2 y_{n}$, and $z_{n+1}=z_{n}$;
(iii) if $x_{n}$ is odd for $n \geq 0, x_{n+1}=x_{n}-\frac{y_{n}}{2}-z_{n}, y_{n+1}=y_{n}$, and $z_{n+1}=$ $y_{n}+z_{n}$.
The integer $x_{0}$ is said to be good if $x_{n}=0$ for some $n \geq 1$. Find the number of good integers less than or equal to 1994 .
21. Note first that $y_{n}=2^{k}(k \geq 2)$ and $z_{k} \equiv 1(\bmod 4)$ for all $n$, so if $x_{n}$ is odd, $x_{n+1}$ will be even. Further, it is shown by induction on $n$ that $u_{n}>z_{n}$ when $x_{n-1}$ is even and $2 y_{n}>z_{n}>y_{n}$ when $x_{n-1}$ is odd. In fact, $n=1$ is the trivial case, while if it holds for $n \geq 1$, then $y_{n+1}=2 y_{n}>z_{n}=z_{n+1}$ if $x_{n}$ is even, and $2 y_{n+1}=2 y_{n}>y_{n}+z_{n}=z_{n+1}$ if $x_{n}$ is odd (since then $x_{n-1}$ is even).
If $x_{1}=0$, then $x_{0}=3$ is good. Suppose $x_{n}=0$ for some $n \geq 2$. Then $x_{n-1}$ is odd and $x_{n-2}$ is even, so that $y_{n-1}>z_{n-1}$. We claim that a pair $\left(y_{n-1}, z_{n-1}\right)$, where $2^{k}=y_{n-1}>z_{n-1}>0$ and $z_{n-1} \equiv 1$ $(\bmod 4)$, uniquely determines $x_{0}=f\left(y_{n-1}, z_{n-1}\right)$. We see that $x_{n-1}=$ $\frac{1}{2} y_{n-1}+z_{n-1}$, and define $\left(x_{k}, y_{k}, z_{k}\right)$ backwards as follows, until we get $\left(y_{k}, z_{k}\right)=(4,1)$. If $y_{k}>z_{k}$, then $x_{k-1}$ must have been even, so we define $\left(x_{k-1}, y_{k-1}, z_{k-1}\right)=\left(2 x_{k}, y_{k} / 2, z_{k}\right)$; otherwise $x_{k-1}$ must have been odd, so we put $\left(x_{k-1}, y_{k-1}, z_{k-1}\right)=\left(x_{k}-y_{k} / 2+z_{k}, y_{k}, z_{k}-y_{k}\right)$. We eventually arrive at $\left(y_{0}, z_{0}\right)=(4,1)$ and a good integer $x_{0}=f\left(y_{n-1}, z_{n-1}\right)$, as claimed. Thus for example $\left(y_{n-1}, z_{n-1}\right)=(64,61)$ implies $x_{n-1}=93$, $\left(x_{n-2}, y_{n-2}, z_{n-2}\right)=(186,32,61)$ etc., and $x_{0}=1953$, while in the case of $\left(y_{n-1}, z_{n-1}\right)=(128,1)$ we get $x_{0}=2080$.
Note that $y^{\prime}>y \Rightarrow f\left(y^{\prime}, z^{\prime}\right)>f(y, z)$ and $z^{\prime}>z \Rightarrow f\left(y, z^{\prime}\right)>f(y, z)$. Therefore there are no $y, z$ for which $1953<f(y, z)<2080$. Hence all good integers less than or equal to 1994 are given as $f(y, z), y=2^{k} \leq 64$ and $0<z \equiv 1$ (mod 4), and the number of such $(y, z)$ equals $1+2+4+8+16=$ 31. So the answer is 31 .