3. Felix chooses a positive integer as the starting number and writes it on the board. He then repeatedly performs the following step: he replaces the number $n$ on the board with $\frac{1}{2} n$ if $n$ is even and with $n^{2}+3$ if $n$ is odd.

(a) Prove that if Felix starts with an odd number, the next two numbers he writes will be even.

(b) For how many choices of starting numbers less than 2023 will Felix never write a number with more than four digits on the board?
## 3. Version for Class 4 and Lower

(a) Suppose Felix starts with an odd number $n$. The next number is then $n^{2}+3$. We need to show that $n^{2}+3$ is even, as well as $\frac{1}{2}\left(n^{2}+3\right)$. In other words, $n^{2}+3$ must be divisible by 4. Since $n$ is odd, it follows that $n=2 k+1$ for a non-negative integer $k$. Then,

$$
n^{2}+3=(2 k+1)^{2}+3=4 k^{2}+4 k+4=4\left(k^{2}+k+1\right)
$$

and this is indeed divisible by 4.

(b) Suppose Felix starts with an odd number $n=2 k+1$. Then the next number he writes is divisible by 4, as we have seen in (a). The next two numbers Felix gets are obtained by dividing by 2 each time. The result, $k^{2}+k+1$, is an odd number, regardless of whether $k$ is even or odd, since one of the factors of $k^{2}+k=k(k+1)$ is even. Then the same three steps follow: squaring plus 3, dividing by 2, and dividing by 2 again, and these three steps keep repeating. We will show that for odd $n \geqslant 5$, the odd number after three steps is greater than $n$. In that case, the process will keep yielding larger numbers, and Felix will eventually write a number with more than four digits. The inequality we want to verify is $\frac{1}{4}\left(n^{2}+3\right)>n$, or $n^{2}-4 n+3>0$, or $(n-2)^{2}>1$. This indeed holds for $n \geqslant 5$. Only the odd starting numbers 1 and 3 keep the numbers small: this results in the repetitions $1-4-2-1$ and $3-12-6-3$.

Suppose Felix starts with an even number. Then he will keep dividing by 2 until he encounters an odd number. If that odd number is at least 5, then the numbers will keep getting larger. Only if repeatedly dividing by 2 eventually results in 1 or 3, will the numbers remain less than four digits. These are numbers of the form $2^{i}$ or $3 \cdot 2^{i}$. There are 11 of the first form less than $2023\left(2^{0}=1\right.$ to $\left.2^{10}=1024\right)$ and 10 of the second form less than $2023\left(3 \cdot 2^{0}=3\right.$ to $\left.3 \cdot 2^{9}=1536\right)$. In total, there are thus 21 starting numbers where Felix will never write a number with more than five digits on the board.