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

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