1990 IMO Problems/Problem 4
Contents
Problem
Let be the set of positive rational numbers. Construct a function such that for all .
Solution
If we let this implies . Plugging in with this new fact. We get . Using again, we see that . Now plugging in we get . Such a function can not be continuous as if is increasing or decreasing on some observable interval, will be increasing on that interval but is decreasing on all positive intervals. This indicates the function is discrete which means we can assign a "4-chain" of , , , and . It is obvious to see that any function where . Must follow such a structure. The problem occurs that we do not know whether our current value of is a or an . To make non-trivial progress on this we must split all rational numbers into two sets, and , such that if then . As long as and have the same size, so the bijection = can hold, there will exist a piece-wise function (possibly with a greater than countable infinity number of pieces) that satisfies f(x).
To find one of these functions we can limit our searching by proving that . To do this simply set yielding: \newline . This means that . Since there will always be an that suffices this and a corresponding . Thus with expands into .
Utilizing we can see that if we break-down every ratio into it's prime factorization of the numerator and denominator. Our "4-chain" is simply , , , where and are unique primes. Thus our 2 sets and is simply 2 sets of equal size containing only primes and their inverse. A good way to do this assuming we aren't given the sequence of all infinite primes (as this would require an explicit formula that does not yet exist) is to split the primes into 2 and 1 mod 6 being in one set with 3 and 5 mod 6 in the other. These sets have equal sizes from a strong form of Dirichlet's theorem on arithmetic progressions.
Thus we have created our two sets and to show that this actually works we will let where is a prime and are integers. Define similarly. For the sake of simplicity if is odd then and if is even . Where our "4-chain" is , , , with being odd. Then (remember ).
Then
Thus QED
solution1
We show first that f(1) = 1. Taking x = y = 1, we have f(f(1)) = f(1). Hence f(1) = f(f(1)) = f(1 f(f(1)) ) = f(1)/f(1) = 1.
Next we show that f(xy) = f(x)f(y). For any y we have 1 = f(1) = f(1/f(y) f(y)) = f(1/f(y))/y, so if z = 1/f(y) then f(z) = y. Hence f(xy) = f(xf(z)) = f(x)/z = f(x) f(y).
Finally, f(f(x)) = f(1 f(x)) = f(1)/x = 1/x.
We are not required to find all functions, just one. So divide the primes into two infinite sets S = {p1, p2, ... } and T= {q1, q2, ... }. Define f(pn) = qn, and f(qn) = 1/pn. We extend this definition to all rationals using f(xy) = f(x) f(y): f(pi1pi2...qj1qj2.../(pk1...qm1...)) = pm1...qi1.../(pj1...qk1...). It is now trivial to verify that f(x f(y)) = f(x)/y.
See Also
1990 IMO (Problems) • Resources | ||
Preceded by Problem 3 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 5 |
All IMO Problems and Solutions |