The author, currently a teacher at UVT, was an international Olympian in mathematics. Originally from the city of Lugoj, he came with a bus full of students to the Timisoara County Olympics.
Published in the Magazine(aka REVISTE) "GAZETA MATEMATICĂ : Supliment cu Exerciții", September 2024 at page 10. The statement is:
"Let $f:\mathbb{R} \rightarrow \mathbb{Z}$ be a monotone and surjective function with properties:
(i) $f(f(x))=f(x),\;\forall x\in \mathbb{R};$
(ii) $f(2x)-f(x)=f\left ( x+\frac{1}{2}\right ),\; \forall x \in \mathbb{R}.$
a) Show that $f\left ( k-\frac{1}{2^n} \right )=k-1$, whatever $k \in \mathbb{Z}$ and $n \in \mathbb{N}.$
b) Determine the function $f$. "
ANSWER CiP
a) Induction on $n\in \mathbb{N}$
b) f(x)=[x] - the Floor function
Solution CiP
The function $f$ being surjective, for $k\in\mathbb{Z}$ there exists $x_k\in\mathbb{R}$ such that $f(x_k)=k.$ Now $k=f(x_k)\underset{(i)}{=}f(f(x_k))=f(k)$, so
$$f(k)=k,\;\;\forall k\in\mathbb{Z} \tag{1}$$
We see from (1) that the function $f$ is weakly increasing i.e.
$$x<y\;\Rightarrow\;f(x)\leqslant f(y). \tag{1#}$$
a) Equation
$$f\left (k-\frac{1}{2^n}\right )=k-1 \tag{2}$$
is true for $n=0$ according to (1). From (ii) we have
$$f\left (2\left (k-\frac{1}{2}\right)\right )-f\left (k-\frac{1}{2}\right )=f\left (k-\frac{1}{2}+\frac{1}{2}\right )\;\Leftrightarrow$$
$$\Leftrightarrow\;f(2k-1)-f\left (k-\frac{1}{2}\right )=f(k)\;\underset{(1)}{\Leftrightarrow}$$
$$\Leftrightarrow\;(2k-1)-f\left (k-\frac{1}{2}\right )=k\;\Rightarrow\;f\left (k-\frac{1}{2}\right )=k-1$$
so (2) is true for $n=1$.
{ edit nov 23, 2024: It seems that an inductive reasoning of (2) after $n$ has no immediate chance of success. }
From $(1)$ and $(1\#)$ we obtain the important estimate
$$k\leqslant x<k+1\;\;\;\Rightarrow\;k\leqslant f(x)\leqslant k+1,\;\;k\in\mathbb{Z}. \tag{3}$$
Let us assume that for a certain $k_0\in \mathbb{Z}$ we have $\color {Red}{f\left (k_0-\frac{1}{4}\right ) \neq k_0-1}$. Hence, from (1#) follow $f\left ( k_0-\frac{1}{4}\right )=k_0$.
We have equality
$$f(2x+1)-f(2x)=f(x+1)-f(x) ,\;\;\forall x \in \mathbb{R}.\tag{4}$$
Indeed, applying (ii) to the underlined expressions
$$f(2x+1)-f(2x)=\underline{f \left ( 2 \left ( x+\frac{1}{2}\right ) \right )}-f(2x)=$$
$$=f\left (x+\frac{1}{2} \right )+f\left(x+\frac{1}{2}+\frac{1}{2} \right )-f(2x)=f(x+1)-\underline{f(2x)+f\left (x+\frac{1}{2} \right )}=$$
$$=f(x+1)-f(x).$$
Taking in (4) $x=k_0-\frac{1}{4}$ we get $f \left ( 2 \left (k_0-\frac{1}{4} \right )+1 \right )-f \left (2 \left( k_0-\frac{1}{4} \right ) \right )=f \left (k_0-\frac{1}{4}+1\right)-f(\left (k_0-\frac{1}{4} \right )\;\Leftrightarrow$
$$\Leftrightarrow\;f\left (2k_0+1-\frac{1}{2} \right )-f \left (2k_0-\frac{1}{2}\right )=f\left (k_0-\frac{1}{4}+1 \right )-f\left (k_0-\frac{1}{4} \right ) \;\Leftrightarrow$$
$$\overset{(2)\;for\;n=1}{\underset{f(k_0-1/4)=k_0}{\Leftrightarrow}}\;2k_0-(2k_0-1)=f\left (k_0+1-\frac{1}{4}\right )-k_0$$
hence $f\left (k_0+1-\frac{1}{4}\right )=k_0+1$, so applying a inductive reasoning results
$$f\left (k-\frac{1}{4}\right )=k,\;\forall k\geqslant k_0,\;k\in \mathbb{Z}.\tag{5}$$
Applying (ii) again for $k-\frac{1}{4}$ we get $f\left (2\left (k-\frac{1}{4}\right) \right )-f\left (k-\frac{1}{4} \right )=f\left (k-\frac{1}{4}+\frac{1}{2} \right )$
$$\Leftrightarrow\;f\left (2k-\frac{1}{2} \right )-f\left (k-\frac{1}{4} \right )=f\left ( k+\frac{1}{4} \right )\;\overset {(2)\;for\;n=1}{\underset{(5)}{\Leftrightarrow}}$$
$$\Leftrightarrow\;(2k-1)-k=f\left (k+\frac{1}{4} \right )\;\Leftrightarrow\;f\left (k+\frac{1}{4} \right )=k-1.$$
But then we get $k=f(k)\leqslant f \left ( k+\frac{1}{4} \right )=k-1$, FALSE.
So $f\left (k-\frac{1}{4} \right )=k-1,\; \forall k \in \mathbb{Z}$ hence (2) is true for $n=2$.
{edit nov 27, 2024: This is how we can prove (2) by induction on $n$ }
Let the predicate depending on the variable $n\in \mathbb{N}$ be
$$P(n)\;:\;\;"\forall k \in \mathbb{Z},\;f\left (k-\frac{1}{2^n} \right )=k-1"$$
For $n\in \{0,\;1,\;2\}$ we have $P(n)-{\color{Green}{true}}$.
We now assume $P(n)$-true for some $n$ and we will show that $P(n+1)$ is also true, so according to mathematical induction it results $\forall n\in \mathbb{N}\;P(n)$-true.
If, by absurdity, $P(n+1)$ is false, it means that there exists $k_0\in \mathbb{Z}$ such that $f\left ( k_0-\frac{1}{2^{n+1}} \right ) \neq k_0-1$. But, because of (3), we must then have
$$f\left (k_0-\frac{1}{2^{n+1}}\right )=k_0. \tag{6}$$
Applying (ii) for $x=k_0-\frac{1}{2^{n+1}}$ we get
$$f\left (2\left (k_0-\frac{1}{2^{n+1}}\right ) \right )-f\left ( k_0-\frac{1}{2^{n+1}}\right )=f\left ( k_0-\frac{1}{2^{n+1}}+\frac{1}{2} \right )\;\Leftrightarrow$$
$$\Leftrightarrow\;f\left ( 2k_0-\frac{1}{2^n}\right )-f \left (k_0-\frac{1}{2^{n+1}} \right )=f\left (k_0+\frac{1}{2}-\frac{1}{2^{n+1}} \right )\;\Leftrightarrow$$
$$\overset{P(n)-true}{\underset{(6)}{\Leftrightarrow}} \;(2k_0-1)-k_0=f\left (k_0+\frac{1}{2}-\frac{1}{2^{n+1}} \right )\;\;\Rightarrow$$
$$\Rightarrow\;\;\;f\left( k_0+\frac{1}{2}-\frac{1}{2^{n+1}} \right )=k_0-1.$$
But, since $\frac{1}{2}-\frac{1}{2^{n+1}}>0$, we have the inequalities
$k_0=f(k_0)\leqslant f\left (k_0+\frac{1}{2}-\frac{1}{2^{n+1}} \right )=k_0-1$-FALSE.
With this "a)" is demonstrated.
b) Let's show that for $k\leqslant x <k+1$ we have $f(x)=k$.
If we choose a $n>-log_2(k+1-x)$ we have
$-n<log_2(k+1-x)\;\;\Rightarrow\;\;2^{-n}<k+1-x\;\;\Rightarrow\;\;x<k+1-\frac{1}{2^n}.$
Further $k=f(k)\leqslant f(x)\leqslant f\left ( k+1-\frac{1}{2^n} \right )\underset {(2)}{=}k$, so $f(x)=k$. We got the answer.
$\blacksquare$
