Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1990 IMO Problems/Problem 4"
(→‎Solution)
 
(One intermediate revision by one other user not shown)
Line 9: Line 9:
 
<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>.
 
<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. 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.
+
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>).  
 
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>).  
−
\newline
+
 
 
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>
 
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>
−
\newline
+
 
 
<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(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>
−
\newline
+
 
 
<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>f(x) = P_2^{E_{1x}} \times P_1^{-E_{2x}} \times P_4^{E_{3x}} \times P_3^{-E_{4x}}\dots</math>
−
\newline
+
 
 
<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>
 
<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>
−
\newline
+
 
 
Thus <math>f(xf(y)) = \frac{f(x)}{y}</math> QED
 
Thus <math>f(xf(y)) = \frac{f(x)}{y}</math> QED
−
{{solution}}
+
 
 +
==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}}
 
== See Also == {{IMO box|year=1990|num-b=3|num-a=5}}
 +
  
 
[[Category:Olympiad Algebra Problems]]
 
[[Category:Olympiad Algebra Problems]]
 
[[Category:Functional Equation Problems]]
 
[[Category:Functional Equation Problems]]

Latest revision as of 10:01, 30 September 2022

Problem

Let $\mathbb{Q^+}$ be the set of positive rational numbers. Construct a function $f :\mathbb{Q^+}\rightarrow\mathbb{Q^+}$ such that $f(xf(y)) = \frac{f(x)}{y}$ for all $x, y\in{Q^+}$.

Solution

If we let $y = x = 1$ this implies $f(f(1)) = f(1)$. Plugging $f(1) = y$ in with this new fact. We get $f(f(f(1))) = \frac{f(1)}{f(1)} = 1$. Using $f(f(1)) = f(1)$ again, we see that $f(f(f(1))) = f(f(1)) = f(1) = 1$. Now plugging in $x = 1$ we get $f(f(y)) = \frac{1}{y}$. Such a function can not be continuous as if $f(x)$ is increasing or decreasing on some observable interval, $f(f(x))$ will be increasing on that interval but $\frac{1}{x}$ is decreasing on all positive intervals. This indicates the function is discrete which means we can assign a "4-chain" of $f(a) = b$, $f(b) = \frac{1}{a}$, $f(\frac{1}{a}) = \frac{1}{b}$, and $f(\frac{1}{b}) = a$. It is obvious to see that any function where $f(f(x)) = \frac{1}{x}$. Must follow such a structure. The problem occurs that we do not know whether our current value of $x$ is a $b$ or an $a$. To make non-trivial progress on this we must split all rational numbers into two sets, $S_1$ and $S_2$, such that if $E \in S_1$ then $\frac{1}{E} \in S_1$. As long as $S_1$ and $S_2$ have the same size, so the bijection $f(\textrm{an element from }S_1)$ = $(\textrm{an element from } S_2)$ 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 $f(ab) = f(a)f(b)$. To do this simply set $x = \frac{1}{f(y)}$ yielding: \newline $f(1) = f(f(y) \times \frac{1}{f(y)}) = \frac{f(\frac{1}{f(y)})}{y} = 1$. This means that $f(x) = y$. Since $X,Y \in Q+$ there will always be an $x$ that suffices this and a corresponding $y$. Thus $f(ab)$ with $b = f(c)$ $\leftrightarrow$ $c = \frac{1}{f(b)}$ expands into $f(af(c)) = \frac{f(a)}{c} = f(a)f(b)$.

Utilizing $f(ab) = f(a)f(b)$ 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 $f(p) = q$, $f(q) = \frac{1}{p}$, $f(\frac{1}{p}) = \frac{1}{q}$, $f(\frac{1}{q}) = p$ where $p$ and $q$ are unique primes. Thus our 2 sets $S_1$ and $S_2$ 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 $x = P_1^{E_{1x}} \times P_2^{E_{2x}} \times P_3^{E_{3x}} \times \dots$ where $P_i$ is a prime and $E_{ix}$ are integers. Define $y$ similarly. For the sake of simplicity if $i$ is odd then $P_i \in S_1$ and if $i$ is even $P_i \in S_2$. Where our "4-chain" is $f(p_n) = p_{n+1}$, $f(p_{n+1}) = \frac{1}{p_n}$, $f(\frac{1}{p_n}) = \frac{1}{p_{n+1}}$, $f(\frac{1}{p_{n+1}}) = p_n$ with $n$ being odd. Then $f(y) = P_2^{E_{1y}} \times P_1^{-E_{2y}} \times P_4^{E_{3y}} \times P_3^{-E_{4y}}\dots$ (remember $f(ab) = f(a)f(b)$).

Then $xf(y) = P_1^{E_{1x} - E_{2y}} \times P_2^{E_{2x} + E_{1y}} \times P_3^{E_{3x} - E_{4y}} \times \dots$

$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$

$f(x) = P_2^{E_{1x}} \times P_1^{-E_{2x}} \times P_4^{E_{3x}} \times P_3^{-E_{4x}}\dots$

$\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$

Thus $f(xf(y)) = \frac{f(x)}{y}$ 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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1990_IMO_Problems/Problem_4&oldid=178566"