Olympiad Maths Prep

Library / /7 of 14

Algebra Difficulty 8.7 Shortlist Prove it IMO

Let f:RNf: \mathbb{R} \rightarrow \mathbb{N} be a function which satisfies
f(x+1f(y))=f(y+1f(x)) for all x,yR f\left(x+\frac{1}{f(y)}\right)=f\left(y+\frac{1}{f(x)}\right) \quad \text{ for all } x, y \in \mathbb{R}
Prove that there is a positive integer which is not a value of ff.

Solution

Suppose that the statement is false and f(R)=Nf(\mathbb{R})=\mathbb{N}. We prove several properties of the function ff in order to reach a contradiction.

To start with, observe that one can assume f(0)=1f(0)=1. Indeed, let aRa \in \mathbb{R} be such that f(a)=1f(a)=1, and consider the function g(x)=f(x+a)g(x)=f(x+a). By substituting x+ax+a and y+ay+a for xx and yy in (1), we have
g(x+1g(y))=f(x+a+1f(y+a))=f(y+a+1f(x+a))=g(y+1g(x)). g\left(x+\frac{1}{g(y)}\right)=f\left(x+a+\frac{1}{f(y+a)}\right)=f\left(y+a+\frac{1}{f(x+a)}\right)=g\left(y+\frac{1}{g(x)}\right) .
So gg satisfies the functional equation (1), with the additional property g(0)=1g(0)=1. Also, gg and ff have the same set of values: g(R)=f(R)=Ng(\mathbb{R})=f(\mathbb{R})=\mathbb{N}. Henceforth we assume f(0)=1f(0)=1.

Claim 1. For an arbitrary fixed cRc \in \mathbb{R} we have {f(c+1n):nN}=N\left\{f\left(c+\frac{1}{n}\right): n \in \mathbb{N}\right\}=\mathbb{N}.

Proof. Equation (1) and f(R)=Nf(\mathbb{R})=\mathbb{N} imply
f(R)={f(x+1f(c)):xR}={f(c+1f(x)):xR}{f(c+1n):nN}f(R)f(\mathbb{R})=\left\{f\left(x+\frac{1}{f(c)}\right): x \in \mathbb{R}\right\}=\left\{f\left(c+\frac{1}{f(x)}\right): x \in \mathbb{R}\right\} \subset\left\{f\left(c+\frac{1}{n}\right): n \in \mathbb{N}\right\} \subset f(\mathbb{R}).
The claim follows.

We will use Claim 1 in the special cases c=0c=0 and c=1/3c=1 / 3 :
{f(1n):nN}={f(13+1n):nN}=N. \left\{f\left(\frac{1}{n}\right): n \in \mathbb{N}\right\}=\left\{f\left(\frac{1}{3}+\frac{1}{n}\right): n \in \mathbb{N}\right\}=\mathbb{N} .

Claim 2. If f(u)=f(v)f(u)=f(v) for some u,vRu, v \in \mathbb{R} then f(u+q)=f(v+q)f(u+q)=f(v+q) for all nonnegative rational qq. Furthermore, if f(q)=1f(q)=1 for some nonnegative rational qq then f(kq)=1f(k q)=1 for all kNk \in \mathbb{N}.

Proof. For all xRx \in \mathbb{R} we have by (1)
f(u+1f(x))=f(x+1f(u))=f(x+1f(v))=f(v+1f(x)) f\left(u+\frac{1}{f(x)}\right)=f\left(x+\frac{1}{f(u)}\right)=f\left(x+\frac{1}{f(v)}\right)=f\left(v+\frac{1}{f(x)}\right)
Since f(x)f(x) attains all positive integer values, this yields f(u+1/n)=f(v+1/n)f(u+1 / n)=f(v+1 / n) for all nNn \in \mathbb{N}. Let q=k/nq=k / n be a positive rational number. Then kk repetitions of the last step yield
f(u+q)=f(u+kn)=f(v+kn)=f(v+q) f(u+q)=f\left(u+\frac{k}{n}\right)=f\left(v+\frac{k}{n}\right)=f(v+q)
Now let f(q)=1f(q)=1 for some nonnegative rational qq, and let kNk \in \mathbb{N}. As f(0)=1f(0)=1, the previous conclusion yields successively f(q)=f(2q),f(2q)=f(3q),,f((k1)q)=f(kq)f(q)=f(2 q), f(2 q)=f(3 q), \ldots, f((k-1) q)=f(k q), as needed.

Claim 3. The equality f(q)=f(q+1)f(q)=f(q+1) holds for all nonnegative rational qq.

Proof. Let mm be a positive integer such that f(1/m)=1f(1 / m)=1. Such an mm exists by (2). Applying the second statement of Claim 2 with q=1/mq=1 / m and k=mk=m yields f(1)=1f(1)=1.
Given that f(0)=f(1)=1f(0)=f(1)=1, the first statement of Claim 2 implies f(q)=f(q+1)f(q)=f(q+1) for all nonnegative rational qq.

Claim 4. The equality f(1n)=nf\left(\frac{1}{n}\right)=n holds for every nNn \in \mathbb{N}.

Proof. For a nonnegative rational qq we set x=q,y=0x=q, y=0 in (1) and use Claim 3 to obtain
f(1f(q))=f(q+1f(0))=f(q+1)=f(q). f\left(\frac{1}{f(q)}\right)=f\left(q+\frac{1}{f(0)}\right)=f(q+1)=f(q) .
By (2), for each nNn \in \mathbb{N} there exists a kNk \in \mathbb{N} such that f(1/k)=nf(1 / k)=n. Applying the last equation with q=1/kq=1 / k, we have
n=f(1k)=f(1f(1/k))=f(1n). n=f\left(\frac{1}{k}\right)=f\left(\frac{1}{f(1 / k)}\right)=f\left(\frac{1}{n}\right) .
Now we are ready to obtain a contradiction. Let nNn \in \mathbb{N} be such that f(1/3+1/n)=1f(1 / 3+1 / n)=1. Such an nn exists by (2). Let 1/3+1/n=s/t1 / 3+1 / n=s / t, where s,tNs, t \in \mathbb{N} are coprime. Observe that t>1t>1 as 1/3+1/n1 / 3+1 / n is not an integer. Choose k,lNk, l \in \mathbb{N} so that that kslt=1k s-l t=1.
Because f(0)=f(s/t)=1f(0)=f(s / t)=1, Claim 2 implies f(ks/t)=1f(k s / t)=1. Now f(ks/t)=f(1/t+l)f(k s / t)=f(1 / t+l); on the other hand f(1/t+l)=f(1/t)f(1 / t+l)=f(1 / t) by ll successive applications of Claim 3. Finally, f(1/t)=tf(1 / t)=t by Claim 4, leading to the impossible t=1t=1. The solution is complete.

Looking for a route rather than an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.