Difference between revisions of "1990 IMO Problems/Problem 4"
(→Solution) |
|||
(4 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
− | + | ==Problem== | |
+ | Let <math>\mathbb{Q^+}</math> be the set of positive rational numbers. Construct a function <math>f :\mathbb{Q^+}\rightarrow\mathbb{Q^+}</math> such that <math>f(xf(y)) = \frac{f(x)}{y}</math> for all <math>x, y\in{Q^+}</math>. | ||
+ | |||
+ | ==Solution== | ||
+ | If we let <math>y = x = 1</math> this implies <math>f(f(1)) = f(1)</math>. Plugging <math>f(1) = y</math> in with this new fact. We get <math>f(f(f(1))) = \frac{f(1)}{f(1)} = 1</math>. Using <math>f(f(1)) = f(1)</math> again, we see that <math>f(f(f(1))) = f(f(1)) = f(1) = 1</math>. Now plugging in <math>x = 1</math> we get <math>f(f(y)) = \frac{1}{y}</math>. Such a function can not be continuous as if <math>f(x)</math> is increasing or decreasing on some observable interval, <math>f(f(x))</math> will be increasing on that interval but <math>\frac{1}{x}</math> is decreasing on all positive intervals. This indicates the function is discrete which means we can assign a "4-chain" of <math>f(a) = b</math>, <math>f(b) = \frac{1}{a}</math>, <math>f(\frac{1}{a}) = \frac{1}{b}</math>, and <math>f(\frac{1}{b}) = a</math>. It is obvious to see that any function where <math>f(f(x)) = \frac{1}{x}</math>. Must follow such a structure. The problem occurs that we do not know whether our current value of <math>x</math> is a <math>b</math> or an <math>a</math>. To make non-trivial progress on this we must split all rational numbers into two sets, <math>S_1</math> and <math>S_2</math>, such that if <math>E \in S_1</math> then <math>\frac{1}{E} \in S_1</math>. As long as <math>S_1</math> and <math>S_2</math> have the same size, so the bijection <math>f(\textrm{an element from }S_1)</math> = <math>(\textrm{an element from } S_2)</math> 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 <math>f(ab) = f(a)f(b)</math>. To do this simply set <math>x = \frac{1}{f(y)}</math> yielding: | ||
+ | \newline | ||
+ | <math>f(1) = f(f(y) \times \frac{1}{f(y)}) = \frac{f(\frac{1}{f(y)})}{y} = 1</math>. This means that <math>f(x) = y</math>. Since <math>X,Y \in Q+</math> there will always be an <math>x</math> that suffices this and a corresponding <math>y</math>. Thus <math>f(ab)</math> with <math>b = f(c)</math> <math>\leftrightarrow</math> <math>c = \frac{1}{f(b)}</math> expands into <math>f(af(c)) = \frac{f(a)}{c} = f(a)f(b)</math>. | ||
+ | |||
+ | Utilizing <math>f(ab) = f(a)f(b)</math> 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 <math>f(p) = q</math>, <math>f(q) = \frac{1}{p}</math>, <math>f(\frac{1}{p}) = \frac{1}{q}</math>, <math>f(\frac{1}{q}) = p</math> where <math>p</math> and <math>q</math> are unique primes. Thus our 2 sets <math>S_1</math> and <math>S_2</math> 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 <math>x = P_1^{E_{1x}} \times P_2^{E_{2x}} \times P_3^{E_{3x}} \times \dots</math> where <math>P_i</math> is a prime and <math>E_{ix}</math> are integers. Define <math>y</math> similarly. For the sake of simplicity if <math>i</math> is odd then <math>P_i \in S_1</math> and if <math>i</math> is even <math>P_i \in S_2</math>. Where our "4-chain" is <math>f(p_n) = p_{n+1}</math>, <math>f(p_{n+1}) = \frac{1}{p_n}</math>, <math>f(\frac{1}{p_n}) = \frac{1}{p_{n+1}}</math>, <math>f(\frac{1}{p_{n+1}}) = p_n</math> with <math>n</math> being odd. Then <math>f(y) = P_2^{E_{1y}} \times P_1^{-E_{2y}} \times P_4^{E_{3y}} \times P_3^{-E_{4y}}\dots</math> (remember <math>f(ab) = f(a)f(b)</math>). | ||
+ | |||
+ | Then <math>xf(y) = P_1^{E_{1x} - E_{2y}} \times P_2^{E_{2x} + E_{1y}} \times P_3^{E_{3x} - E_{4y}} \times \dots</math> | ||
+ | |||
+ | <math>f(xf(y)) = P_2^{E_{1x} - E_{2y}} \times P_1^{-E_{2x} - E_{1y}} \times P_4^{E_{3x} - E_{4y}} \times P_3^{-E_{4x} - E_{3y}} \dots</math> | ||
+ | |||
+ | <math>f(x) = P_2^{E_{1x}} \times P_1^{-E_{2x}} \times P_4^{E_{3x}} \times P_3^{-E_{4x}}\dots</math> | ||
+ | |||
+ | <math>\frac{f(x)}{y} = P_2^{E_{1x}- E_{2y}} \times P_1^{-E_{2x} - E_{1y}} \times P_4^{E_{3x} - E_{4y}} \times P_3^{-E_{4x} - E_{3y}}\dots</math> | ||
+ | |||
+ | Thus <math>f(xf(y)) = \frac{f(x)}{y}</math> 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 == {{IMO box|year=1990|num-b=3|num-a=5}} | ||
+ | |||
+ | |||
+ | [[Category:Olympiad Algebra Problems]] | ||
+ | [[Category:Functional Equation Problems]] |
Latest revision as of 11:01, 30 September 2022
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 |