AlgebraDifficulty 8.0National Olympiad, round 2Prove itUnited States
Does there exist a pair (g,h) of functions g,h:R→R such that the only function f:R→R satisfying f(g(x))=g(f(x)) and f(h(x))=h(f(x)) for all x∈R is the identity function f(x)=x? (This problem was suggested by Alexander Betts from the United Kingdom.)
Solution
Solution 1. We claim that g(x)=2x, h(x)=⌊x⌋−1 works. We must show that f(x)=x is the only solution to the system of equations 2f(x)=f(2x) f(⌊x⌋−1)=⌊f(x)⌋−1. for f(x). First, note that 2f(0)=f(0), so f(0)=0. Also, if n is an integer, then f(n)=⌊f(n+1)⌋−1, so f(n) is an integer. Therefore, we obtain that f(n)=⌊f(n+1)⌋−1=f(n+1)−1, which together with f(0)=0 gives f(n)=n for all integers n. Now, assume that there is some x with f(x)=x. Note that if ⌊a⌋=⌊b⌋, then by using the second equation for a and b we get ⌊f(a)⌋=⌊f(b)⌋. Now let f(x)=x+ϵ, where ∣ϵ∣>1/2k for a large enough integer k. Then, we obtain f(2kx)=2kx+2kϵ by the first equation. But then because ⌊2kx⌋=⌊2kx⌋, we have ⌊2kx⌋=⌊2kx+2kϵ⌋. But ⌊2kϵ⌋>1, a contradiction. We conclude that f(x)=x as desired.
Solution 2. The answer is yes. Let g(x)={x+1x+21if {x}<21if {x}≥21, and h(x)=2g(2x), where {x} denotes the fractional part of x. By Kronecker's theorem, if x is irrational and n ranges over the positive integers, then {nx} is dense in the unit interval. Observe that if x is in the range of g, then g(x)=x+1, and, if x is in the range of h, then h(x)=x+2. We now make the following observations.
a. If x is in the range of g, then so is f(x), because then x=g(x0) for some x0 and f(x)=f(g(x0))=g(f(x0)) by the given condition.
b. If x is in the range of g, then f(x+1)=f(g(x))=g(f(x))=f(x)+1, so f(x+n)=f(x)+n for all positive integers n.
Similarly, we notice that
c. If x is in the range of h, then so is f(x).
d. If x is in the range of h, then f(x+m2)=f(x)+m2 for all positive integers m.
We now show by contradiction that f(x)=x. Assume that there exist a=b such that f(a)=b. We divide into two cases.
Case 1: Suppose that a is in the range of both g and h. Then so is b and f(a+n)=b+n for all positive integers n. Since a and b are in the range of h we have {2a},{2b}<21. By Kronecker's theorem, we can find a positive integer n such that {2n} is in one of the intervals [21−{2b},21−{2a}) or [1−{2a},1−{2b}) unless 2a−b is an integer. In the first situation, we would have {2a+n}<21 and {2b+n}≥21, so a+n is in the range of h while b+n is not. But b+n=f(a+n), which contradicts (c).
Similarly by Kronecker's theorem, we obtain that there exists a positive integer m such that {a+m2}<21 and {b+m2}≥21, which violates (a) because f(a+m2)=b+m2 for all m, unless a−b is an integer. Thus, both a−b and 2a−b should be integers, which is clearly impossible.
Case 2: Suppose that a is in the range of g but not in the range of h. Then f(a+n)=b+n for all positive integers n. By Kronecker's theorem, there exists an n such that {2n} is in the interval (1−{2a},23−{2a}), so {2a+n}<21 and a+n is in the range of h. We can then use a+n as our a in Case 1 to rule out this case. The case where a is in the range of h but not g is similar.
Case 3: Suppose finally that a is in the range of neither g nor h. We have f(g(a))=g(a)=a+21 and f(g(a))=g(f(a))=f(a)+1, hence f(a)+21. Since f(a)=a, we have f(a)=a−21. But we also have f(h(a))=h(a)=a+22 and f(h(a))=h(f(a))=f(a)+2, which implies f(a)+22. We conclude that f(a)=a−22. 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) is always equal to a.
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.