IMO 2017 Q2

Note: my equation labelling does not seem to work. Someone please help me fix it. Thanks in advance.

The problem: IMO 2017 Q2

Find all functions ${f: \mathbb R \rightarrow \mathbb R}$ such that for all ${x,\,y \in \mathbb R}$ we have the following:

$\displaystyle f(f(x)f(y)) + f(x+y) = f(xy).$

Solution and Discussion

Denote the given equation by ${P(x,y)}$ . Cmon. It isn’t easy to see what solution would work save for ${f(x) \equiv 0}$ . An observation is that if ${f(0) = 0}$ we simply substitute ${y=0}$ into the equation and we get ${f(x)=0}$ for all ${x.}$ So now we can assume ${f(0) \neq 0}$ . Where to go?

It’s a medium so preliminary investigations can guide us quite a long way most likely. (Even for the monstrous 2015 Q5 one should at least get to showing ${f(0)=0}$ or ${2}$ before getting helplessly stuck.) So suppose ${x+y=xy}$ , which is to say that ${y=\frac{x}{x-1}}$ , we shall have

$\displaystyle f(f(x)f(\frac{x}{x-1}))=0$

for all ${x \neq 1}$ . Now suppose that for a certain ${\lambda \in \mathbb R}$ we have ${f(\lambda) = 0}$ (you see such ${\lambda}$ just has to exist, say ${\lambda = f(0)^2}$ ) we will then have ${f(f(\lambda)f(\frac{\lambda}{\lambda - 1})) =0}$ and thus ${f(0)=0}$ which is bad…. Unless ${\lambda = 1}$ .

That is to say,

$\displaystyle f(\lambda) = 0 \Longleftrightarrow \lambda =1.\,\,\,\,\,(1)$

As a side, ${f(x)f(\frac{x}{x-1}) = 1}$ for all ${x \neq 1}$ . Ergo, ${f(0)^2 = f(2)^2 =1}$ . Also, ${P(1,1)}$ gives us ${f(0)+f(2)=0}$ . Combining these two equations we have either

$\displaystyle f(0)=1 \,\mbox{ and }\,f(2)=-1,\,\,\,\,\,\,(*)$

or vice versa.

Do they really correspond to solutions at all? At present stage it seems that the equation (*) is suggesting that ${f(x) = 1-x}$ , and the ‘vice versa’ demands ${f(x) = x-1}$ . Substitute them in … they work! We want to only pursue one line of reasoning though.

Observation: if ${f(x)}$ is a solution, ${g(x) = -f(x)}$ is also a solution. This is because ${g(g(x)g(y))+g(x+y) = -(f(f(x)f(y))+f(x+y))=-f(xy)=g(xy)}$ . So we can really WLOG assume (*) is true. (why not the vice versa? Because ${f(x)=1-x}$ is an involution, that is, ${f(f(x))=x,\,\forall x}$ which could simplify our work a lot potentially.)

First of all, ${P(x,1) \implies}$

$\displaystyle 1 + f(x+1) = f(x)\,\,\,\,\,\,\,(2)$

And here you go, ${P(x,0) \implies}$

$\displaystyle f(f(x))+f(x) = 1 \,\,\,\,\,\,\,(3)$

which is to say that ${f(x) = 1-x ,\, f(f(x))=x,\, \forall x \in f(\mathbb R).}$ So it remains to show ${f}$ is surjective!

Sounds nice, doesn’t work. Sad!

If surjection doesn’t work, one might still try injection. So let’s try to show injection. Doesn’t seem easy… Suppose ${f(x_1)=f(x_2)}$ , ${P(x_1, -x_2)}$ and ${P(-x_1,x_2)}$ gives us that, provided that ${f(-x_1) =f (-x_2)}$ , ${f(x_1-x_2)=f(x_2-x_1)}$ . So let’s pause for a moment, and see if ${f(-x_1)=f(-x_2)}$ can be shown…

As a matter of fact, your OP got exceedingly lucky when trying this problem. He somehow made a bad mistake that gave him true conclusions. Don’t ask him how. The OP just somehow figured out that

$\displaystyle f(-f(f(x)))=f(-x)\,\,\,\,\,\,\,\,(4)$

To show (4), we look back into the original equation ${P(x,y)}$ .

$\displaystyle P(f(x),2) \implies \\ f(-f(f(x))) + f(f(x)+2) = f(2f(x))$

$\displaystyle P(x,-1)\implies \\ f(2f(x))+f(x-1)=f(-x)$

Combining the above two pieces of computation we get

$\displaystyle f(-f(f(x))) - f(-x) = -f(x-1) - f(f(x)+2) = -f(x) -1 - (f(f(x))-2) = 1- (f(f(x))+f(x)) = 0$

by referencing (2) and (3).

Whooosh. That was precarious. But now we have (4), which gives us not only that ${f(-x_1) = f(-x_2)}$ , but also that, if ${k = x_1 - x_2}$ , ${f(k) = f(-k) = f(-f(f(k)))}$ , and if we ${f}$ both sides, ${f(f(k)) = f(f(-f(f(k))))}$ . Suppose we could show that ${-f(f(k)) \in f(\mathbb R)}$ , we would be able to ‘undress’ the RHS and get ${f(f(-f(f(k))))=-f(f(k))}$ and thus getting ${f(f(k))=0}$ . Sounds like a plan. Well, (3) says if ${u \in f(\mathbb R)}$ , ${1-u \in f(\mathbb R)}$ and (2) says if ${1-u \in f(\mathbb R)}$ , ${-u \in f(\mathbb R)}$ . Now ${f(f(k)) \in f(\mathbb R)}$ so it works.

Hooray! We have just shown that if ${f(k)=f(-k)}$ with ${k \neq 0}$ , we must have ${f(f(k))=0}$ and thus ${f(k)=f(-k) = 1}$ . Reference (2), we have that ${f(k+1)=0}$ . Recall that ${1}$ is the only root to ${f(x)=0}$ , we have ${k=0}$ . Thus ${x_1=x_2}$ . YAY!!! ${f}$ is indeed injective!!!

The rest is easy. (3) shows that ${f(f(f(x)))=f(x)}$ and by injectivity ${f(f(x))=x}$ and by (3) we have ${f(x) = 1-x}$ for all ${x \in \mathbb R}$ .

The solutions are ${f(x)=x-1,\,f(x)=1-x,}$ and ${f(x)=0.}$

Comment

What a tedious problem…. Took me two hours + ${\varepsilon}$ to solve. It’s easy to leave gaps in the solution here and there, for instance the OP believed he got the identity that ${f(x+f(y))=f(y+f(x))}$ but in fact it demands ${x,y \in f(\mathbb R)}$ to hold. It helped him discovering (4) though. (4) is really important (and somewhat natural to think of after we have discovered (3)).

The entire solution shows the power of setting ${f(0)=1}$ instead of ${-1}$ because (3) will take some much more deplorable forms had we chosen ${f(0)=-1}$ to work with, so will be (4) — in my humble opinion. I am happy to be shown wrong and be presented a proof using ${f(0)=-1}$ as starting point — I have not yet tried, but it looks disastrous to me.

OP was surprised to see that the key to the solution is injectivity really. The equation looks nothing like something for which injectivity would be a step towards solution — no naked variable anywhere. The point that ${1}$ is the only root to ${f(x)=0}$ must be made for it is the essential cornerstone of any effort towards injectivity.

One might be tempted to use analysis, but I personally do not believe that analysis will be helpful. Analysis required inequality whereas this problem only gives equality that is difficult to be transformed into inequalities.

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.

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) <n =f(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)

Solution to be published gradually….

IMO

Online Algebra Olympiad 2016 Q5

Find all $f: \mathbb R \to \mathbb R$ such that $f(xf(x)-yf(y))=f(x-y)(f(x)+y),\forall x,y \in \mathbb R$ .

All right, looks old-fashioned. For old-fashioned functional equation whose solutions are probably only the obvious ones, we aim to characterise its properties instead of its specific values. Sleeves up, let’s get to work.

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

(Checking is omitted for it is trivial.)

Let $S_2 = \{x\in \mathbb R | f(f(x))=x \}, \Omega = \{x \in \mathbb R | f(x)=0\}$ , and $P = \{x \in \mathbb R | f(t)=f(t+x), \forall t \in \mathbb R\}$ .

That is, $S_2, \Omega, P$ are sets of second-order fixed points, zeroes, and periods of the function, respectively. We will see why we mentioned these sets very soon.

Let the statement of the question be $P(x,y)$ . The condition looks rather symmetric, but not quite. This gives us space for manipulation.

$P(0,0) \implies f(0)=f(0)^2 \implies f(0)= 0$ or $1$ .

Having conjectured that only the two aforementioned solutions to the functional equation exist, we aim to rule out the second case.

$P(x,x) \implies f(0)=f(0)(f(x)+x) \implies f(x)=1-x$ . Substitution shows that this is NOT a solution. Thus $f(0)=0$ .

Keep going, we are on track.

$P(0,y) \implies f(-yf(y)) = yf(-y), P(0,-y) \implies f(yf(-y))=-yf(y)$ .

Look, look, these two switch between each other. Better take this information into account. $\forall y \in \mathbb R, -yf(y), yf(-y) \in \mathbb S_2$ .

But how are we going to exploit the second order fixed points? We have to substitute it into somewhere and compare it with the original value, so we’d better do it with something where $x$ and $f(x)$ are both present, as in such occasion substituting $s \in S_2$ will make this expression comparable with the original one. Such expression exists in the LHS.

$P(s,f(s)), s \in S_2 \\ \implies f(sf(s)-f(f(s))f(s))=f(s-f(s))(f(s)+f(s))\\ \implies f(s-f(s))f(s)=0$ ,

as $f(f(s))=s$ and $f(0)=0$ . If $s \ne 0$ , $f(s) \ne 0$ as $f(f(s))=s \ne 0$ and $f(0) =0$ . Thus $f(s-f(s)) =0$ . If $s=0$ , $f(s-f(s))= f(0-0)=0$ . Thus in whatever case, $s-f(s) \in \Omega$ .

Look at that. That looks like quite some information isn’t it, especially after we substitute $s= yf(-y)$ in…

$yf(-y)-f(yf(-y))=yf(-y)+yf(y) = y(f(y)+f(-y)) \in \Omega, \forall y \in \mathbb R$ .

That wasn’t a big surprise, since the $y$ and $-y$ are supposed to either cancel or both give vanishing function value anyway. But this expression has an advantage….

$P(x, -x) =\implies f(xf(x)+xf(-x))=f(2x)(f(x)-x)$ , and the LHS of this expression is equal to $0$ . Thus,

$\forall x \in \mathbb R, f(2x)=0$ or $f(x)=x \ \ \ \ \ \ \ \ \ \ \ \ \ (*)$ .

Once we are here normally there are many ways to finish the problem off.

Claim: $\Omega = P$ .

If $p \in P$ , $f(p)=f(0+p)=f(0)=0$ .

If $\omega \in \Omega. P(\omega, -y)\implies f(yf(-y))=f(\omega +y)(0+y)=yf(\omega +y)$ . $P(0,-y) \implies f(yf(-y)) = f(y)y$ . If $y \ne 0$ , we can divide both sides by $y$ and conclude $f(\omega + y) =\frac {f(yf(-y))}{y} = f(y)$ . If $y =0$ , $f(\omega + y) = f(\omega) =0 =f(0)=f(y)$ . Thus $f(\omega + y)=y, \forall y\in \mathbb R$ .

If $f$ only vanishes on $x=0$ , we recall the statement (*), in which $f(2x) \ne 0, \forall x \ne 0$ , thus $f(x)=x \forall x \in \mathbb R \ \{0\}$ . But $f(0)=0$ anyway, thus $f(x)=x$ .

If $\exists \omega \ne 0, f(\omega)=0$ , then $\omega$ is a period of the function. $P(x, \omega) \implies f(xf(x))=f(x-\omega)(f(x)+\omega)=f(x)(f(x)+\omega)=f(x)^2 +\omega f(x)$ .

But now, $P(x, 0) \implies f(xf(x))=f(x)^2$ . Thus $\omega f(x)=0, \forall x \in \mathbb R$ . Which, since $\omega \ne 0$ , forces us to have $f(x)=0, \forall x \in \mathbb R$ .

Comment: Boring problem, just a few substitutions to crack it open. But the substitutions are not that easy to find, especially the middle part where one needs to play around with the second order fixed point set. The part proving that all zeroes are periods makes use of the ubiquity of $f(x)$ on both sides (since it is ubiquitous we let it vanish to reduce the equation down.)

IMO

China TST 14′ Q3 & USA TSTST 12′ Q3

Suppose $f:\mathbb N^+ \to \mathbb N^+$ satisfies:

1) $\gcd(f(m),f(n))\le \gcd (m,n)^{2014},\forall m,n\in \mathbb N^+$

2) $n\le f(n)\le n+2014,\forall n \in \mathbb N^+$ .

Show that $\exists \Omega \in \mathbb N^+,f(n)=n, \forall n \ge \Omega$ .

Let $\mathcal B = \{n\in \mathbb N^+ | f(n) \ne n\}$ .

The $2014$ looks DAUNTING. Let’s try a small case with both the $2014$ ‘s replaced with $1$ .

If $\exists n$ large enough, $f(n)=n+1$ , we will need $f(n+1)=n+2$ because if $f(n+1)=n+1$ , we will have $\gcd(f(n+1),f(n))=\gcd(n+1,n+1)=n+1 > \gcd(n+1,n)=1$ which is bad. Therefore we inductively show that all large enough $n$ will have $f(n)=n+1$ . Then we will choose large enough odd $n$ and $n+2$ , and thus $f(n)=n+1$ and $f(n+2)=n+3$ , which blows up the inequality 1) by $\gcd (f(n),f(n+2)) =2 \ge \gcd(n,n+2)=\gcd(n,2)=1$ .

Right. We have a rough idea now: letting infinitely many non-fixed points exist and then we show that there are A LOT of non-fixed points, in which set we can do stuff. Note that the above ‘very large’ only requires $n+1 > 1$ .

Choose $\Omega = 2014^{2014} +1$ . We claim that $\forall n\in \mathcal B, n \le 2014 ^{2014}$ .

We suppose it is not true, and let $q \ge \Omega$ and $q\in \mathcal B$ , with $f(q)=q+c$ .

We want to control $\gcd(f(n),q+c)$ and $\gcd(n,q)$ at the same time, thus we want to use Chinese Remainder Theorem to get a good residue modulo $q$ and $q+c$ . But CRT requires co-primality of the different modulos that we are putting together, thus $\gcd(q,q+c)=\gcd(q,c)=g \le 2014$ , because $1\le c \le 2014$ .

Let $\displaystyle \frac ng \equiv g \mod \frac qg$ ,

$\displaystyle \frac ng \equiv 0 \mod \frac {q+c}{g}$ . (This can be done now by definition of $g$ .)

We claim that for such $n$ , $n \in \mathcal B$ .

Because if not, $\gcd(f(n),f(q))=f(q+c,n)=q+c$ , and $\gcd (n,q)=g$ . The second equation is true because if $g|q$ , we have $\gcd(n,q)=\gcd(n,g)=g$ . If $g \not | q$ , we then have $\displaystyle \gcd (n,g\frac qg)=\gcd (\frac ng,\frac qg)g=\gcd(1,\frac qg)g=g$ . We thus need $g^{2014} \ge q+c$ which is not true as $g^{2014} \le 2014^{2014}$ and $q+c > \Omega > 2014 ^{2014}$ .

(This is why we defined $\Omega$ to be that number !!!)

Thus we see that there exists an infinite arithmetic progression whose large enough terms are all elements of $\mathcal B$ . We will just write $\mathcal A$ for the arithmetic progression.

We now want to let ( $a\in \mathcal A$ ) $f(a)=a+k$ have prime factors that we push to infinity, whereas $a$ themselves must not be tainted with those factors. And then we will compare it with other stuff, with the ‘other stuff’ better be coprime with $a$ , with $f(\textnormal {other stuff})$ having enough common factor with $f(a)$ to blow up the inequality. (Don’t say this word at airport.)

Choose $p_{i,j}$ , where $i \in \{1,2, ... , 2014\}, j\in \{0,1,...,2014\}$ to be a collection of $2014 \times 2015 = 4058210$ different primes which are all greater than $2014$ and all greater than the common difference in $\mathcal A$ . This can be done as there are infinitely many primes. (Yes, infinitude of primes is a GREAT theorem. It gives you a nice collection of modulos to Chinese Remainder on. And Chinese Remainder theorem is used almost always to only show the existence of a certain desired solution taking the form of an A.P., while not accentuating on the numerial value of the solution.)

Let

$\displaystyle \\ \eta \in \mathcal A \\ \\ \eta \equiv -1 \mod p_{1,j}, \forall j, \\ \\ \eta \equiv -2 \mod p_{2,j}, \forall j, \\ \\ ... \\ \\ \eta \equiv -i \mod p_{i,j}, \forall j, \\ \\ ... \\ \\ \eta \equiv -2014 \mod p_{2014, j}, \forall j .$

We need to show that this can be done. All we need to show is that all the $p_{i,j}$ ‘s are coprime to the common difference of $\mathcal A$ , which is true since we have chosen them to be large enough.

(This step is why we took all the pain to show that elements of $\mathcal B$ not only exist, but exist IN AN ARITHMETIC PROGRESSION, and then we can select the desired subsequence we want from it by Chinese Remaindering the arithmetic progression with other prime modulos. Only assuming that $\mathcal B$ has infinitely many elements restricts what we can do on it.)

Note that what we are doing now DEVIATES from what we did with the simple case, because now it is rather difficult to control over what happens to $f(\eta)$ as now we only have $f(\eta) \ne \eta$ instead of what it actually is. Thus I wish to restrict all the values of $f(\eta)$ and then compare it with OTHER positive integer’s function values instead of integers in the arithmetic progression that defined $\eta$ .

Fix the $\eta$ , and suppose $f(\eta) = \eta +c$ , where $1\le c \le 2014$ .

Now let

$\displaystyle \sigma \equiv - j \mod p_{c,j}$ for each $p_{c,j}, 0\le j \le 2014$ .

and $\sigma \equiv 1 \mod \eta$ .

Again, we need to show that this can be done, and it suffices to check that $\gcd (\eta, p_{c,j})=1, \forall p_{c,j}$ . Assume this is not true, and $p_{c,\rho} | \eta$ . Recall that $\eta + c \equiv 0 \mod p_{c,\rho}, \implies \gcd(\eta, \eta+c) =\gcd(\eta, c) \ge p_{c, \rho}$ .

The above inequality is impossible due to the fact that $p_{c,\rho} > 2014 \ge c >0$ . Thus the Chinese Remainder construction of $\sigma$ is indeed possible. (Note that the $c>0$ requires the full power of $\eta \in \mathcal B$ .)

OMG SO MANY CHINESE REMAINDERS… We use it to control the remainders of the variables dividing each other so as to manipulate the gcd’s.

Finally, we have an $\eta \in \mathcal B$ with all its possible function values being star-crossed, and a $\sigma$ , not necessarily in $\mathcal B$ , with all its function values holding such an enmity with function values of $\eta$ . This will blow up the inequality.

Substitute $\eta$ and $\sigma$ into the inequality, $\implies \gcd(f(\eta),f(\sigma)) \le \gcd (\eta, \sigma)^{2014}$ . The RHS $=1$ as $\sigma \equiv 1 \mod \eta$ . The LHS $= \gcd (\eta +c, \sigma + k)$ , where $0 \le k \le 2014$ , and since $p_{c,k} | \eta+c, p_{c,k} | \sigma + k$ , LHS $\ge p_{c,k} >1$ . Contradiction.

Comment: while the idea is easy, it takes great care to babysit all the details in the Chinese Remainder Constructions, as one easily runs into modulos not being coprime or remainder actually $\equiv 0$ which must be evaded if we wish to estimate the gcd. All the first half is done to generate an A.P. of $\mathcal B$ ‘s elements. I admit it can be annoying to see such problem posed in an exam, but we now see that all the crazy and daunting $2014$ ‘s are indeed red herrings (its status of red herring should be apparent on first glance), the factor that really matters here is the FINITENESS of all the indices, for which a Chinese Remainder will always work because we only need finitely many congruence equations to hold simultaneously–and we can use A LOT of difference congruence equations to make our life easy as there’s not taxation on considering many congruence equations at the same time.

Suppose $f:\mathbb N^+ \to \mathbb N^+$ satisfies:

1) $\gcd(f(m),f(n))=1$ if and only if $\gcd (m,n)=1$

2) $n\le f(n) \le n+2012.$

Show that $\forall n\in \mathbb N^+, \forall p$ prime, $p|f(n)$ implies $p|n$ .

This problem seems to be the precursor of the one in 2014, and is left to the reader as an exercise.

IMO

IMO 2013 Q5

Suppose $f:\mathbb Q^+ \to \mathbb R$ satisfies:

$f(x)f(y)\ge f(xy),\forall x,y\in \mathbb Q^+$
$f(x+y)\ge f(x)+f(y),\forall x,y \in \mathbb Q^+$
$\exists a \in \mathbb Q^+, a >1, f(a)=a.$

Show that $f(x)=x,\forall x \in \mathbb Q^+.$

All right. This looks like a spin-off of Cauchy equation, which, when fixed on rational numbers, admits only trivial solutions, and the deduction is done by first doing it on integers and then extending it to rational numbers.

The codomain being $\mathbb R$ hints that it is not advisable to iterate the function. We might want to perform preliminary investigation on it first.

Let the condition 1 be $P(x,y)$ , condition 2 be $Q(x,y)$ .

$P(1,a) \implies f(1) f(a) \ge f(a)$ , or, $f(1)a \geq a$ . Thus, $f(1) \geq 1$ , since $a>0$ .

$Q(n-1,1) \implies f(n)\ge f(n-1)+f(1)\ge f(n-1)+1$ . This can be used to inductively prove that $f(n) \ge n,\forall n \in \mathbb N^+$ .

$P(\frac mn , n)\implies f(\frac mn)f(n)\ge f(m)\ge m$ . Since $f(n) >0, f(\frac mn)\ge \frac m{f(n)}>0,$ where $m,n \in \mathbb N^+$ , and $\frac mn \in \mathbb Q^+.$

Let $x_1 < x_2, x_1, x_2 \in \mathbb Q^+, Q(x_1, x_2-x_1)\implies f(x_2)\ge f(x_1)+f(x_2 - x_1) > f(x_1).$ Thus $f$ is strictly monotically increasing.

That was the (trivial) preliminary investigation. We have obtained some upper bounds on the function’s values at integers, but further investigation seems beyond reach. This is because we cannot really find any upper bound on the function values $f(x)$ that does not involve further reference to function values.

(In fact, at this point, if the fixed point condition is ignored, $f(x)=x^2$ fits into all the above equations. I did not realise this when I attempted the problem, but it does, in hindsight, point at the necessity of utilising the fixed point condition.)

$P(a, a^{k-1})\implies f(a^{k-1})a\ge f(a^k)$ . This can be used inductively to prove that $a^k \ge f(a^k)$ .

YES! I has it! Upper bound! From now on we will just try to compare the function value with the powers of $a$ in order to apply a sandwich squeezing type of idea to fix the $f(x)$ because we were worried about $f$ growing too rapidly.

Claim: $\forall x \in \mathbb Q^+, f(x) \le x$ .

Fix $\lambda \in \mathbb Q^+$ . We define $l(x) = \left\lfloor \frac x \lambda \right\rfloor \lambda$ , and $u(x)= \left\lceil \frac x \lambda \right\rceil \lambda$ . We thus have $0\le u(x)-x < \lambda, 0\le x-l(x) < \lambda$ .

(Here we are defining extensions of floor and ceiling functions.)

Let $h:\mathbb N^+ \to \mathbb Q^+$ be $h(k)=a^{k+1} - a^k$ , and $g:\mathbb N^+ \to \mathbb Q^+$ be $g(k) = l(a^{k+1})-u(a^k)$ . Let $k\to \infty$ , as since $a>1$ , we have $g(k) \to \infty$ . We will let $k$ be large enough such that $g(k) >0$ . Thus $h(k) \ge g(k)$ , from which $\displaystyle \frac {f(h(k))}{f(g(k))}\ge 1$ .

$\displaystyle Q(h(k),a^k)\implies f(a^{k+1}-a^k) + f(a^k) \le f(a^{k+1}) \\ \implies f(h(k))\le f(a^{k+1})-f(a^k)\\ \le af(a^k)-f(a^k) =(a-1)f(a^k) \le (a-1)a^k \\ =h(k) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (*)$

as $f(a^{k+1}) \le af(a^k)$ and $f(a^k)\le a^k$ .

At this point we are still extending the property of $a$ to obtain more points with $f(x)\le x$ . But the next inequality involves the idea of approximating the “ $a$ polynomials” with “multiples” of $\lambda$ . The approximation idea is why we defined that generalisation of floor and ceiling function in the first place: we cannot use $a$ ‘s polynomials to attack $\lambda$ straightaway, we then do it approximately and then analysis will take care of the error.

On the other hand,

$\displaystyle P(\frac{g(k)}{\lambda},\lambda)\implies \\ f(g(k))\ge f(\frac{l(a^{k+1})-u(a^k)}{\lambda})f(\lambda)\\ \ge \frac{g(k)}{\lambda}f(\lambda) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (**)$

as $\frac {l(a^{k+1})-u(a^k)}{\lambda} \in \mathbb N^+$ (by the definition of $l(x)$ and $u(x)$ , and our choice of $k$ being large enough), and the fact that $f(n)\ge n, \forall n\in \mathbb N^+$ .

Dividing (*) by (**) (as both inequalities have their both sides positive), we get

$\displaystyle \frac {f(h(k))}{f(g(k))}\le \frac{\lambda}{f(\lambda)} \frac{h(k)}{g(k)} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (!)$ .

The equation (!) is our main breakthrough. We will very soon let both sides tend to their limit as $k\to \infty$ , thus the inequality will practically look like $1\le \frac {\lambda}{f(\lambda)}$ .

Thus it only remains to show that both $\lim _ {k \to \infty} \frac {h(k)}{g(k)}=1$ and $\lim _ {k\to \infty} \frac{f(h(k))}{f(g(k))}=1$ . The first one: $0\le h(k)-g(k) < 2\lambda$ , thus $\frac { h(k)-g(k) }{g(k)}<\frac {2\lambda}{g(k)}$ . Now let $g(k)\to \infty$ shows that $\lim _{k \to \infty}\frac { h(k)-g(k) }{g(k)}=0$ .

If we consider the worse case scenario, $h(k)-g(k)>0$ . But if the worse case does not happen, substituting $h(k)-g(k)$ into the functional inequality is illegitimate.

If $h(k)>g(k)$ , $Q(h(k)-g(k),g(k))\implies 0< f(h(k))-f(g(k)) \le f(h(k)-g(k)) < f(2\lambda)$ . (The last inequality is true by the monotonicity of $f$ !) If $h(k)=g(k)$ , $f(h(k))-f(g(k))=0<2\lambda$ .

In either case, $f(h(k))-f(g(k)) \in [0,2\lambda]$ is inevitable.

This is the approximation idea at work. We have successfully controlled the error uniformly. We only need to show that $f(g(k)) \to \infty$ as $k\to \infty$ to establish the claim.

But this is obvious since $f(g(k))\ge \frac {g(k)}{\lambda} f(\lambda)$ (As $\frac{g(k)}{\lambda}\in \mathbb N^+$ , and $f(qn) \ge nf(q),\forall n\in \mathbb N^+$ . And now $g(k)>(a-1)a^k -2\lambda \to \infty$ as $k\to \infty$ , our claim is proven.

We already have $f(n)\ge n, \forall n\in \mathbb N^+$ , and thus we automatically have $f(n)=n,\forall n\in \mathbb N^+$ .

$P(\frac mn , n) \implies nf(\frac mn) \ge f(m)=m$ . Thus $f(\frac mn ) \ge \frac mn$ . This combined with the claim, which requires $f(\frac mn) \le \frac mn$ , gives $f(\frac mn)=\frac mn ,\forall m,n\in \mathbb N^+$ .

Q.E.D.

IMO

Renhui Jiuzhang 2015 Exam 1 Q3

Suppose $f:\mathbb Z \to \mathbb Z$ satisfy $f(x-f(y))=f(x)^2+f(2x-f(y)),\forall x,y \in \mathbb Z,$ show that $f(f(x))=0,\forall x \in \mathbb Z.$

From this post on I will try to adopt a more casual tone in expounding the solution, with explanatory text mixing with the solution.

First, we see that the equation does not easily lead itself to non-trivial solution (the $f(x)^2$ term is quite weird), therefore we decide to punish it by repeatedly substituting different values of variables until we can compare the information about the values to find a contradiction.

Setting $x=0, f(-f(y))=f(0)^2 + f(-f(y))$ , and cancelling gives $f(0)=0$ .

Let $y$ be any integer, substituting $x=f(y)$ will give us $f(0)=f(f(y))^2+f(f(y)).$ Since the LHS vanishes, we thus have $f(f(y))=0$ or $-1,\forall f\in \mathbb Z$ . Thus we only have to rule out the latter case and the proof is complete.

Notice that the functional equation, though strange in $\mathbb Z$ , behaves benignly when only the parity is concerned: in fact, setting $f(x)=x$ , we have a ‘solution’ to it $\mod 2$ . Thus we want to consider parity. Setting $y=0$ , we have $f(2x)= f(x)-f(x)^2.$ The RHS, incidentally, is always an even number, whereas the LHS is the function value of any even number. Thus $f$ maps even numbers to even numbers. (Note that the same cannot be said of odd numbers as $f(x)=0$ is a solution to the equation.)

We aim to utilise the assumption that $\exists \xi \in \mathbb Z, f(f(\xi))=-1.$ We let $f(\xi)=\eta$ , for convenience. Let $y=\xi$ in the original equation, we obtain $f(x-\eta)=f(x)^2+f(2x-\eta)$ . Now we implant our initial strategy of trashing the function with repeated substitutions.

Let $x=\eta, y=0$ , we find $f(2\eta)=f(\eta)-f(\eta)^2 = -1-1=-2.$ Setting $x=2\eta,y=\xi$ , we thus have $f(\eta)=f(2\eta)^2+f(3\eta),$ thus $f(3\eta)= -1 -(-2)^2 =-5$ . We thus know that $-1,-2$ and $-5$ are all contained in the image of $f$ .

Setting $f(y)=-2$ , we have $f(x+2)=f(x)^2+f(2x+2)\equiv f(x) \mod \,2$ .

Setting $f(y)=-1$ , we have $f(x+1)=f(x)^2+f(2x+1)$ . Setting $x+2$ in the place of $x, \,f(x+3)=f(x+2)^2+f(2x+5)$ .

Setting $f(y)=-5$ , we have $f(x+5)=f(x)^2+f(2x+5)$ .

Subtracting the two equations above, we get

$\displaystyle f(x+3)-f(x+5)=f(x+2)^2 - f(x)^2 \ \ \ \ \ \ \ \ \ \ \ \ (*)$

(This is why we used $x+2$ instead of $x$ when $f(y)=-1$ , as that would permit us to subtract and reduce one term.)

Upto this point, we haven’t used any property of $\mathbb Z$ (we haven’t in fact used the parity condition). But in an Olympiad problem, we should aim to use all the given conditions, as the problems are almost always tailored such that the conditions just suffice for a solution using elementary method. Now we observe that the LHS of the equation (*) is the difference between two terms with distance $2$ apart, while the RHS has a factor that is also a difference between two terms with distance $2$ apart, with another factor whose absolute value is at least $1$ if we can make sure it is not zero. We want it to be $1$ . This can be done by inequality.

If $\forall x \in \mathbb Z, f(x+2)-f(x)=0$ , then $f$ is a constant on even number (with that value being thus $0$ as $f(0)=0$ ) and a constant on odd number (with that value thus being $-1$ as otherwise $-1$ would not be in the range of $f$ .) Now, we have shown that $-2$ is also in the image of the function, thus this is a contradiction.

Thus $\exists x\in \mathbb Z, f(x+2)-f(x)\ne 0$ . Consider the set $\{\left \vert f(x+2)-f(x)\right \vert \, | \, f(x+2)-f(x)\ne 0\}$ , with its minimal element being attained at $x=\sigma$ . Substitute $x=\sigma -3$ into (*), and take absolute value.

$|f(\sigma+2)-f(\sigma)|=|f(\sigma -1)-f(\sigma -3)| |f(\sigma -1)+f(\sigma -3)|$ .

By the minimality condition, $\lvert f(\sigma -1)-f(\sigma -3)\rvert \ge \lvert f(\sigma+2)-f(\sigma)\rvert$ , and $\lvert f(\sigma -1)+f(\sigma -3)\rvert\ge 1$ because it does not vanish (as the LHS is non-zero)

Multiplying them, we have equality in the face of two inequalities. Thus the two inequalities must have equality holding at the same time, thus $f(\sigma-1)-f(\sigma -3) =\pm 1$ . This is impossible since we have shown above that $f(x) \equiv f(x+2)\mod 2,\forall x\in \mathbb Z.$

Q.E.D.

Comment: The problem is not very difficult, and many alternative methods exist, as the function itself is quite bizarre and repeated substitution per se gives more and more information from which any contradiction would finish the problem off.

The problem is proposed by Qiang Shen, and used in a practice exam at Renhui Jiuzhang MO Tuition Centre (Beijing, China) in 2015.

Uncategorized

IMO 2009 Q3

Let $f: \mathbb N^+ \to \mathbb N^+$ be a strictly increasing function, such that $f(f(n))$ and $f(f(n)+1)$ are both arithmetic progressions in $n$ . Show that $f(n)$ itself is an arithmetic progression.

Let $f(f(n))=an+b, f(f(n)+1)=cn+d$ .

Consider set $M= \{m| \exists n\in \mathbb N^+,f(n+1)-f(n)=m\}$ . We claim that this set is bounded, thus finite.

It is bounded below by $1$ by the strict monotonicity. If it was not bounded from above, we have $\exists n\in \mathbb N^+, f(n+1)-f(n) >a$ . Now, since $f(f(n))=an+b,$ and that $f$ is strictly increasing, $f(f(n)+1)\ge f(f(n))+1, f(f(n)+2) \ge f(f(n)+1) +1......$ Thus $f(f(n)+(f(n+1)-f(n)))\ge f(f(n))+f(n+1)-f(n)>f(f(n))+a.$ This is impossible because $f(f(n+1))=f(f(n))+a.$ Thus $M$ is bounded, and thus finite.

We claim that $a=c$ . If $a>c$ , for $n$ large enough, we must have $an+b > cn+d$ , which contradicts the monotonicity of $f(n)$ . If $a<c$ , we then have $f(f(n)+1)-f(f(n))=(c-a)n+d-b$ which is unbounded for $n\to \infty$ . But we know that $(c-a)n+(b-d) \in M$ which is bounded. This is a contradiction. Thus $a=c$ .

Apply $f(n)$ to both sides of $f(f(n))=an+b$ , we have $f(an+b)=f(f(f(n)))=af(n)+b.$

Consider the minimal element of $M$ , let it be $\mu$ , attained at $n=\eta$ . Let $n=\eta$ and $\eta +1$ in $f(an+b)=af(n)+b$ , we thus have $f(a\eta +a+b)=af(\eta+1)+b=af(\eta)+a\mu+b.$

Because $\mu$ is the minimal element of $M$ , it is thus necessary that $f(a\eta + b+k)\ge k\mu +f(a\eta +b)=k\mu +af(\eta)+b.$ In particular, the equality is attained if and only if $f(a\eta + b + j+1)-f(a\eta + b +j)=\mu, \forall 0\le j \le k-1.$ Let $k=a, f(a\eta +b +a) \ge a\mu + af(\eta)+b=f(a\eta +b +a).$ Thus equality IS attained and we must have $f(a\eta+b+1)-f(a\eta+b)=\mu$ .

Recall that $a\eta+b=f(f(\eta))$ , letting $n=f(\eta)$ in the problem’s condition gives $f(a\eta+b)=f(f(f(\eta)))=af(\eta)+b,$ and $f(a\eta +b +1)=f(f(f(\eta))+1)=af(\eta)+d.$ Since $f(a\eta + b +1)-f(a\eta+b)=\mu,$ that implies $d-b=\mu.$

Let the maximal element of $M$ be $\nu$ , and repeat the same argument above, we would also have $d-b = \nu$ . Thus $M$ is a single-element set, or, the difference $f(n+1)-f(n)$ is a constant for all $n\in \mathbb N^+$ . This proves the statement.

Q.E.D.

Comment: Superficial investigation can only lead one to $a=c$ and $af(n)+b = f(an+b)$ , and it becomes difficult to move on from here as one has to disentangle the iteration of the function. The problem only gives very limited information about the values attained by $f$ , and the information accumulate near the range of the iteration. We see that this range is in general not the same as $\mathbb N^+$ , and thus we have to find an argument to integrate the scattered local information. The definition of $\mu$ and $\nu$ plays this role by interacting directly with the function values elsewhere (considering $f(a\eta + b +k)'$ s values and differences between two consecutive terms, where the ‘equality of the global inequality implies all local equalities’ is really the fruit of the global consideration in defining $\mu$ ).

After knowing that $f(y+1)-f(y)=\mu$ implies $f(ay+b+1)-f(ay+b)=\mu$ , iterating the linear function to try to give a full description of the set of positive integers on which the consecutive difference is minimalised is a natural idea — but turns out uneconomical: it is not clear how to force the subset that minimalise the consecutive difference and the subset that maximises the difference to intersect in that manner. In fact if that could be done the second problem condition becomes unused in deriving the solution–uncommon for Olympiad problems. Thus we seek to show that the subset of $\mathbb N^+$ on which the consecutive difference is minimised (maximised) intersects the image of $f$ instead, which is already done.

I reckon this problem is quite nice (except its original formulation in terms of sequences which uses sub-sub-scripts which is painful to read), as one does not have access to any function value at any point (thus avoiding some ad hoc phenomena) but instead requires conceptual consideration. It is impossible to gauge the consideration of the function with any non-trivial solution, as there isn’t any.

When the functional equation acts on integer sets, it is almost always (practically, the ‘almost’ is redundant in Olympiads) important to consider properties characteristic of integers (extremal elements, number theory, discreteness, etc.) as if a solution without these considerations is possible the problem proposer would just define it on a wider domain. Because direct comparison of values maybe impossible, it might also be useful to consider asymptotic behaviours of certain auxiliary functions to gain information about parameters (here the proof that $a=c$ .)

The problem is proposed by Gabriel Carroll, USA, and appeared in the IMO 2009 as Q3.

IMO

Australia TST 2013 Exam2 Q3

Find all values of $n \in \mathbb {N} ^+$ such that there exists a function $f: \mathbb {R} \to \mathbb {R}$ that satisfies the following properties:

1), $f(x)=0$ if and only if $x=0$ .

2), $\forall x \in \mathbb R,\, f(x) + f(2x) + ... + f(nx) =0$ .

Answer: $\forall n \geq 2, n\in \mathbb {N}^+$ .

Proof: $n=1$ does not fit into the criteria because it requires $f(x)=0,\forall x \in \mathbb R$ . Fix $n \geq 2,n\in \mathbb N ^+$ .

Bertrand’s Postulate (a.k.a. Tchebyshev’s theorem): $\forall m \in \mathbb {N}^+, \exists p, m<p \leq 2m$ , with $p$ prime.

Now we aim to find a $p$ such that $p\leq n <2p$ .

For $n=2$ , take $p=2$ . For $n$ odd, $n\geq 3$ , apply Tchebyshev’s theorem to $\left\lceil\frac{n}{2}\right\rceil$ , there exists a prime $p, \frac {n+1}{2} < p \leq n+1$ . But now $n+1$ is even and $n+1 \geq 4$ thus $n+1$ is not prime, and thus we have $p \leq n$ , which shows that $p$ is the desired prime number as $2p > n+1 >n$ . For $n$ even, apply Tchebyshev’s theorem to $\frac {n}{2}$ to yield a prime $p, \frac {n}{2} <p \leq n$ which gives $p\leq n <2p$ . The $p$ has been chosen for all $n$ .

Let $\mathbb Q ^*= \mathbb Q \backslash \{0\}$ , $\mathbb R ^*= \mathbb R \backslash \{0\}$ . Let $\mathbb Q_n = \{q\in \mathbb Q^* | q \textnormal { can be represented as }\frac {\alpha} {\beta},\, \alpha, \beta \in \mathbb Z, \textnormal{ where all prime factors of }\alpha \textnormal{ and }\beta \textnormal { do not exceed } n\}$ .

(E.g. let $n=3$ , then $Q_3 = \{q|q=\pm \frac {2^\eta}{3^\xi}, \eta,\xi \in \mathbb N ^+ \cup \{0\}\} \cup \{q|q=\pm \frac {3^\eta}{2^\xi}, \eta,\xi \in \mathbb N ^+ \cup \{0\}\}$ .

Define an equivalence relation on $R^*$ : for $x,y \in \mathbb R^*$ , $x \sim y$ if and only if $\frac {x} {y} \in \mathbb Q_n$ . It is easy to verify that this is indeed an equivalence relation. Partition $R^*$ into equivalence classes $K_{\gamma}$ , by this relation. Let $\gamma$ be indexed by the set $\Gamma$ .

Axiom of Choice: If $K_{\gamma}$ is a family of sets indexed by the set $\Gamma$ , then the Cartesian product $\prod _ {\gamma \in \Gamma} K_{\gamma}$ is non-empty.

Apply Axiom of Choice to the equivalence classes of $R^*$ , and we get a family of elements $\kappa _\gamma$ , with each $\gamma \in \Gamma$ corresponding to exactly one $\kappa _ {\gamma}$ .

Let $v_p(q)$ be the $p$ -adic evaluation of $q\in Q^*$ . (That is, reduce $q$ to simplest form $\frac {\alpha}{\beta}$ , $v_p(q)= \textnormal{highest index of }p \textnormal{ dividing } \alpha$ if $p$ does not divide $\beta$ , and $v_p(q)= - \textnormal{highest index of }p \textnormal { dividing } \beta$ if $p|\beta$ .

Let $f(\kappa _ \gamma) =1,\forall \kappa _\gamma$ . For $x\in \mathbb R ^*$ , suppose $x\in K_g, g \in \Gamma$ . Define $f(x)= (-n+1)^{v_p(\frac{x}{\kappa _g})}$ . (E.g. if $n=3, p=3, x= \frac {2\pi}{3}, x \in K_g, \kappa _g =\pi, f(x)= (-2)^{(v_3(\frac 23))}=-\frac 12$ .Similarly, $f(2x)=f(\frac {4\pi}{3})= -\frac 12$ . This gives $f(x)+f(2x)+f(3x)=(-\frac 12) + (-\frac 12) + 1=0$ .) We set $f(0)=0.$

Indeed, we show first show that the function satisfies the conditions.

First, we see that $f(x)$ does not vanish for non-zero $x$ .

We claim that if $x,y \in K_g, f(x)/f(y)= (-n+1)^{v_p(\frac{x}{y})}$ . This is obvious by substituting the definitions of $of f(x)$ and $f(y)$ , and then LHS $=(-n+1)^{v_p(\frac{x}{\kappa_g})-v_p(\frac{y}{\kappa_g})}=(-n+1)^{v_p(\frac{x}{y})}=$ RHS.

Now, we verify the conditions. Condition 1 is already checked. If $x=0$ , $f(x)+f(2x)+...+f(nx)=0+0+...+0=0$ . If $x \ne 0$ , let $x \in K_g$ . For $jx$ with $j\ne p$ , we have $v_p(\frac {jx}{x})=v_p(j)=0$ , and thus $f(jx)=f(x)$ . Since $p\leq n < 2p$ , there are $(n-1)$ such $j'$ s. $f(px)=(-n+1)^{v_p(\frac{px}{x})}f(x)=(-n+1)f(x)$ .

Thus $f(x)+f(2x)+...+f(nx)= (n-1)f(x)+(-n+1)f(x)=0$ . We have found the desired function, for each of $n\in \mathbb N^+,n\ge 2$ .

Q.E.D.

Comment: to be written later.

IMO

IMO 2011 Q3

$f: \mathbb {R} \to \mathbb {R}$ satisfies $f(x+y) \leq yf(x)+f(f(x))$ for all real numbers $x$ and $y$ . Show that $f(x)=0$ for all $x \leq 0$ .

First, set $y=0$ gives us inequality $f(f(x)) \geq f(x)$ for all $x\in \mathbb R$ .

Let the inequality be denoted by $P(x,y)$ .

$P(x, f(y)-x)$ gives us $f(f(y)) \leq (f(y)-x)f(x) + f(f (x))$ for all $x,\,y \in \mathbb R$ . Similarly, we have $f(f(x)) \leq (f(x)-y)f(y) + f(f(y))$ , by switching $x$ and $y$ .

Adding the two inequalities up, we get $2f(x)f(y) \geq xf(x) + yf(y),\, \forall x,\,y \in \mathbb R$ . Let $y=2f(x)$ in this inequality, we see that $xf(x) \leq 0 \, \forall x \in \mathbb R$ .

If $x<0$ , we see that from $xf(x) \geq 0$ , we get either $f(x)=0$ or $f(x) >0$ . We now try to rule out the latter case, by observing that replace $x$ in the inequality $xf(x) \leq 0$ with $f(x)$ and we get $f(x)f(f(x)) \leq 0$ . This demands $f(f(x))$ to be non-positive.

Now, since $f(x)$ is positive, $f(f(x))$ is non-positive, we have $f(f(x)) < f(x)$ for that certain $x<0$ , which contradicts our initial inequality $f(f(x)) \geq f(x)$ . Thus this cannot happen and $f(x)=0,\, \forall x<0$ .

It remains to show $f(0)=0$ . Now, we re-use the inequality $f(f(x)) \geq f(x)$ by letting $x$ be any negative number, which gives off $f(x)=0$ and thus $f(0) \geq 0$ .

$P(0,y)$ gives $f(y) \leq yf(0) + f(f(0))$ . Assume now that $f(0) > 0$ , and let $y \to - \infty$ , which requires $yf(0)+ f(f(0)) \to - \infty$ since $f(0)$ is positive, and thus we see for $y<0,\, |y|$ large enough, $f(y) <0$ , which is impossible as now $y$ is negative and $f(y)=0$ . Contradiction. Thus $f(0)>0$ has been wrong which combined with $f(0) \geq 0$ gives $f(0)=0$ .

Q.E.D.

Comment: The functional inequality does not lead to simple non-trivial solution, and we thus hope to exploit the “badly-behavedness” of the condition by reducing it to something simple yet non-trivial. (In this problem’s case, the inequaity $xf(x) \leq 0$ .) Since the condition is an inequality, it is not easy to derive an equality out of it. In this solution we established equality from both sides, to thus force the equality to be true.

The motivation for the substitution $y \to f(y)-x$ is to yield a $f(f(y))$ term on one side, being symmetric to the $f(f(x))$ term on the other side. Since on the other side $y$ only appears once and appears outside $f$ , we can afford to substitute a relatively complicated form of $y$ . Once we reach $2f(x)f(y) \geq xf(x) + yf(y)$ , substituting $y \to 2f(x)$ is simply giving up the strength of that inequality while preserving its non-triviality. It should be noted that substituting $x=y$ leads to weaker inequality $f(x)^2 \geq xf(x)$ .

The difficulty of the problem lies in the difficulty in dealing with the iterated application of $f$ , given that it is not easy to find a non-trivial solution to this equation–under the pressure of IMO and the anxiety of the windmill problem. (I personally do not know of any elementary non-trivial solution to the inequality, which nonetheless makes it a great problem.) Also, functional inequality is much less common than functional equations. I reckon that if it appeared on the IMO as Q2 instead with the windmill problem being Q3, it would be better done–people would likely spend more time on it. And it proves itself not as challenging as the windmill problem after all!

This solution is probably very close to the official solution.

The problem is proposed by Igor Voronovich, Belarus, and appeared in IMO 2011 as Q3.

MathFashion

The Earth is Round, Like an Orange!

IMO 2017 Q2

Iran TST 2011 Q5

Special topic: Three sides of a triangle

Online Algebra Olympiad 2016 Q5

China TST 14′ Q3 & USA TSTST 12′ Q3

IMO 2013 Q5

Renhui Jiuzhang 2015 Exam 1 Q3

IMO 2009 Q3

Australia TST 2013 Exam2 Q3

IMO 2011 Q3