Maths Olympiad Prep

Library / /87 of 92

Algebra Difficulty 7.6 National olympiad, round 2 Prove it Iran

Find all functions f:RAf : \mathbb{R} \to A such that

i. xf(y)x \in f(y) if and only if yf(x)y \in f(x).

ii. xy>2|x - y| > 2 if and only if f(x)f(y)=f(x) \cap f(y) = \emptyset.

iii. For all real numbers 0r10 \le r \le 1; f(r)=[r21,r2+1]f(r) = [r^2 - 1, r^2 + 1].

Solution

We shall firstly prove following lemmas;

Lemma 1. For any real number rr, the length of the interval f(r)f(r) is at most 2.
Proof. If x,yf(r)x, y \in f(r) we have rf(x)f(y)r \in f(x) \cap f(y) hence we have xy2|x - y| \le 2.

Lemma 2. If the interval II has length 2, then there is a real number rr such that f(r)=If(r) = I.
Proof. If I=[x,x+2]I = [x, x+2] then by condition 2 there is rf(x)f(x+2)r \in f(x) \cap f(x+2) so we have x,x+2f(r)x, x+2 \in f(r). But the length of f(r)f(r) is at most 2 hence we have f(r)=[x,x+2]f(r) = [x, x+2], this completes our proof.

Lemma 3. f is an injective function and for any r the length of f(r) is 2.
Proof. Using preceding lemmas it is enough to show that if f(x)f(y)f(x) \subset f(y) then x=yx = y. Assume the contrary, let II be an interval of length 2 such that xI,yIx \in I, y \notin I then by lemma 2 there exists rr such that I=f(r)I = f(r). Now we have rf(x),rf(y)r \in f(x), r \notin f(y) which contradicts f(x)f(y)f(x) \subset f(y).

Define a new function g:RRg: \mathbb{R} \to \mathbb{R} such that for all rr, g(r)g(r) is the midpoint of f(r)f(r). Since we know the length of f(r)f(r) we can forget about ff and work with gg. We apt to find all bijective functions gg such that:
i.xg(y)1    yg(x)1. i. \quad |x - g(y)| \le 1 \iff |y - g(x)| \le 1.
ii.g(x)g(y)2    xy2. ii. \quad |g(x) - g(y)| \le 2 \iff |x - y| \le 2.
iii.g(r)=r2 for all 0r1. iii. \quad g(r) = r^2 \text{ for all } 0 \le r \le 1.

Lemma 4. g is strictly increasing.
Proof. It suffices to prove if x<y,yx<1x < y, y - x < 1 then g(x)<g(y)g(x) < g(y). We firstly consider the case y=0y = 0. For each 2x0-2 \le x \le 0 by condition 2 and g(0)=0g(0) = 0 we have
g(x)g(2)>2,g(x)2,g(2)2 |g(x) - g(2)| > 2, |g(x)| \le 2, |g(2)| \le 2
so we can deduce that g(x)g(x) and g(2)g(2) have different signs, similarly we can deduce that g(2),g(1)=1g(2), g(1) = 1 have the same sign (they are both opposite to the sign of g(2)g(-2)). Hence we have g(2)>0,g(x)<0g(2) > 0, g(x) < 0.
We prove by induction on x\lfloor x \rfloor (We only prove the case that 0x<y0 \le x < y the other case is similar). For the base if 0x<y<10 \le x < y < 1 then x2<y2x^2 < y^2. We know that yx2>2y - x - 2 > 2 hence by the second condition we have
g(y)g(x2)>2,g(y)g(x)2,g(x)g(x2)2. |g(y) - g(x - 2)| > 2, |g(y) - g(x)| \le 2, |g(x) - g(x - 2)| \le 2.
We know by induction that g(x)g(x2)>0g(x) - g(x - 2) > 0 hence we have g(y)>g(x)g(y) > g(x).

Lemma 5. *we have g(x+1)=g1(x)+1g(x + 1) = g^{-1}(x) + 1.*
Proof. We know that gg is bijective so it suffices to prove that g(g(x)+1)=x+1g(g(x) + 1) = x + 1. Assume that g(r)=x+1g(r) = x + 1 then we have rg(x)+1r \le g(x) + 1. Now if r>rr' > r we have g(r)>x+1g(r') > x + 1 hence by condition 1; r>g(x)+1r' > g(x) + 1 so we get r=g(x)+1r = g(x) + 1.

By the last lemma we obtain that there is only one function that satisfies the condition of the problem and that function is:
g(x)={(xx)2+xx0(mod2);xx+xx1(mod2). g(x) = \begin{cases} (x - \lfloor x \rfloor)^2 + \lfloor x \rfloor & \lfloor x \rfloor \equiv 0 \pmod{2}; \\ \sqrt{x - \lfloor x \rfloor} + \lfloor x \rfloor & \lfloor x \rfloor \equiv 1 \pmod{2}. \end{cases}
It is easy to check that this function actually works. ■

Want a route through all this instead of 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.