The RMM problems seem to be lacking in originality this year. After the well known #1, seeing this one was surprising too, as I have seen the following problem posted on AoPS multiple times before: Prove that the only function f:R->R satisfying f(x^2)=(f(x))^2 and f(x+1)=f(x)+1 is f(x)=x.

Someone please check my solution, I am very skeptical about it because it seems simple for RMM (and for that possibly false). Answer is yes. Take $g(x)=x+1$ and $h(x)=x^2$. \[ f(x+1)=f(x)+1, \\ f(x^2)=(f(x))^2\] Claim: $f(x)=x$ For integers it can be easily seen what is their image. Down we can suppose $x$ is not integer. Lemma 1: For each $x$: $\lfloor{f(x)} \rfloor \ge \lfloor{x} \rfloor$. Suppose opposite. Then it holds also for $=x-\lfloor{x} \rfloor $. But $x-\lfloor{x} \rfloor \ge 0$ and $f(x- \lfloor{x} \rfloor)=f(x)-\lfloor{x} \rfloor < 0$. That is contradiction with the second condition that says that $f$ is positive when $x$ is positive. Lemma 2: We have for each $x$ : $\lfloor{f(x)} \rfloor \le \lfloor{x} \rfloor$. Suppose opposite.$f(x-1)=f(x)-1, f(x-2)=f(x)-2 \dots$ We will have a negative number such that its image is positive. Also if continue to decrease argument of function by 1, we will have value of $f$ between $(-1,0)$ and argument of function $t$ will be strictly less than $-1$. But $f(t^2)=f(t)^2<1$ and $t^2 \ge 1$. This contradicts first lemma. Conclusion $\lfloor{f(x)} \rfloor = \lfloor{x} \rfloor$. Take $x \ge 1$. $f(x^2)=f(x)^2$, $f(x^4)=f(x)^4 \dots$. If $f(x)$ is different than $x$ then there exists positive integer $n$ such that distance between $f(x)^{2^n}$ and $x^{2^n}$ is bigger than one- contradiction. EDIT: I now see that MathTwo suggests same functions.

If the requirement $g,h$ bijective (or even just surjective) had been added, and the yes/no aspect removed (although it might be OK for the bijective version), I think the problem would've been much better... The three official solutions all have a nice combinatorial flavor; the second constructs surjective $g,h$ and the third constructs bijective $g,h$. (Both use binary encoding.) This would rule out all of the solutions that use $f(\operatorname{Range}(g)) \subseteq \operatorname{Range}(g)$ to get $|f(x) - x|$ bounded by a constant.

RaleD wrote: Lemma 2: We have for each $x$ : $\lfloor{f(x)} \rfloor \le \lfloor{x} \rfloor$. Suppose opposite.$f(x-1)=f(x)-1, f(x-2)=f(x)-2 \dots$ We will have a negative number such that its image is positive. Also if continue to decrease argument of function by 1, we will have value of $f$ between $(-1,0)$ and argument of function $t$ will be strictly less than $-1$. But $f(t^2)=f(t)^2<1$ and $t^2 \ge 1$. This contradicts first lemma. between $(-1,0)$? Maybe $[-1,0)$

@yunxiu: Yes, you are right, but it still should be ok with small corrections

Hmm the bounding idea from IMO #5 this year is somewhat reminiscent of this problem.

A bit more complicated solution:

In the third official solution which proves bijective functions exist, how would one think of translating the problem into a graph theory problem and how would one come up with the functions $g$ and $h$? Is it common to do such things? Thanks in advance!

Motivation anyone? Also, it said at the end of the official solution about a hyper-continual set. What is a hyper-continual set? Thanks!

I claim that the answer is yes. Let $g(x) = \lfloor x^2 \rfloor$ and $h(x) = x+1$. We know that \[f(\lfloor x^2 \rfloor ) = \lfloor f(x)^2 \rfloor \qquad (\diamondsuit )\]and \[f(x+1) = f(x) + 1. \qquad (\spadesuit)\] Now we set $x = 0,1$ in $(\diamondsuit)$, yielding \[f(0) = \lfloor f(0)^2 \rfloor\]and \[f(1) = \lfloor f(1)^2 \rfloor.\]It follows easily that $f(0) = 0$ and $f(1) = 1$. We note that for each integer $n \ge 0$, $\sqrt{n} \le x < \sqrt{n+1}$ implies $\sqrt{n} \le f(x) < \sqrt{n+1}$ or $-\sqrt{n+1} < f(x) \le -\sqrt{n}$. Due to $(\spadesuit)$, we must have $\sqrt{n} \le f(x) < \sqrt{n+1}$. It follows that $f(x) - x \rightarrow 0$. Thus $f(x) = x$ for all $x$. $\blacksquare$

Answer: Yes. Let $\mathcal{S} = \{0, 1\}^{\mathbb{N}}$ be the set of all infinite binary sequences. Since $\mathbb{R}$ and $\mathcal{S}$ are in bijection we deal with $\mathcal{S}$ only. Define $g, h: \mathcal{S} \to \mathcal{S}$ by \begin{align*} g(x_1, x_2, \dots) & = 0, x_1, x_2, \dots,\\ h(x_1, x_2, \dots) & = 1, x_1, x_2, \dots. \end{align*}Then, a hypothetical $f$ must satisfy the following: \begin{align*} f(0, x_1, x_2, \dots) & = 0, f(x_1, x_2, \dots),\\ f(1, x_1, x_2, \dots) & = 1, f(x_1, x_2, \dots). \end{align*}In particular, \begin{align*} f(x_0, x_1, x_2, \dots) & = x_0, f(x_1, x_2, \dots)\\ & = x_0, x_1, f(x_2, \dots)\\ & = x_0, x_1, x_2, f(\dots)\\ & \vdots \end{align*}forcing $f(s) = s$ for all $s \in \mathcal{S}$ as desired.

Yes, the pair exists. We take $g(x)=x+1$ and $h(x)=x^2$, so we're now going to show that the only function $f:\mathbb{R}\to\mathbb{R}$ satisfying $f(x+1)=f(x)+1$ and $f(x^2)=f(x)^2$ is $f\equiv\mathrm{id}$. Note that $f(1)=f(1)^2$ and $f(0)=f(0)^2$, so $f(0),f(1)\in\{0,1\}$. However, we also have $f(1)=1+f(0)$, so $f(0)=0$ and $f(1)=1$. This easily implies that $f(n)=n$ for all $n\in\mathbb{Z}$. Lemma: For any real number $x$, we have $f(x)\ge\lfloor x\rfloor$. Proof: Note that if $y\ge 0$, then $f(y)=f(\sqrt{y})^2\ge 0$. Let $y=x-\lfloor x\rfloor\ge 0$. Thus, \[0\le f(x-\lfloor x\rfloor)=f(x)-f(\lfloor x\rfloor)=f(x)-\lfloor x\rfloor,\]\ as desired. $\blacksquare$ We now can state and prove the killer blow. Claim: For any real number $x$, we have $f(x)\ge x$. Proof: Since $f(x+1)=f(x)+1$, it suffices to show the claim for sufficiently large $x$. In particular, we'll show the claim when $x>1$. Iterating the lemma over and over, we see that \[f(x)^{2^n}\ge\lfloor x^{2^n}\rfloor\ge x^{2^n}-1,\]so for arbitrarily large $N$, we have \[f(x)\ge (x^N-1)^{1/N}=x(1-x^{-N})^{1/N}\ge x(1-x^{-N}).\]This implies that $f(x)\ge x$, as desired. $\blacksquare$ Note that $f(-x)^2=f(x)^2$, so $f(-x)=\pm f(x)$. Suppose we have $0<x<1$ and $f(x)>x$. Then, $f(-x)=f(x)$, otherwise $f(-x)<-x$, which is a contradiction. Thus, $f(-x)=f(x)$, so $f(1-x)=f(x)+1>1+x>1-x$. Thus, by the same logic, $f(x-1)=f(1-x)=1+f(x)$, so $f(x)-1=f(x)+1$, a contradiction. Therefore, $f(x)=x$ for all $0\le x\le 1$, so since $f(x+1)=f(x)+1$, we have $f\equiv\mathrm{id}$, as desired.

Let's set $g(x) = x + 1$ to enforce some sort of linearity-ish condition on $f$. Indeed,\[f(g(x)) = g(f(x)) \implies f(x+1) = f(x) + 1.\]Now we need to enforce another condition $f(h(x) = h(f(x))$ that somehow guarantees linearity along with $f(0) = 0$. In general, for any $x \in \mathbb{R}_+$, we have\[f(x) = f(x - 1) + 1 = \ldots = f(\{x\}) + \lfloor x \rfloor.\]Consider something like $h(x) = x^2$, then we have $f(x^2) = f(x)^2$. First of all, $f(0)^2 = f(0)$ and $f(1)^2 = f(1)$, so $f(0) = 0 \implies f(1) = 1$, else if $f(0) = 1$ then $f(1) = 2$, impossible. We will show that $f(x) < \lfloor x \rfloor$ is bad, which is intuitively true since that would force $f(\text{positive}) = \text{negative}$ somewhere. Indeed, we would have\[f(\{x\}) = f(x) - \lfloor x \rfloor = f\left(\sqrt{\{x\}}\right)^2\]impossible. Hence $f(x) \geq \lfloor x \rfloor$. Next, suppose $\lfloor f(x) \rfloor > \lfloor x \rfloor$. Then,\[f(\{x\} - 1) = f(x) - \lfloor x \rfloor - 1 < -1\]so we would have\[(-1 - \epsilon)^{2^k} = f(\{x\} - 1)^{2^k} = f\left((1 - \{x\})^{2^k}\right)\]so theres a small number $r \in (0, 1)$ for which $f(r)$ is large. Then, we can find a super negative $x$ with fractional part $r$ for which $f(x) = f(r) + \lfloor x\rfloor \in (0, 1)$. But then, we would have $f(x^2) = f(x)^2 \in (0, 1)$, but it has already been established that $f(x^2) < \lfloor x^2 \rfloor$ is bad, so this is impossible, and $\lfloor f(x) \rfloor > \lfloor x \rfloor$ is impossible. Hence, $\lfloor f(x) \rfloor \leq \lfloor x \rfloor$ yet $f(x) \geq \lfloor x \rfloor$ hence $f(x) = \lfloor x \rfloor + \epsilon$ for some fractional part $\epsilon \in (0, 1)$. Lastly, we make the jump $f(x) = x$ for all $x$. For any sufficiently large power $p = 2^k$, note $x^p - 1 < f(x^p) = f(x)^p < x^p + 1$, and upon considering sufficiently large $p$, the condition forces $f(x) \to x$, as desired. So the exhibited $g \equiv x+1, h \equiv x^2$ does indeed force $f \equiv x$ for all reals $x$.

Does it true if we instead the real number $\mathbb{R}$ for any set $X$?Is there any article to discuss these problems?

here is a solution that is the same as the above solutions, but with an additional remark :p

This feels like 2019 USAJMO/2 with a neat trick embedded. I claim that taking $(g, h) = \left(x+1, x^2\right)$ works; so $f(x+1) = f(x) + 1$ and $f\left(x^2\right) = f(x)^2$. Now, observe the following very important claim: Claim: If $a \geq 0$, then $f(a) \geq 0$. Proof: Clear by the second equation. $\blacksquare$ This claim is actually all that we need. Assume $f \neq x$. Claim: There exists real numbers $a>b>1$ such that $f(a) = b$. Proof: Assume for the sake of contradiction that we cannot find such a pair. Then fix a pair $(a', b')$ such that $f(a') = b'$ and $a' < b'$, and assume $a'$ and $b'$ are both positive (otherwise just square). Let $m = \lfloor b' \rfloor$. Take $a = (a'-m-1)^2$ and $b = (b'-m-1)^2$. Then $a'-m-1 < b'-m-1 < 0$, so it follows that $a>b$. The two equations still imply $f(a) = b$, as needed. Now just shift up by $1$. $\blacksquare$ Now let $\varepsilon = a-b$ and let $N > \log_2\left(\frac 2{\varepsilon}\right)$ be a positive integer. Then \[a^{2^N} - b^{2^N} = (b+\varepsilon)^{2^N} - b^{2^N} \geq 2^N \cdot b^{2^N - 1} \cdot \varepsilon > 2\]by assumption of $N$ and $b > 1$. Finally, let $n = \left \lfloor a^{2^N} \right \rfloor$, so that \[f\left(a^{2^N} - n\right) = f\left(a^{2^N}\right) - n = b^{2^N} - n.\]But by definition of $n$, $a^{2^N} - n \geq 0$ and $b^{2^N} - n < 0$, hence contradiction! Remark: This problem is quite magical and in my opinion very difficult if one has not seem some kind of argument like this before. The idea is that each condition $f(g(x)) = g(f(x))$ only gives a ``countable" constraint on $f$, but $\left|\mathbb N^2\right| < |\mathbb R|$, so it is impossible to narrow down precisely what the values of $f$ are. (We can see the ``countability" of the constraint by noting that $f(g(x)) = g(f(x))$ will work as long as $f$ ``commutes" between the cycle graph of $g$.) For example, even if we take $(g, h) = \left(x+1, x^2\right)$, nothing ``should" go wrong if $f(\pi) = e$, $f(e) = \pi$, and $f(x) = x$ for all other $x$. But the choice of $h \equiv x^2$ allows us to do inequalities (i.e. the first claim), which is ultimately our most powerful tool.