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) $y_{0}=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 \pmod{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 \( y_{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 \pmod{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' > y \Rightarrow f\left(y', z'\right) > f(y, z) \) and \( z' > z \Rightarrow f\left(y, z'\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 \pmod{4} \), and the number of such \( (y, z) \) equals \( 1 + 2 + 4 + 8 + 16 = 31 \). So the answer is 31.