Maths Olympiad Prep

Library / /2 of 2

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:RRg, h : \mathbb{R} \to \mathbb{R} such that the only function f:RRf : \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 xRx \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)=x1h(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(x1)=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 aba \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 ab2\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 aba-b is an integer. Thus, both aba-b and ab2\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)=a12f(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)=a22f(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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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