Maths Olympiad Prep

Library / RMM /2 of 2

RMM

Algebra Difficulty 8.0 National Olympiad, round 2 Prove it United States

Does there exist a pair (g,h)(g, h) of functions g,h:R→Rg, h : \mathbb{R} \to \mathbb{R} such that the only function f:R→Rf : \mathbb{R} \to \mathbb{R} satisfying f(g(x))=g(f(x))f(g(x)) = g(f(x)) and f(h(x))=h(f(x))f(h(x)) = h(f(x)) for all x∈Rx \in \mathbb{R} is the identity function f(x)=xf(x) = x?
(This problem was suggested by Alexander Betts from the United Kingdom.)

Solution

Solution 1. We claim that g(x)=2xg(x) = 2x, h(x)=⌊x⌋−1h(x) = \lfloor x \rfloor - 1 works. We must show that f(x)=xf(x) = x is the only solution to the system of equations
2f(x)=f(2x) 2f(x) = f(2x)
f(⌊x⌋−1)=⌊f(x)⌋−1. f(\lfloor x \rfloor - 1) = \lfloor f(x) \rfloor - 1.
for f(x)f(x). First, note that 2f(0)=f(0)2f(0) = f(0), so f(0)=0f(0) = 0. Also, if nn is an integer, then f(n)=⌊f(n+1)⌋−1f(n) = \lfloor f(n+1) \rfloor - 1, so f(n)f(n) is an integer. Therefore, we obtain that
f(n)=⌊f(n+1)⌋−1=f(n+1)−1, f(n) = \lfloor f(n + 1) \rfloor - 1 = f(n + 1) - 1,
which together with f(0)=0f(0) = 0 gives f(n)=nf(n) = n for all integers nn.
Now, assume that there is some xx with f(x)≠xf(x) \neq x. Note that if ⌊a⌋=⌊b⌋\lfloor a \rfloor = \lfloor b \rfloor, then by using the second equation for aa and bb we get ⌊f(a)⌋=⌊f(b)⌋\lfloor f(a) \rfloor = \lfloor f(b) \rfloor. Now let f(x)=x+ϵf(x) = x + \epsilon, where ∣ϵ∣>1/2k|\epsilon| > 1/2^k for a large enough integer kk. Then, we obtain f(2kx)=2kx+2kϵf(2^k x) = 2^k x + 2^k \epsilon by the first equation. But then because ⌊2kx⌋=⌊2kx⌋\lfloor 2^k x \rfloor = \lfloor 2^k x \rfloor, we have ⌊2kx⌋=⌊2kx+2kϵ⌋\lfloor 2^k x \rfloor = \lfloor 2^k x + 2^k \epsilon \rfloor. But ⌊2kϵ⌋>1\lfloor 2^k \epsilon \rfloor > 1, a contradiction. We conclude that f(x)=xf(x) = x as desired.

Solution 2. The answer is yes. Let
g(x)={x+1if {x}<12x+12if {x}≥12, g(x) = \begin{cases} x + 1 & \text{if } \{x\} < \frac{1}{2} \\ x + \frac{1}{2} & \text{if } \{x\} \ge \frac{1}{2}, \end{cases}
and
h(x)=2g(x2), h(x) = \sqrt{2} g \left( \frac{x}{\sqrt{2}} \right),
where {x}\{x\} denotes the fractional part of xx. By Kronecker's theorem, if xx is irrational and nn ranges over the positive integers, then {nx}\{nx\} is dense in the unit interval. Observe that if xx is in the range of gg, then g(x)=x+1g(x) = x + 1, and, if xx is in the range of hh, then h(x)=x+2h(x) = x + \sqrt{2}. We now make the following observations.

a. If xx is in the range of gg, then so is f(x)f(x), because then x=g(x0)x = g(x_0) for some x0x_0 and f(x)=f(g(x0))=g(f(x0))f(x) = f(g(x_0)) = g(f(x_0)) by the given condition.

b. If xx is in the range of gg, then f(x+1)=f(g(x))=g(f(x))=f(x)+1f(x+1) = f(g(x)) = g(f(x)) = f(x)+1, so f(x+n)=f(x)+nf(x+n) = f(x)+n for all positive integers nn.

Similarly, we notice that

c. If xx is in the range of hh, then so is f(x)f(x).

d. If xx is in the range of hh, then f(x+m2)=f(x)+m2f(x+m\sqrt{2}) = f(x) + m\sqrt{2} for all positive integers mm.

We now show by contradiction that f(x)=xf(x) = x. Assume that there exist a≠ba \neq b such that f(a)=bf(a) = b. We divide into two cases.

Case 1: Suppose that aa is in the range of both gg and hh. Then so is bb and f(a+n)=b+nf(a+n) = b+n for all positive integers nn. Since aa and bb are in the range of hh we have
{a2},{b2}<12. \left\{ \frac{a}{\sqrt{2}} \right\}, \left\{ \frac{b}{\sqrt{2}} \right\} < \frac{1}{2}.
By Kronecker's theorem, we can find a positive integer nn such that {n2}\left\{ \frac{n}{\sqrt{2}} \right\} is in one of the intervals
[12−{b2},12−{a2}) or [1−{a2},1−{b2}) \left[ \frac{1}{2} - \left\{ \frac{b}{\sqrt{2}} \right\} , \frac{1}{2} - \left\{ \frac{a}{\sqrt{2}} \right\} \right) \text{ or } \left[ 1 - \left\{ \frac{a}{\sqrt{2}} \right\} , 1 - \left\{ \frac{b}{\sqrt{2}} \right\} \right)
unless a−b2\frac{a-b}{\sqrt{2}} is an integer. In the first situation, we would have {a+n2}<12\left\{ \frac{a+n}{\sqrt{2}} \right\} < \frac{1}{2} and {b+n2}≥12\left\{ \frac{b+n}{\sqrt{2}} \right\} \geq \frac{1}{2}, so a+na+n is in the range of hh while b+nb+n is not. But b+n=f(a+n)b+n = f(a+n), which contradicts (c).

Similarly by Kronecker's theorem, we obtain that there exists a positive integer mm such that {a+m2}<12\{a+m\sqrt{2}\} < \frac{1}{2} and {b+m2}≥12\{b+m\sqrt{2}\} \geq \frac{1}{2}, which violates (a) because f(a+m2)=b+m2f(a+m\sqrt{2}) = b+m\sqrt{2} for all mm, unless a−ba-b is an integer. Thus, both a−ba-b and a−b2\frac{a-b}{\sqrt{2}} should be integers, which is clearly impossible.

Case 2: Suppose that aa is in the range of gg but not in the range of hh. Then f(a+n)=b+nf(a+n) = b+n for all positive integers nn. By Kronecker's theorem, there exists an nn such that {n2}\{\frac{n}{\sqrt{2}}\} is in the interval
(1−{a2},32−{a2}), \left( 1 - \left\{ \frac{a}{\sqrt{2}} \right\} , \frac{3}{2} - \left\{ \frac{a}{\sqrt{2}} \right\} \right),
so {a+n2}<12\{\frac{a+n}{\sqrt{2}}\} < \frac{1}{2} and a+na+n is in the range of hh. We can then use a+na+n as our aa in Case 1 to rule out this case. The case where aa is in the range of hh but not gg is similar.

Case 3: Suppose finally that aa is in the range of neither gg nor hh. We have f(g(a))=g(a)=a+12f(g(a)) = g(a) = a + \frac{1}{2} and f(g(a))=g(f(a))=f(a)+1f(g(a)) = g(f(a)) = f(a) + 1, hence f(a)+12f(a) + \frac{1}{2}. Since f(a)≠af(a) \neq a, we have f(a)=a−12f(a) = a - \frac{1}{2}. But we also have f(h(a))=h(a)=a+22f(h(a)) = h(a) = a + \frac{\sqrt{2}}{2} and f(h(a))=h(f(a))=f(a)+2f(h(a)) = h(f(a)) = f(a) + \sqrt{2}, which implies f(a)+22f(a) + \frac{\sqrt{2}}{2}. We conclude that f(a)=a−22f(a) = a - \frac{\sqrt{2}}{2}. We thus obtained a contradiction that rules out this case as well.

We have thus obtained a contradiction in each case, and hence f(a)f(a) is always equal to aa.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.