Problem 4. Consider a non-zero natural number $n$ and the function

$$
f: \mathbb{N} \rightarrow \mathbb{N}, f(x)=\left\{\begin{array}{c}
\frac{x}{2} \quad, \text { if } x \text { is even } \\
\frac{x-1}{2}+2^{n-1}, \text { if } x \text { is odd }
\end{array}\right.
$$

Determine the set

$$
A=\{x \in \mathbb{N} \mid(\underbrace{f \circ f \circ \ldots \circ f}_{\text {of } n \text { times } f})(x)=x\}
$$
Solution. We observe that $f(x) < x$ for $x \geq 2^n$, so $A \subset \{0, 1, \ldots, 2^n - 1\} \ldots \ldots \ldots .2$ p

We show that $A = \{0, 1, \ldots, 2^n - 1\}$. From $f(2^n - 1) = 2^n - 1$ we deduce $2^n - 1 \in A$.

Then, $2 f(x) \in \{x, x + 2^n - 1\}$, so $2 f(x)$ is congruent to $x$ modulo $2^n - 1 \ldots \ldots .2$ p

It follows inductively that $x \equiv 2^n f^{[n]}(x) \equiv f(x) \pmod{2^n - 1}$. Since $f(x) < 2^n - 1$ for $x < 2^n - 1$, we deduce $f^{[n]}(x) = x$ if $x \in \{0, 1, \ldots, 2^n - 2\}$ (we denote $f^{[n]} = \underbrace{f \circ \ldots \circ f}_{\text{of } n \text{ times } f}$. $3 \mathbf{p}$

Another solution. As above, $A \subset \{0, 1, \ldots, 2^n - 1\} \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots . \ldots \ldots . \ldots \ldots$ For $x \in \{0, 1, \ldots, 2^n - 1\}$, we write $x$ in base 2 with $n$ digits, adding, if necessary,

![](https://cdn.mathpix.com/cropped/2024_06_07_017d0dd5bd29afd1c0bbg-4.jpg?height=46&width=1399&top_left_y=1517&top_left_x=360)

Then $f(x)$ is obtained from $x$ by moving the last digit of $x$ to the first position; after $n$ compositions, the digits of $x$ appear in the same positions as at the beginning, so $f^{[n]}(x) = x \ldots \ldots \ldots \ldots .3$ p