Problem 1295

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.