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.)

Advertisements
Standard
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.

Standard
IMO

IMO 2013 Q5

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

  1. f(x)f(y)\ge f(xy),\forall x,y\in \mathbb Q^+
  2. f(x+y)\ge f(x)+f(y),\forall x,y \in \mathbb Q^+
  3. \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.

 

 

 

 

 

 

 

 

 

Standard
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.

 

 

 

 

 

 

 

 

 

 

 

 

Standard
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.

Standard
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.

 

 

 

Standard
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.

Standard