For the second part, we can inductively construct $ g$ if we take $ f(x) = x + 1$. We well take any increasing function $ g$ in $ [0,1)$ for which $ g(x)$ stays in the same interval $ [0,1)$. Assume we constructed till $ [n,n + 1)$. Construction of $ g(x)$ for $ x$ being in $ [n + 1,n + 2)$ will be the following: Take $ g(n + 1)$ so that: 1) $ g(n + 1)$ is in $ S$; 2) $ g(n + 1) < n + 2$; 3) $ g(n + 1) > g(g(n)) + 1$; For any positive integer $ k$, take $ g(n + 2 - \frac {1}{k + 1})$ such that: 1) $ g(n + 2 - \frac {1}{k + 1})$ is in $ S$; 2) $ g(n + 2 - \frac {1}{k + 1}) < n + 2$; 3) $ g(n + 2 - \frac {1}{k + 1}) > g(n + 2 - \frac {1}{k}$; 4) $ g(n + 2 - \frac {1}{k + 1}) > g(g(n + 1 - \frac {1}{k + 1})) + 1$; Easy to verify that for this cinstruction of $ g$, it's from $ S$ to $ S$, it's scritly increasing and for any $ x$ from $ [n,n + 1)$, where $ n$ is nonnegative integer, $ g(n)$ is in $ [n,n + 1)$. Moreover, we have $ g(x + 1) > g(x) + 1$, for all $ x$ in $ S$. $ f$ is also from $ S$ to $ S$ and is strictly increasing as well. For any $ x$ in $ S$, we have $ f(g(g(x))) = g(g(x)) + 1 < g(x + 1) = g(f(x))$, as in condition. Hence, such a couple exists for $ S = \{a - \frac {1}{b}: a, b\in\mathbb{N}\}$.

Another solution to part ii) Let $(a,b)$ represent $a-\frac{1}{b}$. The construction $f(a,b)=(2a,b), g(a,b)=(a,b+(a-1))$ works too. This is inspired by the fact that you require $f(x) > g^n(x)$ for all $n$, so $g$ should not make any "hops" in the $a$-value, and also by the intuitive fact that applying $f$ then $g$ should make the number bigger than applying $g$ then $f$.

(i) Because it is increasing, $f(x),g(x) \ge x$ and so $g(f(x))>f(g^2(x)) \ge g^2(x) \Rightarrow f(x)>g(x)$. Repeating this argument, $g(f(x))>f(g^2(x)) > g(g^2(x))=g^3(x) \Rightarrow f(x) > g^2(x)$, and, inductively, $f(x) > g^n(x)$ for any natural $n$. If $g(x) \neq x$ then $g(x) > x$, and $g(g(x))>g(x)$ because it is increasing and so inductively $g^n(x) > g^{n-1}(x)$ and so $f(x) > g^{f(x)}(x) \ge g^{f(x)-1}(x) +1 \ge ... \ge g(x)+(f(x)-1) \ge f(x)$, a contradiction. Then $g(x)=x$ for all $x$ and plugging in, $f(x)>f(x)$, a contradiction. They don't exist. (ii) Notice that our set is basically equivalent to $\{wn+m : n\ge 0, m \ge 1 \}$, where $w$ is the first infinite ordinal number. Let $f(wn+m)=w(n+1)+m$, and $g(wn+m)=wn+(m+3^n)$, so that $g$ grows faster the bigger $n$ is. Then $f(g(g(wn+m))) = f(g(wn+m+3^n))=f(wn+m+2*3^n) = w(n+1)+m+2*3^n$ and $g(f(wn+m))=g(w(n+1)+m)=w(n+1)+m+3^{n+1}$ and so $ g(f(x))=w(n+1)+m+3^{n+1} > w(n+1)+m+2*3^n = f(g(g(wn+m)))$, and they satisfy.

Has anyone seen a smilier problem before at an earlier competition?

LMat wrote: Has anyone seen a smilier problem before at an earlier competition? No, I haven't. That's an excellent problem, fresh and original. It's a pity that it did not get selected.

Nice problem! Here's my solution: (i) We claim that Spanish Couples cease to exist naturally (pun intended!). FTSOC assume there is such a Spanish Couple $(f,g)$. The crucial observation is that any strictly increasing function $h: \mathbb{N} \mapsto \mathbb{N}$ satisfies $h(x) \geq x$ (since otherwise the smaller values have to map into an even smaller set, and so two of them must coincide, which is not possible). Using this deep fact, we propose the following Lemma- LEMMA Given a positive integer $k$, we have $f(x)>g^k(x)$ for all $x \in \mathbb{N}$. Proof of Lemma We proceed by induction on $k \geq 1$. Using the deep fact, we get $$g(g(x)) \leq f(g(g(x)))<g(f(x)) \Rightarrow g(x)<f(x)$$proving the base case. Now, suppose the result is true for some $k$. Then, since $f(x)>g^k(x)$ for all $x \in \mathbb{N}$, so we have $$g(f(x))>f(g(g(x)))>g^{k+2}(x) \Rightarrow f(x)>g^{k+1}(x)$$competing the induction step. $\Box$ Return to the problem at hand. If $g=\text{id}$, then the given condition translates to $f(x)<f(x)$, which is not possible. So there exists some $x_0 \in \mathbb{N}$ satisfying $g(x_0)>x_0$. Let $f(x_0)-x_0=m$, where $m \geq 0$. Applying the Lemma for $k=m+1$, we get $$f(x_0)>g^{m+1}(x_0) \geq g^m(x_0)+1 \geq g^{m-1}(x_0)+2 \geq \dots \geq g(x_0)+m$$But, since $f(x_0)=x_0+m$, so the above inequality gives $x_0>g(x_0)$, a contradiction. Thus, all Spanish Couples are unnatural. (ii) For any $a,b \in \mathbb{N}$, and some fixed positive integer $n>1$, let $$f \left(a-\frac{1}{b} \right)=na-\frac{1}{b} \text{ and } g \left(a-\frac{1}{b} \right)=a-\frac{1}{b+\rho(a)}$$where $\rho:\mathbb{N} \mapsto \mathbb{N}$ is some function. It's easy to see that both $f,g$ are strictly increasing. Then $$f \left(g \left(g \left(a-\frac{1}{b} \right) \right) \right)=na-\frac{1}{b+2\rho(a)}$$$$\text{and}$$$$g \left(f \left(a-\frac{1}{b} \right) \right)=na-\frac{1}{b+\rho(na)}$$So we want $$na-\frac{1}{b+2\rho(a)}<na-\frac{1}{b+\rho(na)} \iff \rho(na)>2 \rho(a)$$So our aim is to show the existence of such a function $\rho$ for some $n$. But taking any $n>2$ and $\rho(a)=a$ does the deed. $\blacksquare$

Redacted due to mistake

April wrote: Let $ S\subseteq\mathbb{R}$ be a set of real numbers. We say that a pair $ (f, g)$ of functions from $ S$ into $ S$ is a Spanish Couple on $ S$, if they satisfy the following conditions: (i) Both functions are strictly increasing, i.e. $ f(x) < f(y)$ and $ g(x) < g(y)$ for all $ x$, $ y\in S$ with $ x < y$; (ii) The inequality $ f\left(g\left(g\left(x\right)\right)\right) < g\left(f\left(x\right)\right)$ holds for all $ x\in S$. Decide whether there exists a Spanish Couple on the set $ S = \mathbb{N}$ of positive integers; on the set $ S = \{a - \frac {1}{b}: a, b\in\mathbb{N}\}$ Proposed by Hans Zantema, Netherlands Solved with Rg230403 and MathPassionForever (a) We claim that no spanish couples exist if $S=\mathbb{N}$ .Assume to the contrary that there are functions $(f,g)$ satisfying the assertion. Then note that since $f,g$ are increasing functions on $\mathbb{N}$ so $f(x)\geq x$ and $g(x)\geq x$ Claim : $f(x) > g^k(x)$ for all $k\geq 1$ Proof Since $g(f(x))>f(g(g(x)))\geq g(g(x))\Longleftrightarrow f(x) > g(x)$ . Plugging back we have $$g(f(x))>f(g(g(x)))>g(g(g(x)))\implies f(x)>g^2(x)$$and now a simple induction proves the claim.$\square$ Now if there exists a $x\in\mathbb{N}$ such that $g(x)>x$ and let $\chi=f(x)-x$.Thus $$f(x)>g^{x}(x)\geq 1+g^{\chi-1}(x)\geq 2+g^{\chi-2}(x)\cdots > \chi+x =f(x)$$a contradiction.$\square$ (b)The answer is Yes for this case.The following construction works:- $f\left(a-\dfrac{1}{b}\right)=a+1-\dfrac{1}{b} $ ; $ g\left(a-\dfrac{1}{b}\right)=a-\dfrac{1}{b+3^a}$.Indeed $$f(g(g(x)))=f\left(g\left(g\left(a-\dfrac{1}{b}\right)\right)\right)=a+1-\dfrac{1}{b+2\cdot 3^a}<a+1-\dfrac{1}{b+3^{a+1}}=g\left(f\left(a-\dfrac{1}{b}\right)\right)=g(f(x))$$so we are done.$\blacksquare$

i: The answer is no. Obviously if $g,f\ge \text{id}$. If $g(g(x))\le g(f(x))$ we immediately die, and therefore $f(x)>g(x)$. Now, we claim that $f(x)>g^n(x)$ for all natural $n$ by induction. The base case, $n=1$, is proven. For the inductive step assume the hypothesis true for $n=N$; notice that $g(f(x))>g^{N+2}(x)$ because $f(g^2(x))>g^{N+2}(x)$. If $g$ is not the identity, we die here. Otherwise, we just get $f(x)<f(x)$ which is false. ii. The answer is yes. Consider $f(a-\frac{1}{b})=a-\frac{1}{3b},g(a-\frac{1}{b})=a+187b-\frac{1}{b}$. The LHS becomes $a+374b-\frac{1}{3b}$, while the RHS becomes $a+561b-\frac{1}{3b}$.

Very original problem as pointed out by #6 and #7. Here is a solution with some motivation. As always, let $g^n(x) = g^{n-1}(g(x))$ for all $n \in \mathbb{N}$.

$\textbf{Part 2)}$

Let $f(x) = x+1$ and $g(a-\frac{1}{b}) = a-\frac{1}{b+3^a}$, we can indeed verify that for all $a,b \in \mathbb{N}$ $$g(f(a-\frac{1}{b})) > a+1- \frac{1}{b+3^{a+1}}> a+1-\frac{1}{b+2 \cdot 3^a} = f(g(g(a-\frac{1}{b})))$$meaning that $(f,g)$ are a Spanish pair for $S = \{a- \frac{1}{b}|a,b \in \mathbb{N} \}$. $\blacksquare$

When only positive integers are in question, we have $f(x)\ge x.$ Thus, $g(g(x))\le f(g(g(x)))<g(f(x))$ which implies $g(x)<f(x).$ Now, $f(g(g(x)))<g(f(x))<f(f(x))$ so $g(g(x))<f(x).$ $~$ If $g^n(x)<f(x)$, then $g^n(g^2(x))<f(g(g(x)))<g(f(x))$ implies $g^{n+1}(x)<f(x),$ absurd. Thus, $f(x)>g^n(x)$ for all $x.$ If $g(k)>k$, then $g^n(k)>n+k$ but increasing $n$ will eventually make $f(x)\le g^n(x).$ Thus, $g(x)=x$ which implies $f(x)<f(x)$, impossible. $~$ Let $f(x)=x+2\lceil x\rceil = 3a-\frac{1}{b}$ and $g(x)=a-\frac{1}{a+b}$ works.

For the first part, repeatedly substituting $x=g(g(x))$ and noting that $f(x)\ge x$ we obtain \[g^{2k}(x)\le f(g^{2k}(x))<g^k(f(x))\implies g^k(x)<f(x)\]for all $k\ge 1$. Therefore we can choose arbitrarily large $x$ where $g(x)=x$ which implies $g(x)=x$ for all $x$, a contradiction. For the second part, take $f\left(a-\frac{1}{b}\right)=(a+1)-\frac{1}{b}$ and $g\left(a-\frac{1}{b}\right)=a-\frac{1}{b+(2^a-1)}$.