IMO 2009, Problem 5

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

orl

3647 posts

orl

#1 h Jul 16, 2009, 11:39 AM • 7 Y

Y by Davi-8191, Ankoganit, megarnie, HWenslawski, microsoft_office_word, Adventure10, Sedro

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) \text{ and } f(b + f(a) - 1).$
(A triangle is non-degenerate if its vertices are not collinear.)

Proposed by Bruno Le Floch, France

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Soarer

2589 posts

Soarer

#2 h Jul 16, 2009, 12:33 PM • 19 Y

Y by threehandsnal, frill, Sx763_, Wizard_32, igli.2001, MathbugAOPS, sabrinamath, megarnie, myh2910, microsoft_office_word, channing421, Aopamy, Adventure10, Mango247, Sedro, and 4 other users

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Bugi

1857 posts

Bugi

#3 h Jul 16, 2009, 1:23 PM • 4 Y

Y by Adventure10, Mango247, Mango247, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cocoowner

28 posts

cocoowner

#4 h Jul 16, 2009, 1:43 PM • 2 Y

Y by Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Erken

1363 posts

Erken

#5 h Jul 16, 2009, 2:23 PM • 1 Y

Y by Adventure10

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Agr_94_Math

881 posts

Agr_94_Math

#6 h Jul 16, 2009, 4:25 PM • 2 Y

Y by Adventure10, Mango247

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?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bertram

383 posts

bertram

#7 h Jul 16, 2009, 6:25 PM • 2 Y

Y by Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

apratimgtr

81 posts

apratimgtr

#8 h Jul 16, 2009, 6:48 PM • 1 Y

Y by Adventure10

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Bugi

1857 posts

Bugi

#9 h Jul 16, 2009, 8:17 PM • 1 Y

Y by Adventure10

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Oiler

1 post

Oiler

#10 h Jul 17, 2009, 6:32 AM • 2 Y

Y by Stuffybear, Adventure10

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

nik

23 posts

nik

#11 h Jul 17, 2009, 12:05 PM • 2 Y

Y by Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

hedgehuogis

49 posts

hedgehuogis

#12 h Jul 18, 2009, 1:00 AM • 3 Y

Y by Adventure10, Mango247, and 1 other user

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

freemind

337 posts

freemind

#13 h Jul 18, 2009, 5:04 AM • 2 Y

Y by Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

FightTheTide

140 posts

FightTheTide

#14 h Jul 18, 2009, 6:02 AM • 2 Y

Y by Adventure10, Mango247

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

This post has been edited 1 time. Last edited by FightTheTide, Jul 18, 2009, 8:08 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

CatalystOfNostalgia

1479 posts

CatalystOfNostalgia

#15 h Jul 18, 2009, 6:50 AM • 1 Y

Y by Adventure10

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Spectator

657 posts

Spectator

#79 h Jun 3, 2023, 5:33 AM • 1 Y

Y by gracemoon124

huashiliao2020 wrote:

Spectator wrote:

Click to reveal hidden text

Legend says he still hasn't found time to rigorously do this

the real rigorous solve was the friends we made along the way

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

DongerLi

22 posts

DongerLi

#80 h Jul 5, 2023, 5:08 PM

Y by

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}$ .

This post has been edited 1 time. Last edited by DongerLi, Jul 5, 2023, 5:09 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Math4Life7

1703 posts

Math4Life7

#81 h Nov 1, 2023, 7:08 PM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bobthegod78

2982 posts

bobthegod78

#82 h Nov 17, 2023, 11:19 PM

Y by

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.

This post has been edited 1 time. Last edited by bobthegod78, Nov 17, 2023, 11:19 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

abeot

123 posts

abeot

#83 h Nov 26, 2023, 11:56 PM • 2 Y

Y by megarnie, centslordm

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

amazingtheorem

17 posts

amazingtheorem

#84 h Jan 23, 2024, 6:44 PM

Y by

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.

This post has been edited 1 time. Last edited by amazingtheorem, Jan 23, 2024, 6:47 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Sedro

5811 posts

Sedro

#85 h Jun 17, 2024, 12:10 AM

Y by

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$

This post has been edited 1 time. Last edited by Sedro, Jun 17, 2024, 2:56 PM
Reason: Cleaned up proof

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Bryan0224

53 posts

Bryan0224

#86 h Jul 13, 2024, 10:46 AM

Y by

Guys I really don’t know latex

Attachments:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ihatemath123

3430 posts

ihatemath123

#87 h Aug 11, 2024, 3:23 PM

Y by

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$ .
Proof: If $f(a+1) \leq a$ , then taking $P(f(a+1),b)$ for any integer $b$ gives us $f(a+b) \leq a-1+f(b),$ contradicting injectivity.

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

This post has been edited 2 times. Last edited by ihatemath123, Aug 11, 2024, 3:25 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cursed_tangent1434

548 posts

cursed_tangent1434

#88 h Sep 22, 2024, 3:45 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

HamstPan38825

8853 posts

HamstPan38825

#89 h Nov 5, 2024, 4:26 PM

Y by

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.

This post has been edited 2 times. Last edited by HamstPan38825, Nov 5, 2024, 4:28 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bin_sherlo

662 posts

bin_sherlo

#90 h Dec 2, 2024, 6:07 PM • 1 Y

Y by tiny_brain123

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Mathandski

711 posts

Mathandski

#91 h Dec 4, 2024, 10:05 PM

Y by

Subjective Rating (MOHs) $\text{[math]}$

Attachments:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Ilikeminecraft

298 posts

Ilikeminecraft

#92 h Monday at 11:33 PM

Y by

The answer is $f\equiv x.$
Pick $a = 1$ first, and we have $f(b) = f(b + f(1) - 1).$ If $f(1)\neq1,$ then $f$ has period $f(1) - 1 > 1.$ However, if we fix $b,$ and pick an arbitrarily large $a \equiv1\pmod{f(1)-1}$ such that $a > f(b) + f(b + f(1) - 1),$ then this is a contradiction. Thus, $f(1) = 1.$

Take $b = 1$ and we get that $f$ is an involution.
Hence, $f$ is injective and surjective.

Plug in $b = f(b)$ and we get the new equation $a, b, f(f(a) + f(b) - 1)$ forms a triangle.

We now prove $f\equiv x$ using strong induction.
Assume $f(s) = 2.$ Take $2, 2$ and we get $4 > f(3).$ Hence, either $f(3) = 2$ or $f(3) = 3.$
In the first case, we have $f(3) = 2, f(2) = 3.$ Take $2, 2$ and so $4 > f(5),$ contradiction.
To finish, easy induction suffices. Assume $f(k) = k$ for all $k < n.$
Take $n-1, 2$ and we get $f(n) < n + 1,$ so $f\equiv n.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

asdf334

7585 posts

asdf334

#93 h Yesterday at 6:50 PM

Y by

hey that was kind of fun lol

Okay so we need to brainstorm. The first piece of information we can get comes from plugging in $a=1$ ; we get $f(b)=f(b+f(1)-1)$ . In that case if $f(1)\ne 1$ then we ultimately find that $f$ is periodic and thus bounded, a contradiction to the original triplet given as we can set $a$ to be large.

Thus $f(1)=1$ , hence we obtain from $b=1$ that $a=f(f(a))$ . Now write $a\to f(a)$ to get the nicer triplet $f(a)$ , $f(b)$ , and $f(a+b-1)$ .

Turns out we are almost done. Suppose that $f(2)=S$ and $f(S)=2$ . What information can we get from this? Well, we can set $a+b-1=S$ , but this restricts our options and doesn't work as well.

Instead write $a=S$ to obtain that $(2,f(b),f(b+S-1))$ form the side lengths of a triangle. Note that $f$ is injective and surjective; if $S>2$ then we must have $|f(b)-f(b+S-1)|=1$ . But now consider the set $\{b+0(S-1),b+1(S-1),b+2(S-1),\dots\}$ . When adjacent values in the set are plugged into $f$ , they yield consecutive outputs. Furthermore, all outputs are distinct. As a result, the outputs are simply $\{f(b)+0,f(b)+1,f(b)+2,\dots\}$ .

But if $S>2$ then there are still an infinite number of inputs outside this set, and only a finite number of outputs left (less than $f(b)$ ). That is a contradiction, so $S=f(2)=2$ .

Hence $f(n)\le n$ for $n\in \{1,2\}$ . Now we can induct: if $f(n)\le n$ and $n\ge 2$ , write
$n+2\ge f(n)+f(2)>f(n+1)$ thus proving that $f(n+1)\le n+1$ and so $f(n)\le n$ always. As $f$ is injective we get $f(n)=n$ always, done. $\blacksquare$

Z K Y