IMO

# Iran TST 2011 Q5

Find all SURJECTIVE functions $f:\mathbb R \to \mathbb R$ such that $\forall x,y \in \mathbb R$,

$f(x+f(x)+2f(y))=f(2x)+f(2y)$.

Answer: $f(x)=x, \forall x \in \mathbb R$.

Let the equation be $P(x,y)$.

All right… Surjective… That means we will be able to let $f(y)$ be whatever we want…

$f(x)=x$ obviously works, and $f(x)=kx, k\ne 1$ don’t work. $f(x)=x+c,c\ne 0$ don’t work either. Since the right hand side is symmetric in $x$ and $y$, we’d expect the LHS to be basically symmetric as well (hmm we might be able to twiddle take this, at some point), thus we expect $f(x)=x$ to be the only solution. (Constant solutions work but they are not surjective.

Turns out that $x+f(x)$ term is hard to control, and we don’t find $f(0)$ that easily.

We want to show it is injective. Because if it was injective we can twiddle take the equation and show $f(y)-f(x)=y-x$ by switching $y$ and $x$, from which the solution follows straightaway.

So LHS, as function of $y$ only depends on $f(y)$, and the RHS has only $f(2y)$. Thus we see that $f(2y) = h(f(y))$, i.e. $f(2y)$ only depends on $f(y)$.

Now, let $f(x_1)=f(x_2)$, then $P(x_1,y), P(x_2,y) \implies f(x_1 + f(x_1)+2f(y))=f(x_2 + f(x_1)+2f(y))$ as $f(2x_1)=f(2x_2)$. Let $x_1 - x_2 = t, 2f(y)+f(x_1)+x_2 = a$. We then have $f(a+t)=f(a), \forall a \in \mathbb R$. (This uses surjectivity!!!! It is only because the function is surjective that we can make $a$ range over the entire real number.)

Seems like our injectivity scheme is not going well… Well we will twiddle take the equation anyway.

Define $x\equiv y$ as $f(x)=f(y)$. That is, $x-y$ is a period of $f$. It is easy to check that this is an equivalence relation that is preserved by addition of equal term.

$P(x,y). P(y,x) \implies x+f(x)+2f(y) \equiv y+f(y) + 2f(x)$, or,

$(f(x)-x) \equiv (f(y)-y) , \forall x, y \in \mathbb R \,\,\,\,\,\,\,(*)$.

This is like a pseudo $f(y)-f(x)=y-x$….  Let’s sub in values and see…

Let $f(r)=0$. (by surjectivity it exists.)

In (*) let $y=0$, we see that $f(x)\equiv x+f(0)$.

$P(0,r) \implies f(f(0))=f(0)+f(2r)$. LHS$\equiv f(0)+f(0)\equiv 2f(0)$, RHS$\equiv f(0)+2r+f(0)$. Thus $2r \equiv 0$.

$P(r,y) \implies f(r+f(r)+2f(y))=f(2r)+f(2y)$. $P(0, y) \implies f(0+f(0)+2f(y))=f(0)+f(2y)$. Since $2r \equiv 0$, $r \equiv f(0) \equiv f(f(r)) \equiv r + 2f(0)$. Thus $2f(0)\equiv 0$.

$\displaystyle P(\frac r2 , y) \implies f(\frac r2 +f(\frac r2 )+2f(y))=f(2y) \\ \implies \frac r2 +f(\frac r2 )+2f(y) \equiv 2y \\ \implies 2\times \frac r2 + f(0) + 2y + 2f(0) \equiv 2y \\ \implies r \equiv -f(0) \equiv f(0)\\ \implies 0=f(r) =f(f(0))$.

But since $r \equiv f(0), 2r \equiv r+r\equiv f(0)+f(0)\equiv 2f(0)\equiv 0$, thus $f(f(0))=f(0)+f(2r)=2f(0)$. But $f(f(0))=0 \implies f(0)=0$.

So, we tried to show that $f$ is injective, but ended up showing $f(0)=0$. That is still great though, because now we have $f(x)\equiv x, \forall x \in \mathbb R$. All these substitutions are found by trial and error, which makes the problem quite challenging indeed. The idea behind, though, is that if the “$\equiv$” sign is replaced by equal, we will be able to determine $f(0)=0$ by equating coefficients of LHS and RHS of $P(x,y)$. We are just doing in modulo the set of periods.

Since $f(f(x))=f(x)$, all values in the image of $f$ are fixed points of $f$.

But $f$ is surjective. Thus $f(\mathbb R)=\mathbb R$, thus every real number is a fixed point. Or, $f(x)=x, \forall x \in \mathbb R$.

Comment: the middle part of finding the $f(0)$ is tricky, and it is useful to notice the structure that all difference between pair of number giving off the same value are periods of the function. We used the surjectivity twice, once when showing that they are periods, the other when showing that the image of $f$ is the entire real number. The second time, despite that the equation could be reduced to additive Cauchy function, the zero function can still work, so we need to use the surjectivity to do this.

Standard
Uncategorized

# Special topic: Three sides of a triangle

Find all function $f: \mathbb N^+ \to \mathbb N^+$ such that $\forall a,b \in \mathbb N^+$,

$a,\,\,\,f(b),\,\,\,f(f(a)+b-1)$

form the three sides of a non-degenerate triangle. (IMO 2009 Q5)

Answer: $f(n)=n ,\forall n \in \mathbb N^+$.

Let the condition be $P(a,b)$.

It’s obvious that $f(n)=n$ works, and that $f(n)=n+k, k \ne 0$ or $f(n)=cn, c\ne 1$ don’t work. With the term $a$ which is linear in the functional inequality, we expect only linear solutions to exist.

Because the triangle condition implies strict inequalities, we wish to use the discreteness of integers to reduce it.

$P(1,b) \implies f(b) + 1 > f(f(1)+b-1), f(f(1)+b-1) +1 > f(b)$. The two inequalities reduce to

$f(b) \ge f(f(1)-1 +b ) \ge f(b) \implies f(b)=f(f(1)-1+b)$

If $f(1) \ne 1$, we have $f(1) \ge 2$ and $f(1)-1$ is a period of the function $f$. Since $f$ is defined on $\mathbb N^+$, that implies that $f$ is bounded. Suppose that $f(b) \le M, \forall b \in \mathbb N^+$.

$P(2M+1,b) \implies 2M+1 < f(b) + f(f(2M+1)+b-1) \le 2M$. This is absurd. Thus $f(1)=1$.

We did this because there is one unbounded term!

Using the same trick as above,

$P(a,1) \implies a = f(f(a)), \forall a \in \mathbb N^+\, \, \, \, \, \, (*)$.

Or, $f$ is an involution. This automatically shows that it’s bijective.

We already know a lot about the function now… If we could show any extra condition the conclusion should be within reach. Monotonicity, $f(n) \le n$ or $f(n) \ge n$ all work. Let’s see what happens if $\exists f(k) \ne k$. Since $f(1)=1, k\ne 1$. WLOG $f(k) > k$ as otherwise one can replace $k$ with $f(k)$. We have $P(k,b) \implies f(b) + k > f(b+f(k)-1)$. Now, $f(b)+k-1 \ge f(b+f(k)-1)$. Reiterate this inequality, we have

$f(b) + j(k-1) \ge f(b + j(f(k)-1)) \, \, \, \, \, \, (*)$.

What does this imply? $f(k)-1 > k-1$, and we thus have that $f(n)$ grows ‘more slowly than $n$. We wish to make $n\to \infty$ to create a contradiction. But how? We want to move forward with $f(k)-1$ as the length of our ‘pace’\$. Thus if we exhaust a complete system of remainder modulo $f(k)-1$, we will be able to show that $f(n) < n$ for $n$ large enough. That should be able to finish the problem off: as $f(f(n)) < f(n) < n =f(f(n))$ will be bad, so we only have to make sure $f(n)$ is ‘large enough’ to ensure a contradiction is reached.

Let $C = \max _{1 \le n \le f(k)-1}f(n)$. Letting $j > C$, we have (upon reducing $b$ into $\{1,2, ..., f(k)-1\}$,

$f(b+j(f(k)-1)) - (b+j(f(k)-1))\\ \le f(b) +j(k-1) -(b+j(f(k)+1)) = (f(b)-b) + j(k-f(k))\\ < f(b) -j \le C -j <0\textnormal{.}$

Let $b$ exhaust the set $\{1,2, .. , f(k)-1\}$, we see that for $n$ large enough we indeed have $f(n) < n$.

We now claim that $f(n) \to \infty$ as $n \to \infty$. This is because $f$ is injective, and thus there are only finitely many $n$ such that $f(n) \le \gamma$ for any fixed $\gamma$. Thus, if we let $D$ be such a number that $f(n) < n, \forall n \ge D$, there exists $D'$ such that $f(n) > D, \forall n \ge D'$. We let $n \ge \{D,D'\} \implies f(f(n)) < f(n) . Contradiction. Thus $\not \exists k \in \mathbb N^+, f(n) \ne n$. We conclude that $f(n) = n \forall n \in \mathbb N^+$.

Comment: Easy problem. We used proof by contradiction because the problem’s condition is ultimately an inequality for which it is easier to assume certain inequalities to compare the values. One should be able to solve it rather quickly: Andrew Elvey Price only took half an hour to finish it up.

The following problem is basically a spin-off the previous one, and is left to the reader as an exercise.

Find all function $f: \mathbb N^+ \to \mathbb N^+$ such that

1) $\forall a,b \in \mathbb N^+, \gcd (a,b)>1,$

$f(a)f(b)=f(ab)$

2) $\forall a,b \in \mathbb N^+,$

$f(a),\,\,\,\,\,f(b),\,\,\,\,\,f(a+b-1)$

form the three sides of a non-degenerate triangle. (AUS&UNK 2016 IMO Final Training)

Determine whether there exists $f: \mathbb N^+ \to \mathbb R^+$ such that for all pairwise different $x,y,z \in \mathbb N^+$,

$(x+y)f(z),\,\,\,\, (y+z)f(x),\,\,\,\, (z+x)f(y)$

are the three sides of an acute-angled triangle.(Renhui Jiuzhang 2015 Prac Exam 6 Q2)

Find all function $f: \mathbb R^+ \to \mathbb R^+$ such that $\forall a,b,c \in \mathbb R^+$, $a,b,c$ pairwise different, $a,b,c$ form the three sides of a non-degenerate triangle if and only if $f(a),f(b),f(c)$ form the three sides of a non-degenerate triangle. (China TST 2016 Q18)