Find all functions $f: \mathbb R^+ \rightarrow \mathbb R^+$ satisfying the following condition: for any three distinct real numbers $a,b,c$, a triangle can be formed with side lengths $a,b,c$, if and only if a triangle can be formed with side lengths $f(a),f(b),f(c)$.
Problem
Source: China Team Selection Test 2016 Test 3 Day 2 Q6
Tags: algebra, function
26.03.2016 18:16
First note $f(2x) \geq 2f(x)$ while $f(y) < 2f(x)$ for all $y<2x$, thus $f$ is monotone increasing. Using this and simple induction, we obtain $f(nx) \geq nf(x)$. On the other hand, another induction shows that for any $\epsilon > 0$, $f((n+1)y+ \epsilon) < (n+1) f(y+\epsilon)$. Let $\epsilon = \frac{1}{n}x$ and $y = \frac{n-1}{n}x$, it follows that $f(nx) < (n+1) f(x)$. Now fix $a, b > 0$. For positive integers $m, n$, if $ ma \leq nb $ then $mf(a) \leq f(ma) \leq f(nb) \leq (n+1)f(b)$. Thus $\frac{f(a)}{f(b)} \leq \frac{n+1}{m}$ whenever $\frac{a}{b} \leq \frac{n}{m}$. By choosing $m, n$ sufficiently large and $\frac{n}{m}$ close to $\frac{a}{b}$, we conclude that $\frac{f(a)}{f(b)} \leq \frac{a}{b}$. But $a, b$ are symmetric, so we actually have equality. This means $f(a) = \lambda a$ which does satisfy the condition.
27.03.2016 07:55
Sorry to ask, but how did you prove that it is monotone increasing?
27.03.2016 19:04
navi_09220114 wrote: Sorry to ask, but how did you prove that it is monotone increasing? Hi no problem, perhaps I didn't make it clear. Consider $x, x, 2x$. They cannot form a triangle so $f(x), f(x), f(2x)$ cannot either. This implies the inequality $f(2x) \geq 2f(x)$. On the other hand for any $y < 2x$, $x, x, y$ can form a triangle. That means $f(x), f(x), f(y)$ also can, so $f(y) < 2f(x)$. Therefore for all $y < 2x$ it holds that $f(y) < 2f(x) \leq f(2x)$, and $f$ is monotone.
28.03.2016 06:00
My solution above was incorrect because I overlooked the requirement that $a, b, c$ be distinct. But here is a fix: we first show $f$ is continuous. Once we know that, the rest of the argument goes through without trouble. By the triangle inequality on the function values, it suffices to show $f(x) \to 0$ as $x \to 0$. We have $f(x) < f(1) + f(1+ \frac{x}{2}) < f(1) + (f(1) + f(2))$ is bounded when $x$ is near zero. Moreover, along any sequence $x_n \to 0$ we cannot have $f(x_n) \to \lambda > 0$. For that would imply $f(x_m), f(x_n), f(x_k)$ are sides of a triangle for sufficiently large $m, n, k$, even though $x_m, x_n, x_k$ will not be if we pick $k$ much larger than $m,n$. Thus we have shown $f(x) \to 0$ as $x \to 0$. There should be a way to avoid the bit of analysis used here, but perhaps it's tricky and not really worth the extra effort.
03.05.2016 06:49
This was a really nice and intriguing question. Does anyone else have a solution?
19.06.2016 06:22
any one have the solution of this problem , it's very beautifull and my opinion and I don't succeed on solving it myself
01.10.2017 16:03
Does anyone have a solution? (angiland's solution is hard to understand) Thanks!!!
02.10.2017 14:03
angiland after showing " f is continuous",what do you do?(Is the rest in #4?)
18.12.2019 18:54
For example consider the equation $ab+a+b$ and add arbitrarily $f $ on it. It becomes $f(af(b))+f (a+b)=f (bf (a)+a)+b$. That's how we can solve it.
19.12.2019 06:26
Does anyone have the official solution?
20.12.2019 14:22
Suppose that $f $ is a standard function. Consider $a,a $ and $2b$ $\implies f (2a)\ge 2f (a) $ Because $a,a $ and $2a $ cannot form a $\triangle $ Notice that $f (a)+f (a)\le f (2a)\implies 2f (a)\le f (2a) $ If $b <2a $ then $a,a $ $b $ can form a triangle. So $2f (a)>f (y) $ $\ldots(1)$ Hence, \[f (b)<2f (a)\le f (2a) \forall b <2a\]By induction, $nf(a)\le f (na) $ Note, for any $\epsilon>0$ then $b <b+\epsilon$ $\implies 2b+\epsilon <2b+\epsilon\implies f (2b+\epsilon)<2f(b+\epsilon) $ By induction, \[f ((a+1)b+\epsilon)<(a+1)f (b+\epsilon)\]Now, $\epsilon=\frac {1}{n} a$ and $b=\frac {(n-1)}{n}a $
17.12.2021 03:55
@above I received one version where $a,b,c$ are not necessarily pairwise distinct, but this version needs $a,b,c$ p/w distinct. The answer is $f(x)\equiv cx$ for $c\in \mathbb{R}^+$. It clearly works. It suffices to show these are the only functions. Step 1: prove $f$ is increasing. Consider $P(x,y,2x)$ where $y>x$ and $P(x,z,2x)$ where $z<x$ Claim: if $z<x$, $f(z)$ is not the largest among $f(z),f(x),f(2x)$. Proof: If $f(z)$ is the largest among the three, then $f(z)\ge f(x)+f(2x)$. By $P(x,2x,t)$ for $t<3x$, $f(z)\ge f(x)+f(2x)>f(t)$ Let $p_1=x+\epsilon_1, p_2=x+\epsilon_2, p_3=3x-\epsilon_2, p_4=3x-\epsilon_1$ for $\epsilon_1<\epsilon_2<z$ very small. Then $z,p_1,p_3$ don't satisfy the triangular inequality. Since $f(z)=\max\{ f(z), f(p_1), f(p_3)\}$, it follows that $f(z)\ge f(p_1)+f(p_3)$. Similarly, $f(z)\ge f(p_2)+f(p_4)$ However, $z,p_1,p_2$ and $z,p_3,p_4$ satisfy the triangular inequality, so $f(z)<f(p_1)+f(p_2)$ and $f(z)<f(p_3)+f(p_4)$. It follows that $f(p_1)+f(p_2)+f(p_3)+f(p_4) > 2f(z) \ge f(p_1)+f(p_2)+f(p_3)+f(p_4)$, contradiction. If $z<x<y$, $P(x,z,2x), P(x,y,2x)$ gives $f(z)\le |f(2x)-f(x)|<f(y)$, $f$ is strictly increasing. Step 2: Prove $f(x+y)=f(x)+f(y)$ We know $f(x+y)\ge f(x)+f(y)$ (*). Assume for contradiction $f(x+y) > f(x)+f(y)$ for some $x,y$, then there exists $\epsilon>0$ such that $\frac{f(x+y)}{f(x)+f(y)} = 1+\epsilon$ Then there exists an integer $n>\frac{1}{\epsilon}$ such that $n(f(x)+f(y)) \le (n-1)f(x+y)$ By repeatedly using (*), we get $(n-1)f(x+y) \le f((n-1)(x+y))$ Let $\delta<\frac{\min\{x,y\}}{1000n}$, then $n(f(x)+f(y)) > f(x+y-\delta) + (n-1)f(x) + (n-1)f(y) > f(nx+ny-2n\delta)$ by induction, so we can get $f((n-1)(x+y)) > (n-1)f(x+y) \ge n(f(x)+f(y)) > f(nx+ny-2n\delta)$. By our definition of $\delta$, this contradicts that $f$ is increasing. Since additive and increasing implies linear, the conclusion follows.
04.09.2022 10:20
@kai how do you know that $(n-1)f(x+y)\leq f((n-1)(x+y))$? I think (*) only works for $x,y$ that are distinct.
04.09.2022 10:31
NoctNight wrote: @kai how do you know that $(n-1)f(x+y)\leq f((n-1)(x+y))$? I think (*) only works for $x,y$ that are distinct. The problem reads for \(a,b,c\) distinct. I hope this clears your doubt.
04.09.2022 10:34
rama1728 wrote: NoctNight wrote: @kai how do you know that $(n-1)f(x+y)\leq f((n-1)(x+y))$? I think (*) only works for $x,y$ that are distinct. The problem reads for \(a,b,c\) distinct. I hope this clears your doubt. So it's actually not necessarily true that $(n-1)f(x+y)\leq f((n-1)(x+y))$?
04.09.2022 10:58
Solved with an IMO team member. Say that $a,b,c$ are good if they form the sides of a triangle, and bad otherwise. Step 1: $f$ is injective. Proof: Suppose $f(x)=f(y)$ for $x<y$. Then $f(a),f(b),f(x)$ are good if and only if $f(a),f(b),f(y)$ are good, so $a,b,x$ are good if and only if $a,b,y$ are good for any $a,b$. Taking $a=\frac{x}{2}+\varepsilon,b=\frac{x}{2}$ for arbitrarily small $\varepsilon$ gives $a+b=x+\varepsilon>x$ so $a,b,x$ are good, but $a+b=x+\varepsilon<y$ so $a,b,y$ are bad, a contradiction. Step 2: $f$ is strictly increasing. Proof: FTSOC suppose that there exists $a>b$ such that $f(a)<f(b)$ - call such a pair decreasing. By choosing $c=\frac{a+b}{2}$, if $f(a)<f(c)$, then $a,c$ are a decreasing pair with half the difference. Similarly, if $f(a)>f(c)$, then $f(c)<f(a)<f(b)$ so $b,c$ are a decreasing pair with half the difference. Repeating this allows us to choose a decreasing pair $a,b$ with an arbitrarily small value of $a-b$. Now, choose $m,n$ such that $a-b<m,n<b<m+n<a$ (such a pair exists since $a-b$ can be made arbitrarily small). WLOG assume $f(m)>f(n)$. Then, $m,n,b$ are good but $m,n,a$ are bad. Therefore, $$f(m)+f(n)>f(b)>f(a)\quad \text{and}\quad f(m)-f(n)<f(b)$$in order for $f(m),f(n),f(b)$ to be good. For $f(m),f(n),f(a)$ to be bad, we must have $f(n)+f(a)\leq f(m)$, so $f(a)\leq f(m)-f(n)<f(b)$. We can now choose arbitrarily many real numbers $m_1,m_2,\ldots,m_k$ with $f(m_1)<f(m_2)<\ldots<f(m_k)$ such that for any $i\neq j$, we have $a-b<m_i,m_j<b<m_i+m_j<a$. This means that $f(m_{i+1})-f(m_i)\geq f(a)$ and $f(m_k)-f(m_1)<f(b)$. By choosing $k$ such that $kf(a)>f(b)$, we have $$f(b)>f(m_k)-f(m_1)=(f(m_k)-f(m_{k-1}))+\ldots+(f(m_2)-f(m_1))\geq kf(a)>f(b)$$a contradiction. Therefore, $f$ is strictly increasing. Step 3: There exists $x$ such that $f(x)$ is arbitrarily small. Proof: Suppose FTSOC that $f(x)>c$ for all $x$, for some constant $c>0$. First, substitute $x,y,x+y$ for distinct $x,y$ to see that $f(x+y)\geq f(x)+f(y)$ for distinct $x,y$ because $x,y,x+y$ are bad so $f(x),f(y),f(x+y)$ are bad and $f$ is strictly increasing. Then choose $x,y$ where $y-x=z>0$. Let $f(y)-f(x)=t$ and choose an arbitrarily large integer $k$ such that $kc>t$. We consider numbers $z_1<z_2<\ldots<z_k$ such that $z_1+z_2+\ldots+z_k=z$. Then $$f(x)+t=f(y)\geq f(x)+f(z)\geq f(x)+f(z_1)+f(z_2)+\ldots+f(z_k)\geq f(x)+kc>f(x)+t$$by an inductive argument, a contradiction. Therefore, such $c>0$ does not exist, so arbitrarily small $f(x)$ do exist. Step 4: $f$ is continuous. Proof: It suffices to show that for any $a$ and $c$, there exists $b$ such that $|f(x)-f(c)|<a$ for all $x$ such that $|x-c|<b$. To do this, choose $b$ such that $f(b)<a$ and $b<c$ which exists since $f$ is strictly increasing. Then, since $x,b,c$ are good, then $f(x),f(b),f(c)$ are good, so $|f(x)-f(c)|<f(b)<a$, as desired. Step 5: $f(x)=cx$ for some constant $c>0$. Proof: Suppose $f(a+b)>f(a)+f(b)$. Then since $a+b-\varepsilon,a,b$ are good for any $\varepsilon>0$, $f(a+b-\varepsilon)<f(a)+f(b)$. Then there is no value of $x$ such that $f(x)=f(a)+f(b)$, a contradiction by Intermediate Value Theorem since $f(a+b)>f(a)+f(b)$ and $f(a+b-\varepsilon)<f(a)+f(b)$ and $f$ is continuous. Therefore, $f(a+b)=f(a)+f(b)$ for any $a,b$. By Cauchy's functional equation, since $f(x)>0$ for all $x$, we have that $f(x)=cx$ for some constant $c>0$. Evidently, $x,y,z$ form a triangle if and only if $cx,cy,cz$ form a triangle, so the only solution is $f(x)=cx$.
09.10.2022 23:54
Thanks to NoctNight for the catch. NoctNight wrote: @kai how do you know that $(n-1)f(x+y)\leq f((n-1)(x+y))$? I think (*) only works for $x,y$ that are distinct. Thank you for pointing out the silly mistake. I am sure I can prove $n(f(x)+f(y)) > f((n-\frac 12)(x+y))$ and $(n-1)f(x+y) < f((n-\frac 12)(x+y))$ since $f$ is increasing.
09.10.2022 23:58
GL cbk lol
25.01.2024 18:53
Nice one. Here is my solution which I think is a bit cleaner than the one posted above. Claim 1: $\lim_{x \to 0} {f(x)} = 0$ Proof: First notice that there doesn't exist a sequence $a_n \to 0$ such that $f(a_n) \to c \neq 0$, as for all big enough $i,j,k$ we would have $f(i),f(j),f(k)$ be the sides of a triangle, but we can take big enough $j,k$ such that $a_i>a_j+a_k$, which is a contradiction. Assume for contradiction that there exists a sequence $a_n \to 0$ such that $f(a_n) \to \infty$. Take some $a>0$ and notice that $f$ is bounded by some constant $M$ in the segment $[a,\frac{101a}{100}]$, as for all $b$ in that segment we know that $b,\frac{a}{2},\frac{2a}{3}$ is a triangle, so $f(b)<f(\frac{a}{2})+f(\frac{2a}{3})$. Now notice that $a,a+\frac{a_k}{2},a_k$ are the sides of a triangle, but for big enough $k$ we have $f(a)+f(a+\frac{a_k}{2})<2M<a_k$ which is a contradiction. It means that $f$ doesn't have any subsequential limit in $0$ other than $0$, which means that $\lim_{x \to 0} {f(x)} = 0$. Claim 2: $f$ is continuous. Proof: Let $x \in \mathbb R^+, \varepsilon>0$. for all small enough $\delta$ we have $f(\delta)<\varepsilon$, which means that for all $y \in (x-\delta,x+\delta)$ we have $f(x)-\varepsilon<f(x)-f(\delta)<f(y)<f(x)+f(\delta)<f(x)+\varepsilon$, which proves continuouity. Claim 3: $f$ is injective Proof: Assume that $x<y$ and $f(x)=f(y)$. Then for small enough $\varepsilon$, $x,y,\varepsilon$ are not the sides of a triangle but $f(x),f(y),\varepsilon$ are, which is a contradiction. As $f$ is continuous and injective, we get that it's strictly monotonic, and as $\lim_{x \to 0} {f(x)} = 0$, we know it must be strictly increasing. Let $x,y \in \mathbb R^+$. then $f(x),f(y),f(x+y)$ are not the sides of a triangle, so $f(x+y)\geq f(x)+f(y)$ (because $f$ is increasing), but for all small enough $\varepsilon > 0$ we have $f(x+\varepsilon)+f(y)>f(x+y)$, which means by continuity that $f(x)+f(y)\geq f(x+y)$. Therefore, $f(x+y)=f(x)+f(y)$, which means that $f(x)=cx$ for all $x$ for some $c \in \mathbb R^+$, and that is indeed a solution.