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

(a) Prove that when Felix starts with an odd number, the next two numbers he writes down are even.

(b) For how many choices of starting numbers below 2023 will Felix never write a number of more than four digits on the board?

## 3. Version for klas 4 and below

(a) Suppose Felix starts with an odd number $n$. Then the next number he writes down is $n^{2}+3$. We must show that $n^{2}+3$ is even, and $\frac{1}{2}\left(n^{2}+3\right)$ is even as well. In other words, $n^{2}+3$ must be divisible by 4 . Since $n$ is odd, we can write $n=2 k+1$ for a non-negative integer $k$. Then it holds that

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

and this is indeed divisible by 4 .

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

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

