49th International Mathematical Olympiad Spain

We show that the answer is NO for part (a), and YES for part (b).

a. Throughout the solution, we will use the notation $g_k(x)=\stackrel{k}{\overbrace{g(g(\dots g}}(x)\dots ))$, including $g_0(x)=x$ as well. Suppose that there exists a Spanish Couple $(f,g)$ on the set $\mathbb{N}$. From property (i) we have $f(x)\ge x$ and $g(x)\ge x$ for all $x\in \mathbb{N}$.

We claim that $g_k(x)\le f(x)$ for all $k\ge 0$ and all positive integers $x$. The proof is done by induction on $k$. We already have the base case $k=0$ since $x\le f(x)$. For the induction step from $k$ to $k+1$, apply the induction hypothesis on $g_2(x)$ instead of $x$, then apply (ii): $$g\left(g_{k+1}(x)\right)=g_k\left(g_2(x)\right)\le f\left(g_2(x)\right)<g(f(x))$$ Since $g$ is increasing, it follows that $g_{k+1}(x)<f(x)$. The claim is proven.

If $g(x)=x$ for all $x\in \mathbb{N}$ then $f(g(g(x)))=f(x)=g(f(x))$, and we have a contradiction with (ii). Therefore one can choose an $x_0\in S$ for which $x_0<g\left(x_0\right)$. Now consider the sequence $x_0,x_1,\dots$ where $x_k=g_k\left(x_0\right)$. The sequence is increasing. Indeed, we have $x_0<g\left(x_0\right)=x_1$, and $x_k<x_{k+1}$ implies $x_{k+1}=g\left(x_k\right)<g\left(x_{k+1}\right)=x_{k+2}$.

Hence, we obtain a strictly increasing sequence $x_0<x_1<\dots$ of positive integers which on the other hand has an upper bound, namely $f\left(x_0\right)$. This cannot happen in the set $\mathbb{N}$ of positive integers, thus no Spanish Couple exists on $\mathbb{N}$.

b. We present a Spanish Couple on the set $S=\{a-1/b:a,b\in \mathbb{N}\}$. Let $$\begin{array}{rl}& f(a-1/b)=a+1-1/b\\ & g(a-1/b)=a-1/(b+3^a)\end{array}$$ These functions are clearly increasing. Condition (ii) holds, since $$f(g(g(a-1/b)))=(a+1)-1/(b+2\cdot 3^a)<(a+1)-1/(b+3^{a+1})=g(f(a-1/b))$$