2

Consider a positive integer $n$ and the function $f:\mathbb{N}\to \mathbb{N}$ ($\mathbb N$ includes $0$) by

$$f(x) = \begin{cases} \frac{x}{2} & \text{if } x \text{ is even} \\ \frac{x-1}{2} + 2^{n-1} & \text{if } x \text{ is odd} \end{cases} $$ Determine the set

$$ A = \{ x\in \mathbb{N} \mid \underbrace{\left( f\circ f\circ ....\circ f \right)}_{n\ f\text{'s}}\left( x \right)=x \}. $$

(Romania NMO 2013)

The solution starts by stating that $f(x)<x, \quad\forall x\ge 2^n-1$. This was easy enough to understand. However, they continue by saying this implies that $A\subset\{0,1,\dots,2^n-1\}$. Why is that?

Please help me understand! Thanks in advance!

furfur
  • 598
  • For $x \leqslant 2^n - 1$ we have $f(x) \leqslant 2^n - 1$ too. – Daniel Fischer Sep 01 '20 at 18:45
  • the only way for $f(x) > 2^n-1$ is for $x > 2^n-1$ and $2^n-1 < f(x) < x$. So if $2^n-1< f(f(f(....(x))))..) = x$ that means $2^n-1 < x= f(f(f(....(x))))) < f(f(.....(x)))) < f(....(x) < ...... <f(f(x)) < f(x) < x$ which is a contradiction. – fleablood Sep 01 '20 at 19:05

3 Answers3

1

Note first that the inequality $f(x) < x$ only holds for $x \geq 2^n$ since $f(2^n - 1) = 2^n -1$.

If there is an element $x \in A$ with $x \geq 2^n$, then we can choose such an $x$ minimally, i.e. such that every $y \in A$ with $y < x$ satisfies $y \leq 2^n - 1$. Now we have $f^n(x) = x$ and hence $$f^n(f(x)) = f^{n+1}(x) = f(f^n(x)) = f(x),$$ so $f(x) \in A$ and the minimality of $x$ together with $f(x) < x$ implies $f(x) \leq 2^n - 1$.

Now check that this implies $f^k(f(x)) \leq 2^n-1$ for all $k \in \mathbb{N}$ (as hinted at in Daniel's comment) and in particular $x = f^n(x) = f^{n-1}(f(x)) \leq 2^n-1$, contradicting the initial choice of $x$.

Sebastian A. Spindler
  • 1,799
1

Hint:

Letting all divisions be integer and splitting the cases after the low order bits of $x$, we can expand the function iterates for, say, $n=4$, and the pattern becomes obvious.

$$f(x)=\begin{cases}\frac x2&\text{ if } x \text{ is even}\\\frac{x}2+8&\text{ if } x \text{ is odd}\end{cases}$$

$$f(f(x))=\begin{cases}\frac x4&\\\frac{x}4+4\\\frac{x}4+8\\\frac{x}4+12\end{cases}$$

$$f(f(f(x)))=\begin{cases} \frac x8&\\\frac{x}8+2\\\frac{x}8+4\\\frac{x}8+6\\ \frac x8+8&\\\frac{x}8+10\\\frac{x}8+12\\\frac{x}8+14\end{cases}$$

$$f(f(f(f(x))))=\begin{cases} \frac x{16}&\\\frac{x}{16}+1\\\frac{x}{16}+2\\\frac{x}{16}+3\\ \frac x{16}+4&\\\frac{x}{16}+5\\\frac{x}{16}+6\\\frac{x}{16}+7\\ \frac x{16}+8&\\\frac{x}{16}+9\\\frac{x}{16}+10\\\frac{x}{16}+11\\ \frac x{16}+12&\\\frac{x}{16}+13\\\frac{x}{16}+14\\\frac{x}{16}+15\end{cases}$$

0

Stating $f(x) < x,\forall x > 2^n-1$ can be seen as the base step for an induction argument.

We can finish by induction proving :

if $\underbrace{\left( f\circ f\circ ....\circ f \right)}_{k\ f\text{'s}}\left( x \right) < x,\forall x > 2^n-1$ then $\underbrace{\left( f\circ f\circ ....\circ f \right)}_{k+1\ f\text{'s}}\left( x \right) <x,\forall x > 2^n-1$.

First of all put $\underbrace{\left( f\circ f\circ ....\circ f \right)}_{k\ f\text{'s}}\left( x \right) = t_1$ and $\underbrace{\left( f\circ f\circ ....\circ f \right)}_{k+1\ f\text{'s}}\left( x \right) = t_2$ , now:

  • if $t_1$ is even then $t_2 = \frac{t_1}{2} < t_1< x$.

  • if $t_1$ is odd, then $t_2 = \frac{t_1-1}{2}+2^{n-1}$, then we have to show:$$\frac{t_1-1}{2}+2^{n-1} < x \iff t_1 <x+x-(2^n-1)$$but we know that $t_1<x$ and that $x-(2^n-1)>0$, so $t_1 <x+x-(2^n-1)$ is true.

So clearly $A$ is a subset of $\{1,2,...,2^n-1\}$.

Tortar
  • 3,980