Special topic: Three sides of a triangle

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


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,


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


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


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s