Remark: If a triangle with have sidelengths 1,a,b with a,b positive integers, then it's forced by triangle inequality that a=b. 1. Put a = 1, then remark tells us that $ f(b) = f(b + f(1) - 1)$ 2. Claim $ f(1) = 1$. Otherwise $ f(1) - 1 > 0$, which means that $ f$ repeats itself every $ f(1) - 1$ numbers. This means that $ f$ can take finitely many values, so if we take $ a$ sufficiently large, $ a$, $ f(b)$, $ f(b + f(a) - 1)$ cannot be a triangle. 3. Put b = 1, then $ a, 1, f(f(a))$ is a triangle. This implies that $ f(f(a)) = a$ by remark. 4. Claim $ f(n) = (n - 1)f(2) - (n - 2)$ by induction. By 3, $ f$ is bijective, so we now know that $ a,b, f(f(a) + f(b) - 1)$ is a possible triangle. This means that $ f(f(a) + f(b) - 1) < a + b$. Take a = b = 2, then $ f(2f(2) - 1) < 4$, i.e. it can either be 1, 2 or 3. 1 is not possible for that would mean $ 2f(2) - 1 = 1$, i.e. f(2) = 1, contradicting to bijectivity of $ f$. 2 is not possible for that would mean $ 2f(2) - 1 = f(2)$, i.e. f(2) = 1, again contradiction. So it must be 3, i.e. $ 2f(2) - 1 = f(3)$, proving the hypothesis for $ n = 3$. The induction step involves exactly the same argument, by taking $ a = 2, b = n$, and argue that $ f(f(2) + f(n) - 1) = n + 1$. 5. The formula for $ f$ tells us that $ f$ is strictly increasing. Suppose that $ f(i) = i$ for $ i = 1, 2, ..., k - 1$. If $ f(k) > k$, then as $ f$ is increasing nothing can map back to $ k$, contradicting to the bijectivity of $ f$. So $ f(k) = k$. By induction $ f(n) = n$ for all $ n$.

How do you come to repetition when f(1)>1?

$ f(1)>1$, then $ f$ is a peroidic funciton, and let $ k$ be the period, then $ a+nk, f(b), f(b+f(a)-1)$ are triangle's length. A contradiction when let $ a,b$ constant.

I got essentially the same solution as Soarer, but instead of constructing a recursive formula - I simply proved that the function is strictly increasing. The problem is clearly better than the second problem - a bit harder, but still classic and straightforward, nothing extraordinary.

Well, Erken, I think proving the function is strictly increasing is easier actually without using the recursive formula. You can give a proof by contradiction asuming the function to be decreasing at some point. Anyway, giving the recursion appears better. other than that, had the same solution as you both. Infact, I kind of guessed the result in the beginning first and saw. That perhaps helped. Any other solution guys?

The 5th step of Soarer's solution can be done by setting $ n=f(2)$, which gives $ (f(2)-1)^2=1$. All in all, this problem doesn't require a lot of ingenuity; the solution isn't as obvious as in #2, but still can be reached using only standard techniques. Both second problems were relatively easy this year, so the silver cutoff might jump up a little...

I have the same solution.But to complete the proof I proved $ f(f(n))=n$ so that $ f(n)\geq n$ imply $ f(n)=n$ for all n.

khashi70 wrote: Hi ... I don't agree with u bertram ... both the problems $ 4$ and $ 5$ weren't easy enough to silver cut off jump for that reason . I spoke with some IMO participant and they were also agree with me ... I think the silver cut off is gonna be 21 or 22 because only problems $ 1$ and $ 2$ were too easy . You should express your opinions about results and cut off-s in respective topics.

Let a=1, b=1, then 1, f(1), f(f(1)) is non-degenerate, so f(1) = f(f(1)) = k, say. Let a=1, b=k, then 1, k, f(2k-1) is non-degenerate so f(2k-1) = k. Let a=1, b=2k-1, then 1, k, f(3k-2) is non-degenerate, so f(3k-2) = k. Let a=1, b=3k-2, then 1, 3, f(4k-3) is non-degenerate, so f(4k-3) = k. Let a=4k-3, b=1 then 4k-3, k, f(2k-1) is non-degenerate, which means f(2k-1) > 3k-3. But f(2k-1) = k, then k > 3k-3, so k = 1, i.e. f(1) = 1.

I have the same solution as in the first post and don't think it has very different solutions.

I got my solution a bit harder way, as I missed the periodicity idea: Let $ g(x) = f(x) - 1$, then the 3-uple of numbers turns into $ a, g(b) + 1, g(b + g(a)) + 1$. The inequality $ a + f(b) > f(b + f(a) - 1)$ transforms into $ a + g(b) > g(b + g(a))$. It is then a straightforward induction to obtain $ na + g(a) > g(a + ng(a))$ (*) for all positive integers $ a, n$. I claim now that $ g(a) \leq a$. Assume the converse, and fix $ x$ s.t. $ g(x) > x$. Now exploit another inequality, $ g(b) + 1 + g(b + g(a)) + 1 > a$, or $ g(g(a) + b) > a - g(b) - 2$ (**). To make use of this, observe that we can write $ g(a) + b$ as $ g(x)k + x$ with $ b \in \{1, 2, ... g(x)\}$ and $ k = \frac {g(a) + b - x}{g(x)} \in \mathbb{N} \cup \{0\}$. Now we can combine both (*) and (**): $ kx + g(x) > g(kg(x) + x) = g(g(a) + b) > a + g(b) - 2$ and plugging in $ k = \frac {g(a) + b - x}{g(x)}$ we get $ xg(a) > g(x)(a + g(b) - 2 - f(x)) - b + x = g(x)a + (a term that is bounded)$, thus, dividing both sides by $ x$ gives that for $ a$ large enough, $ g(a) > ca$ for some constant $ c > 1$. This, however, immediately contradicts (*) for $ a = x$ and $ n$ large enough: $ nx + g(x) > g(x + ng(x)) > c(x + ng(x)) > cx + cg(x)n$, which cannot hold for $ n$ large. This shows that $ g(a) \leq a$ (***). Thus, $ f(a) \leq a + 1$. In particular, this implies that $ f(1)$ is either $ 2$ or $ 1$, which we deal with case by case: In the first case, playing with small values of $ a, b$ shows it is not possible: $ f(1) = 2$, thus for $ a = b = 1$ we have the three sides of the triangle to be $ 1, 2, f(2)$, so $ f(2)$ also equals $ 2$. Plug now $ a = 1, b = 2$ to get the triple $ 1, 2, f(3)$ must comprise sides of a triangle, so $ f(3) = 2$, and inductively, $ f(n > 1) = 2$, which cannot be (f is clearly unbounded). In the second case, $ f(1) = 1$, so making $ b = 1$ gives $ 1, a, f(f(a))$ must make sides of the triangle. That leads to $ a - 1 < f(f(a)) < a + 1$, so $ f(f(a)) = a$. Put now $ f(a)$ instead of $ a$ in the very initial number triple to transform it into $ f(a), f(b), f(a + b - 1)$.(****) Now assume there's an $ x$ such that $ f(x) > x$, pick the minimal such $ x$. Then, by (***), $ f(x) = x + 1$. If $ x > 2$, then let $ a = 2, b = x - 1$ to turn (****) into $ f(2), f(x - 1), f(x)$. But now, $ f(2) + f(x - 1) \leq 2 + x - 1 = x + 1 = f(x)$, a contradiction. If $ x = 2$, put $ a = b = 3$, then $ 2f(3) > f(5)$, and since $ f(3) = f(f(2)) = 2$, we must have that $ f(5) = c \leq 3$. But $ 5 = f(f(5)) = f(c) \leq c + 1 \leq 4$, a contradiction. This shows that, in fact, $ f(a) \leq a$ for all $ a$, and, combined with $ f(f(a)) = a$, implies $ f(a) = a$. I hope it's ok, please let me know if you find any flaws

I hope this is correct: After showing that $ f(1) = 1$ and $ f$ is injective, one can proceed as follows: let $ k = f(2)$ and fix $ b$. Then $ |f(b + k - 1) - (b)| = 1$. If $ f(b + k - 1) = f(b) - 1$, then $ f(b + t(k - 1))$ has to be $ f(b) - t$, for all $ t$, for otherwise $ f(b + (m - 2)(k - 1)) = f(b + m(k - 1))$ for some $ m$, but $ f$ is injective. This is impossible. Thus $ f(b + t(k - 1)) = f(b) + t$. Let $ A = \{b + t(k - 1)|t\ge0\}$. If $ k > 2$, then $ f(A)$ contains all but finitely many positive integers, while $ \mathbb N\setminus A$ is infinite. So $ k = 2$, and plugging $ b = 2$ we conclude $ f(n) = n$.

I proved that $ f(1) = 1$ since otherwise $ f$ would be bounded above and that can't happen. Then I proved that $ x = f(f(x))$. Then I proved that $ f(2) = 2$ by proving that if $ f(2) =k>2$, then there exist two distinct integers, $ a=2$ and $ b=(k-1)k-(k-2)$ such that $ f(a)=f(b)=k$, contradicting the bijection. I then used induction to show that since $ f(2) + f(x - 1) > f(x)$, we must have $ x + 1 > f(x) > x - 1$, so $ f(x) = x$.

f(1) = 1, and f(f(x))=x, as everyone else has. The second implies that f is injective. Induct strongly; assume f(1)=1, f(2)=2, ..., f(x-1)=x-1. Assume $ f(x)\neq x$, by injectivity, f(x)=k>x. We can then get $ f(k + b - 1) - f(b)\le x - 1$ for all $ b$. We then find f(k)=x, f(k+1)=x+1, ..., f(x+k-2)=2x-2, then we can get f(2k-1)=2x-1, and keep going. Using the fact that k>x, we can check that these groups of x-1 consectuve values are disjoint. We generate, for all y>k, f(y) such that f(y)=z for all z>x. But we then get some y such that f(y)=k, but we have f(x)=k, contradicting injectivity.

First we assume that $ f(1)-1>0$ Let $ g(x)=x-f(x)$ Then: $ a+f(b)\geq f(b+f(a)-1)+1$ is equal to: $ g(a)+g(b+f(a)-1)\geq g(b)$ If $ a=1$ $ \implies 0> g(1) \geq g(b)-g(b+f(1)-1)$ $ \implies g(b+f(1)-1)> g(b)$ Then there exist $ m$ such that for all $ h\geq m$, $ g(h)\geq 0$. And we can take $ a$ such that $ g(a)$ is infinitely large. $ f(b)+f(b+f(a)-1)\geq a+1$ is equal to: $ 2b-2 \geq g(b)+g(a)+g(b+f(a)-1)$ But it is impossible taking $ b=m$ and $ a$ very large. Then $ f(1)=1$ Then its obvious that $ f(f(a))=a$ So $ f$ is bijective. Then $ a+f(b)\geq f(b+f(a)-1)+1$ Let $ b$ such that $ f(b)=2$ Then $ a+1\geq f(b+f(a)-1)$ Hence we can prove by induction on $ a$ that (like $ f$ is bijective) $ a+1=f(b+f(a)-1)$ But $ b+f(a)-1$ is all the natural numbers only for $ b=2$ $ \implies a+1=f(f(a)+1)$ $ \implies f(a)+1=f(a+1)$ And $ f(n)=n$ for all $ n$.

Should be problem 1 or 4.

mozilla wrote: Should be problem 1 or 4. More like problems 4 and 5 should have been swapped (according to the results.)

Here is my solution ( I hope It's sth different from the above ones ) It's easy to prove that $ f(1) = 1$ and that $ f$ is bijective. Put $ a = 2$,It follows that $ 2,f(b)$ and $ f(b + f(2) - 1)$ are side lenghts of a triangle,then $ f(b) - 1 \leq f( b + f(2) - 1 ) \leq f(b) + 1$,which gives 3 possibilities: $ (*)$ $ f( b + f(2) - 1 ) = f(b)$ $ \Rightarrow$ $ b + f(2) - 1 = b$ $ \Rightarrow$ $ f(2) = 1$ , Contradiction ! $ (*)$ $ f( b + f(2) - 1 ) = f(b) - 1$,let $ k = f(2) - 1$ which gives that $ f(b + k) = f(b) - 1$,and from this we can establish that : $ (\forall n \in \mathbb{N*}) : f(b + n.k) = f(b) - n$,which leads to contradiction when $ n \rightarrow \infty$. Hence,$ f( b + f(2) - 1 ) = f(b) + 1$,use induction to prove that $ ( \forall n \in \mathbb{N*} )$ : $ f( 1 + n.k ) = n + 1$ where $ k = f(2) - 1$.Let $ A =${ $ f(1 + n.k) / n \in \mathbb{N*}$ },We have that $ A = \mathbb{N*} -${$ 1$}. Hence,If $ k > 1$ we'll have that $ 1 \leq k - 1 < 1 + k \leq 1 + n.k$ which means that $ f(k - 1) = 1 = f(1)$ $ \Rightarrow$ $ k = 2$ $ \Rightarrow$ $ f(2) = 3$ and $ f(b + 2) = f(b) + 1$ $ \Rightarrow$ $ f(2) = 3$ and $ f(5) = 3$ which is absurd.We conclude that $ k = 1$,It follows that $ f(n + 1) = f(n) + 1$ which obviously gives that $ f(n) = n$.

$ f(b) + f(b + f(a) - 1) > a$ $ f(b) + a > f(b + f(a) - 1)$ $ f(b + f(a) - 1) + f(b) > a$ $ \implies$ $ f(b + f(a) - 1) + 2a > f(b) + a > f(b + f(a) - 1)$ $ a = 1$ $ \implies$ $ f(b + f(1) - 1) + 2 > f(b) + 1 > f(b + f(1) - 1)$ $ \implies$ $ f(b) = f(b + f(1) - 1)$ $ \implies$ $ f(f(1)) = f(1)$ $ \implies$ $ f(1) = c$ $ \implies$ $ f(c) = c$ $ f(c) = f(2c - 1) = f(3c - 2) = ... = c$ $ f(c) + f(c + f(3c - 2)) - 1) > 3c - 2$ $ \implies$ $ c\leq 1$ $ \implies$ $ c = 1 = f(1)$ $ \implies$ $ a - 1 < f(f(a)) < a + 1$ $ \implies$ $ f(f(a)) = a$ $ f(2) = k$ $ \implies$ $ f(b + k - 1) < f(b) + 2$ ,$ f(b + k - 1) > f(b) - 2$ $ \implies$ $ i)f(b + k - 1) = f(b) - 1$ assume that this equation is done by $ b\in N$ $ \implies$ $ k - 1 = m$ $ f(b + m.l) = f(b) - l$ contradiction! $ ii)f(b + k - 1) = f(b)$ assume that this equation is done by $ b\in N$ $ \implies$ $ b = b + f(2) - 1$ $ f(2) = f(1) = 1$ contradiction! $ f(b + f(2) - 1) = f(b) + 1$ $ \implies$ $ f(2) - 1 = m$ $ \implies$ $ b = k + m$ $ \implies$ $ f(k + 2m) = f(k) + 2$ $ \implies$ $ b = q + l.m$ $ \implies$ $ f(q + (l + 1).m)) = f(q) + l + 1$ $ \implies$ $ q = 1$ $ \implies$ $ f(1 + (l + 1).m) = l + 2$ , $ l + 1 = p$ $ \implies$ $ f(1 + p.m) = p + 1$ $ \forall p\in N$ $ f(b + k - 1) = f(b) + 1$ $ \implies$ $ f(k + 1) = k + 1$ $ \implies$ $ k + 1 = 1 + k.m$ $ \implies$ $ m = 1$ $ \implies$ $ f(2) = 2$ $ \implies$ $ f(b + 1) = f(b) + 1$ $ \implies$ $ f(b + n) = f(b) + n$ $ \implies$ $ f(n + 1) = n + 1$ $ \implies$ $ f(x) = x$ $ \Box$ sorry for my bad english

1,b: f(b)=f(b+f(1)-1) => f is bounded => contraction. a,1: f(f(a))=a. Assuming f is not the identity, let a be a positive integer such that f(a)-1=:c>a-1 f(b+Kc)<=f(b+(K-1)c)+(a-1)<=...<=f(b)+K(a-1)<= K(a-1)+const(a). So f(x)<x for large enough x, which is clearly a contradiction. Hence, the identity function is the only one that works.

Spectator wrote:

Legend says he still hasn't found time to rigorously do this We claim the answer is f(x)=x only By triangle inequality, for lengths m,n,1 we have m=n. For a=1, it is easy to see that f(b)=f(b+f(1)-1). If f(1)-1 is not 0, then f(b) is periodic with period f(1)-1 not infinite, meaning f can only take on f(1)-1 values, contradiction. Then f(1)=1. Taking b=1, a=f(f(a)), so f is an involution and therefore a bijection. We know a, f(b), f(b+f(a)-1), or a, f(f(b))=b, f(f(b)+f(a)-1) (substitute f(b) instead of b) form a triangle. a=b=2, we have f(2f(2)-1)<4. LHS cannot be 1 since that would imply 2f(2)-1=1, or f(2)=1=f(1). LHS is not 2 since that implies f(2)=3/2, not an integer. So we have f(2)=2. At a=2, f(b)-1$\le$f(b+f(2)-1)$\le$f(b)+1 by triangle inequality. Now we casework: f(b+1)=f(b+f(2)-1)=f(b)-1, contradiction since this means f is strictly decreasing. f(b+1)=f(b+f(2)-1)=f(b), contradiction since f is constant. Finally, we have f(b+1)=f(b+f(2)-1)=f(b)+1, and inductively this holds so f ranges over all positive integers, and this is the only solution.

huashiliao2020 wrote: Spectator wrote:

Legend says he still hasn't found time to rigorously do this the real rigorous solve was the friends we made along the way

The only solution is $f(x) = x$ for all $x \in \mathbb{Z}_{>0}$. It is easy to confirm that this solution works. Denote the given assertion as $P(a, b)$. $P(1, b)$ states that $1, f(b), f(b + f(1) - 1)$ are the sides of a non-degenerate triangle. Hence, $f(b) = f(b + f(1) - 1)$ for all $b \in \mathbb{Z}_{>0}$. Case 1: $f(1) > 1$. Note that $f$ is periodic with period $f(1) - 1$, and thus has a maximum $M$. However, the assertion $P(2M, 1)$ states that $2M \geq f(1) + f(f(1)) > 2M$. Contradiction. Case 2: $f(1) = 1$. $P(a, 1)$ states that $a, 1, f(f(a))$ are the sides of a non-degenerate triangle. Thus, $a = f(f(a))$ and so $f$ is a bijection. Let $g(a) = f(f(a) + f(2) - 1)$ for all $a \geq 1$. Furthermore, $P(a, f(2))$ states that $a, 2, g(a)$ are the sides of a non-degenerate triangle. By the Triangle Inequality, \[g(a) \in \{a-1, a+1\}\](since $f(a) + f(2) - 1 > f(a)$ and $f$ is bijective, $g(a) \neq a$). Note that by injectivity, all $g(a)$ are distinct. Since $f(2) + f(2) - 1 \neq 1$, $g(2) \neq 1$, and so $g(2) = 3$. Since $f(3) + f(2) - 1 \neq f(2)$, $g(3) \neq 2$, and so $g(3) = 4$. Claim: For all $a \geq 2$, $g(a) = a + 1$. Proof: Proceed by induction. The claim is true for $a = 2, 3$. Suppose the claim is true for all $a \leq k - 1$, where $k \geq 4$. Then since $g(k) \neq g(k - 2) = k - 1$ and $g(k) \in \{k - 1, k + 1\}$, $g(k) = k + 1$, completing our induction. Note that for all $a \geq 2$, $f(a) + f(2) - 1 \geq 2 + 2 - 1 = 3$. Hence, for all $a \geq 2$, $a + 1 = g(a) \neq f(2)$. Since $f$ is injective, $f(2) = 2$. Simple induction gives $f(x) = x$ for all $x \in \mathbb{Z}_{>0}$.

We plug $a = 1$. This gives that $f(b) = f(b+f(1) - 1)$. FTSOC assume that $f(1) \neq 1$. This means that $f(b) = f(b+c)$ for some positive constant $c$. This means that in our original equation we can increase $a$ to an arbitrarily large number and still have the same values for the other two sides. Contradiction. We can plug in $b = 1$ to see that $f(f(a)) = a$. This means that $f$ is both surjective and injective. We prove by strong induction that $f(x) = x$. Our base case is trivial. Now we try to prove that $f(k) = k$ and we know that $f(x) = x$ for all $x <k$ We look at $P(2, k)$ where and see that $f(k + f(2) - 1) \in {f(k) - 1, f(k), f(k) + 1}$. If $f(k + f(2) - 1) = f(k) - 1$ then we can keep adding $f(2) - 1$ inside the function and make it negative which is impossible. If we have $f(k+f(2) - 1) = f(k)$ then by injectivity we have $f(2) = 1$ which is impossible because $f(1) = 1$. So, we must have $f(k+f(2) - 1) = f(k) + 1$. We can see that $f(k+x(f(2) - 1))$ takes on all values of $f$ such that $f(x) \geq f(k) + 1$ by injectivity. Thus we must have $f(k) = k$ $\blacksquare$

Very cool problem! Let $P(a,b)$ denote the assertion. Initially, we prove $f$ is unbounded. If $f$ was bounded, then take a sufficiently large $a$, and obviously the statement is not true. We claim $f(1)=1$. Consider $P(1,b)$, then obviously $f(b) = f(b + f(1)-1)$. If indeed $f(1)>1$, then the sequence would be periodic every $f(1)-1$ terms, implying that the image of $f$ is $f(1), f(2), \dots, f(f(1)-1)$. But this implies $f$ is bounded, contradiction. Then taking $P(a,1)$, we have $f(f(a))=a$, so $f$ is an involution and therefore bijective. We prove that $f((k-1)f(2) - (k-2)) = k$ for $k\geq 2$ through induction. The base case, $k=2$, is obvious. Now assume this is true for $k=2, 3, \dots, m$. Consider $P(2,(m-1)f(2) - (m-2))$. We have $2, m, f(m f(2) - (m-1))$ are the sides of a triangle. Since $f$ is bijective, in fact, we must have $f(mf(2)-(m-1))=m+1$. This proves the claim. But since $f((k-1)f(2) - (k-2))=k$, the set $S = \{(k-1)f(2) - (k-2) \mid k\geq 2, k \in \mathbb N \}$ must contain all the positive integers at least 2, which implies $f(2)=2$. It is easy to see this finishes.

Denote the assertion as $P(a, b)$. First, \[ P(1, b) \implies f(b) = f(b+f(1) - 1) \]Now, if $f(1) \neq 1$ then $f$ is periodic. If we make $a$ very large then we find that this case fails. Thus, $f(1) = 1$. Then, \[ P(a, 1) \implies f(f(a)) = a \]This means that $f$ is both injective and surjective. Plug \[ P(2, b) \implies f(b) - 1 \leq f(b + f(2) - 1) \leq f(b) + 1 \]Note that in particular since $f(b+f(2) - 1) \neq f(b)$ by injectivity, we have that either $f(b+f(2)-1) = f(b)+1$ or $f(b+f(2) - 1) = f(b) - 1$. Now, suppose that $f(b+f(2)-1) = f(b) - 1$ for some $b$. Denote $m = f(2) - 1$. Then $f(b+2m) = f(b+m) - 1 = f(b) - 2$. By induction, then \[ f(b+(k+1)m) = f(b+km) - 1 = f(b) - k - 1 \]for all positive integers $k$. But then we eventually get a nonnegative output, contradiction. So we must have $f(b+f(2) - 1) = f(b) + 1$. If $m = f(2) - 1$, then by induction, \[ f(b + (k+1)m) = f(b+km) + 1 = f(b) + k + 1 \]If $f(2) - 1 > 1$ then take some $c$ such that $c \not \equiv 1 \pmod{m}$. Since $f(c) \neq f(f(2)) = 2$, then there exists nonnegative integers $k$ and $j$ such that \[ f(c+km) = f(c) + k = 2+j = f(1+jm) \]Then this contradicts injectivity. Thus, $f(2) - 1 = 1$, and so we have $f(b+1) = f(b) + 1$. This implies that $f(n) = n$, which obviously works. $\blacksquare$

The only solution is $f(n)=n$ for all $n \in \mathbb{N}$. It's easy to check that this function satisfies the problem condition. Now, let $P(a,b)$ be the assertation of there is a triangle whose sides are $a,f(b)$, and $f(b+f(a)-1)$. This would later implies $$a+f(b)\ge f(b+f(a)-1)+1, a+f(b+f(a)-1)\ge f(b)+1,\text{and } f(b)+f(b+f(a)-1)\ge a+1.$$ Claim 1. $f(1)=1.$ Proof. Assume to the contrary, we have $f(1)=c\ge 2$. Observe that $P(a,1)$ gives $f(b)\ge f(b+c-1)$ for all $b \in \mathbb{N}$. This implies the chain of inequality: $$f(b)\ge f(b+c-1)\ge f(b+2c-2)\ge f(b+3c-3)\ge \cdots $$It means that for every $i\in \{1,2,3,...,c-1 \}$, there is $M_i\in \mathbb{N}$ such that the sequence $f(i+M_i(c-1)), f(i+(M_i+1)(c-1)), f(i+(M_i+2)(c-1)), \cdots$ is a constant sequence. We now let every terms of that sequence be $N_i$. Choose $r=\max(M_1,M_2,...,M_{c-1})+2$. Notice that the sequence $f(1+(c-1)r),f(2+(c-1)r),f(3+(c-1)r), \cdots$ is periodic in which the period is at most $c-1$. Now, choose $a=2max(N_1,N_2,...,N_{c-1})$. Notice $P(a,1+(c-1)r)$ implies $$f(1+(c-1)r)+f(1+(c-1)r+f(a)-1)\ge a+1.$$However, $f(1+(c-1)r)+f(1+(c-1)r+f(a)-1)\le a$ by the definition of $a$. This is a contradiction. $\blacksquare$ Now, we have $f(1)=1$. Notice that $P(a,1)$ tells us $$f(f(a))+1\ge a+1 \text{and } a+1\ge f(f(a))+1. $$This implies $f(f(a))=a$ for every $a\in \mathbb{N}$, which gives us the bijectivity of $f$. Let $k\ge 2$ be a natural number such that $f(k)=2$. We also have $k=f(2)$. Claim 2. $f(1+(k-1)l)=l+1$ for all $l\in \mathbb{N}_0$ Proof. We will use induction. For $l=0$ and $l=1$, it is clear. Assume that we now have $f(1+(k-1)d)=d+1$ for every $d=0,1,2,...,l$. For $d=l+1$, by the bijectivity of $f$, we have $f(1+(k-1)(l+1))\ge l+1$. However, from $P(f(a),k)$, we have $f(a)+1\ge f(a+k-1)$ for all $a \in \mathbb{N}$. Substituting $a=1+(k-1)l$, we get $l+2\ge f(1+(k-1)(l+1))$. This forces $f(1+(k-1)(l+1))=l+2$. This completes the induction. $\blacksquare$ We now have $f(1+(k-1)l)=l+1$ for all $l\in \mathbb{N}_0$. This implies $f(l)=1+(k-1)(l-1)$ for every $l \in \mathbb{N}$. Now, the bijectivity of $f$ forces $k=2$ (If not, then there is no $q\in \mathbb{N}$ such that $f(q)=2$). This brings us to $f(l)=l$ for every $l\in \mathbb{N}$. To sum up, the only function that satisfies the problem condition is $f(n)=n$ for every $n \in \mathbb{N}$. It is easy to check that this solution indeed satisfies the property given.

We claim that the only solution is $\boxed{f(x)=x}$. It is easy to see that it satisfies the condition in the problem statement; we now prove there are no other solutions. Before we begin, we note all inequalities below are obtained from the triangle inequality unless specified otherwise. Claim: $f(1)=1$. Proof: Let $a=1$, and we have $f(b)+1> f(b+f(1)-1)$ and $f(b+f(1)-1)+1> f(b)$. Together, these imply $f(b) = f(b+f(1)-1)$. For the sake of contradiction, assume $f(1)>1$. Then, there are arbitrarily large positive integers $d$ such that $f(d)=f(1)$. Let $a=d$ and fix $b$ to obtain $f(b)+f(b+f(d)-1) = f(b)+f(b+f(1)-1) > d$. Taking $d$ large enough, we have a contradiction, and hence $f(1)=1$. Claim: $f$ is an involution. Proof: Let $b=1$, and we have $a+1 > f(f(a))$ and $f(f(a))+1 > a$, which together imply $f(f(a))=a$, as desired. Claim: $f(2)=2$. Proof: Assume for the sake of contradiction that $f(2)=r>2$, and hence $f(r)=2$. We prove by strong induction that for any nonnegative integer $k$, we have $f(r+k(r-1))=k+2$. The base case, $k=0$, is trivial, so we proceed to the inductive step. Assume that this claim holds for $0,1,\dots,k$; we show it holds for $k+1$. Let $a=2$ and $b=r+k(r-1)$; then, we have $a+f(b) = k+4 > f(r+(k+1)(r-1))$. Combining this with the facts $f(1)=1$, $f(r+k(r-1)) = k+2$ for $k=0,1,\dots, k$, and $f$ is injective, we must have $f(r+(k+1)(r-1))=k+3$, which completes the inductive step. But this implies that $f(r+(r-2)(r-1)) = r$, so in order not to violate the injectivity of $f$, we must have $r+(r-2)(r-1)=r$. However, this implies $r\in \{1,2\}$, which is a contradiction. Hence, $f(2)=2$. Claim: $f$ is the identity function. Proof: we will show that $f(x)=x$ using strong induction. We already know that $f(1)=1$ and $f(2)=2$; these are our base cases. For the inductive step, we assume $f(x)=x$ for all positive integers less than or equal to $x$, and prove $f(x+1)=x+1$. Note that to preserve the injectivity of $f$, we must have $f(x+1)>x$. Then, let $a=2$, $b=x$, and we must have $x+2 > f(x+1)$. This implies $f(x+1)=x+1$, which completes the inductive step. We are now done. $\blacksquare$

Guys I really don’t know latex

The only solution is $f(x)=x$, which is easy to check. Taking $P(1,a)$ gives us $f(a) = f(a+f(1)-1)$. If $f(1) \neq 1$, it follows that $f(x)$ is periodic with period $f(1)-1$; then, in our original equation, we can repeatedly increase $a$ by $f(1)-1$ to get a contradiction. So, $f(1) = 1$. Taking $P(a,1)$ gives us $a = f(f(a))$, so in particular, $f$ is injective. Claim: We have $f(x) \geq x$.

Combining the above claim with $f(f(x))$ gives us $f(x)=x$, as desired.

Solved with reni_wee. A bit long winded, but this was the solution that we found. Really fun and different kind of problem. The answer is $f(n) = n$ for all $n\in \mathbb{Z}_{>0}$. It’s easy to see that these functions satisfy the given equation. We now show these are the only solutions. Let $P(a,b)$ be the assertion that $a$ , $f(b)$ and $f(b+f(a)-1)$ are the sides of a non-degenerate triangle. We start off by proving the following characteristic of $f$. Claim : The function $f$ is an involution, i.e $f(f(a))=a$ for all positive integers $a$. Proof : Note that from $(1,b)$ we have, \[f(b)-1 < f(b+f(1)-1)< f(b)+1\]which implies $f(b+f(1)-1)=f(b)$ for all positive integers $b$. Now, if $f(1)>1$ this implies that $f$ is periodic with period $T = |f(1)-1|$. Then, since $f$ is a periodic function over the positive integers it must be bounded both above and below. Say $f(m)=M$ is the maximum of this function. Then, $P(2M,m)$ implies, \[2M < f(m)+f(m+f(M)-1)\le 2M\]which is a clear contradiction. Thus, $f$ cannot be periodic and hence $f(1)=1$. Then, $P(a,1)$ implies, \[a-1=a -f(1) < f(f(a))<a+f(1)a+1\]and thus, $f(f(a))=a$ for all positive integers $a$ as desired. Note that now in fact $f$ is both injective and surjective. Next we look at $P(2,f(b))$. This tells us that \[2 , f(f(b)) \text{ and } f(f(b)+f(2)-1)\]are the sides of a non-degenerate triangle. Thus, $2 , f(b)$ and $f(f(b)+f(2)-1)$ are sides of a non-degenerate triangle. This implies, \[b-2 < f(f(b)+f(2)-1)<b+2\]We now have 3 cases to explore. Case 1 : $f(f(b)+f(2)-1) = b$. Thus, \[f(f(b)+f(2)-1)=b = f(f(b))\]which since $f$ is injective implies $f(b)+f(2)-1=f(b)$ or $f(2)=1$ which is a clear contradiction. Case 2 : $f(f(b)+f(2)-1)=b-1$. Thus, \[f(f(b)+f(2)-1)=b-1=f(f(b-1))\]which since $f$ is injective implies $f(b)+f(2)-1=f(b-1)$ But for $f=2$ this rewrites to $2f(2)-1=f(1)=1$ which implies $f(2)=1$ which is again a clear contradiction. Case 3 : $f(f(b)+f(2)-1)=b+1$. Thus, \[f(f(b)+f(2)-1)=b-1=f(f(b+1))\]which since $f$ is injective implies $f(b)+f(2)-1 = f(b+1)$. Thus, \[f(b+1)=f(b)+f(2)-1 \ge f(b)+1>f(b)\]implies that $f$ is strictly increasing. Combining this with our previous observation that $f$ is injective and surjective, it follows that $f$ is indeed the identity function, as claimed.

This solution is very clear and motivated, making the problem nice but not particularly difficult. From letting $a = 1$, we have $f(b) = f(b+f(1) - 1)$ for all $b \in \mathbb N$. If $f(1) - 1 > 0$, then $f$ is eventually periodic, thus taking sufficiently large $a$ in the original assertion yields a contradiction. Thus $f(1) = 1$. Setting $b = 1$, it follows that $f(f(a)) = a$, hence $f$ is bijective. Claim: [Key Claim] For all $n \in \mathbb N$, $f(n+1) = f(n) + f(2) - 1$. Proof: We induct on $n$, with the $n=1$ case clear. First, observe that \[n-1 \leq f(f(n) + f(2) - 1) \leq n+1\]by the condition. First Case: If $f(f(n) + f(2) - 1) = n-1$, applying $f$ to both sides yields \[f(n) = f(n-1) - (f(2) - 1).\]But the inductive hypothesis forces $f(2) = 1$, which contradicts $f$ bijective. Second Case: If $f(f(n) + f(2) - 1) = n$, applying $f$ to both sides yields $f(n) = f(n) - (f(2) - 1)$, hence once again $f(2) = 1$, contradiction. Third Case: If $f(f(n) + f(2) - 1) = n+1$, applying $f$ to both sides yields $f(n) + f(2) - 1 = f(n+1)$, which is the desired conclusion. $\blacksquare$ So $f$ is bijective and linear, implying $f \equiv n$, which works.

Answer is $f(n)=n$ for each positive integer. Claim: $f(1)=1$. Proof:$a=1$ implies $f(b)=f(b+f(1)-1)$. If $f(1)\neq 1$, then $f$ is periodic. Denote by $T$ the period. \[f(b)+f(b+f(a)-1)=f(b)+f(b+f(a+nT)-1)\geq a+nT\]Which is impossible for sufficiently large $n$.$\square$ $b=1$ gives $f(f(a))=a$ hence $f$ is an involution. This yields $f$ is bijective. Claim: $f(2)-1\geq |f(a+1)-f(a)|$. Proof: $a,b\rightarrow f(a),2$ implies $f(2)+f(a+1)\geq f(a)+1\iff f(2)-1\geq f(a)-f(a+1)$. Similarily $f(a)+f(2)\geq f(a+1)+1\iff f(2)-1\geq f(a+1)-f(a)$ which gives the conclusion.$\square$ Claim: $f(2)=2$. Proof: Let $f(c)=2\iff f(2)=c$ by injectivity. Note that $c\neq 1$. $f(a),c,f(a+1)$ are sides hence $a=c-1$ yields $c+1\geq f(c-1)\geq c-1$. Now we split into $3$ cases. Suppose that $f(c-1)=c$. Then, $c=3$ by injectivity and $f(a),2,f(a+2)$ are sides which implies $f(a+2)\leq f(a)+1$. Since $f(1)=1,f(3)=2$, induction with utilising injectivity gives $f(2k-1)=k$. However, $4k-3=f(f(4k-3))=f(2k-1)=k$ does not hold for $k>1$ which results in a contradiction. Assume that $f(c-1)=c+1\iff f(c+1)=c-1$. We observe that $f(a),f(c+1),f(a+c)$ are sides of a triangle thus, $f(a+c)-f(a)\leq c-2$. Let $m_i$ be the maximum among $\{f((i-1)c+1),\dots,f(ic)\}$. $m_i$ increases at most $c-2$ hence \[\max\{f(1),\dots,f(nc)\}\leq m_1+(n-1)(c-1)=m_1+cn-n-c+1\]Since $f$ is injective, $\max\{f(1),\dots,f(nc)\}\geq nc$ which implies $m_1+cn-c-n+1\geq cn$ or $m_1-c\geq n$ which is impossible for sufficiently large $n$. So we get $f(c-1)=c-1$. Pick $a=c,b=c-1$ which yields $f(c),f(c-1),f(2c-2)$ are sides or $2,c-1,f(2c-2)$ are sides. Thus, $f(2c-2)\leq c$. Choose $b=2c-2$ to get $f(a),f(2c-2),f(a+2c-3)$ are sides. So we conclude that \[f(a+2c-3)\leq f(a)+f(2c-2)-1\leq f(a)+c-1\implies f(a+2c-3)-f(a)\leq c-1\]Let $m_i$ be the maximum among $\{f((i-1)(2c-3)+1),\dots,f(i(2c-3))\}$. $m_i$ increases at most $c-1$ thus, \[\max\{f(1),\dots,f(n(2c-3))\}\leq m_1+(c-1)(n-1)=m_1+cn-c-n+1\]Since $f$ is injective, $\max\{f(1),\dots,f(n(2c-3))\}\geq n(2c-3)$ so $2cn-3n\leq m_1+cn-c-n+1$ which is equavilent to $(c-2)n\leq m_1-c+1$. Since $c\neq 1$ and $c$ cannot be larger than $2$, $c=2$.$\square$ We have $|f(a+1)-f(a)|\leq 1$ and $f$ is injective hence $f(n)=n$ for all positive integers as desired.$\blacksquare$

$ $