Problem 5

Determine all functions

f

from the set of positive integers to the set of positive integers such that, for all positive integers

a

and

b

, there exists a non-degenerate triangle with sides of lengths

a

f(b)

and

f(b+f(a)-1)

. (A triangle is non-degenerate if its vertices are not collinear.)

Step 1 of 4: f(1) = 1 and f is an involution

Previous step Next step

In plain words

The degenerate side of length 1 in the triangle inequality is the most restrictive, so testing a=1 pins down f(1), and testing b=1 afterward makes f its own inverse.

f(1)=1,\qquad f(f(n))=n\ \text{ for every } n

Detailed analysis

Taking $a=1$ : the triangle with sides $1,f(b),f(b+f(1)-1)$ has two sides differing by less than the third side $1$ ; since $f(b)$ and $f(b+f(1)-1)$ are integers, they must be equal, for every $b$ . If $f(1)>1$ , set $N=f(1)-1\ge1$ ; then $f(b)=f(b+N)$ for all $b$ makes $f$ periodic with period $N$ , hence bounded, say $f\le B$ always. But taking $b$ fixed and $a$ arbitrarily large in the original condition needs $a<f(b)+f(b+f(a)-1)\le 2B$ , impossible for large $a$ . So $f(1)=1$ . Now take $b=1$ : the triangle with sides $n,f(1)=1,f(1+f(n)-1)=f(f(n))$ again has two sides ( $n$ and $f(f(n))$ ) differing by less than the third side $1$ , so being integers, $f(f(n))=n$ for every $n$ .