Find all functions $ f: \mathbb{N} \to \mathbb{N} $ such that $$ f\left(x+yf\left(x\right)\right) = x+f\left(y\right)f\left(x\right) $$holds for all $ x,y \in \mathbb{N} $
Problem
Source: 2018 Taiwan TST Round 3, Day 5, Problem 2
Tags: algebra, functional equation, function, Taiwan
28.04.2018 20:15
$x=y=0$: $f(0)=$${f}^{2}(0)$ $=>$ $f(0)=0$ or $f(0)=1$ Case 1: $f(0)=0$ - $y=0$: $f(x)=x$, $ x\in \mathbb{N} $ Case 2: $f(0)=1$ - $y=0$: $f(x)=x+f(x)$, $ x\in \mathbb{N} $ nonsense. So: $f(x)=x$, $ x\in \mathbb{N} $
28.04.2018 20:16
robinjacobs wrote: $x=y=0$: $f(0)=$${f}^{2}(0)$ $=>$ $f(0)=0$ or $f(0)=1$ Case 1: $f(0)=0$ - $y=0$: $f(x)=x$, $ x\in \mathbb{N} $ Case 2: $f(0)=1$ - $y=0$: $f(x)=x+f(x)$, $ x\in \mathbb{N} $ nonsense. So: $f(x)=x$, $ x\in \mathbb{N} $ $\mathbb{N}$ does not contain 0.
28.04.2018 20:35
$P(xf(y)+y,f(y)): f(f(x)f(y)^2+(x+y)f(y)+y)=f(x)f(y)f(f(y))+yf(f(y))+xf(y)+y$ $P(y,f(x)f(y)+x+y):f(f(x)f(y)^2+(x+y)f(y)+y)=f(y)f(f(x)f(y)+x+y)+y$ Therefore $f(f(x)f(y)+x+y)=f(x)f(f(y))+x+\frac{yf(f(y))}{f(y)}......(1)$ and so $f(y)|yf(f(y))\quad\forall y\in\mathbb{N}......(2)$ Claim. $f(1)=f(f(1))$. Proof of the claim Assume for the sake of contradiction that $f(f(1))\neq f(1)$. Then $f(1)>1$ and $f(f(1))=kf(1)$ by (2). Taking $y=f(x)+x$ in (2) and simplifying the identity with $P(x,1),P(x,f(1)$, we get that $f(x)f(1)+x|(1-k)(f(1)-1)x^2$. Set $x=p$ where $p$ is a prime greater than $|(1-k)(f(1)-1)$. Then $f(1)f(p)+p=cp,cp^2$ where $c|(1-k)(f(1)-1)$. Now, let $\mathbb{P}_n:=\{p\in \mathbb{P}|p>|(1-k)(f(1)-1)|, p>f(1)^n, p\equiv 1+\cdots+f(1)^{n-1}\mod f(1)^n\},$ $A_n := \{c|\frac{(1-k)(f(1)-1)}{c}\in\mathbb{Z}\textup{ and }\exists p\in\mathbb{P}_n \textup{ s.t. } f(1)f(p)+p=cp\}$ and $B_n := \{c|\frac{(1-k)(f(1)-1)}{c}\in\mathbb{Z}\textup{ and }\exists p\in\mathbb{P}_n \textup{ s.t. } f(1)f(p)+p=cp^2\}$. By Dirichlet's thm., $|\mathbb{P}_n|=\infty\quad\forall n$, and so $|A_n|+|B_n|\neq 0$. Since $\mathbb{P}_1\supseteq \mathbb{P}_2\supseteq\cdots$, we know that $A_1\supseteq A_2\supseteq \cdots$ and $B_1\supseteq B_2\supseteq\cdots$. Note that $(1-k)(f(1)-1)\neq 0$, so $|A_1|,|B_1|<\infty$ and hence $\bigcap_{n\in\mathbb{N}}A_n, \bigcap_{n\in\mathbb{N}} B_n$ are not both empty. Case 1. $\exists c\in\bigcap_{n\in\mathbb{N}}A_n$. For any $n\in\mathbb{N}$, let $p\in\mathbb{P}_n$ such that $f(1)f(p)+p=cp$. Then $f(p)=\frac{c-1}{f(1)}p$, and so $m:=\frac{c-1}{f(1)}\in\mathbb{N}$. Suppose that $p=yf(1)^n+f(1)^{n-1}+\cdots+1$ where $y\in\mathbb{N}$, then $P(1,yf(1)^{n-1}+\cdots+1),P(1,yf(1)^{n-2}+\cdots+1),\ldots,P(1,y)$ together show that $mp=f(p)=f(yf(1)^n+\cdots+1)=f(1)^nf(y)+f(1)^{n-1}+\cdots+1$, and so $f(1)^n|(mp-(f(1)^{n-1}+\cdots+1))(f(1)-1).$ Since $(f(1)-1)p\equiv -1\mod f(1)^n$, we have $f(1)^n|1-m$. Since $n$ can be arbitrarily large and $f(1)>1$, we have that $m=1$, and so there exists infinitely many $p$ such that $f(p)=p$. Put $(x,p),(p,x)$ in (1), and we can get that $pf(x)+x+p=pf(f(x))+\frac{xf(f(x))}{f(x)}+p$. Since this holds for infinitely many $p$, we have that $f(x)=f(f(x))$ and in particular $f(1)=f(f(1))$, which is a contradiction. Case 2. $\exists c\in\bigcap_{n\in\mathbb{N}}B_n$. For any $n\in\mathbb{N}$, let $p\in\mathbb{P}_n$ such that $f(1)f(p)+p=cp^2$, then $f(p)=\frac{cp-1}{f(1)}p,\Rightarrow m:=\frac{cp-1}{f(1)}\in\mathbb{N}$. By the same argument in Case 1., we have that $f(1)^n|1-m$, and so $f(1)^n|cp-1-f(1)$. Multiplying the right hand side by $(f(1)-1)$, we get that $f(1)^n|1-f(1)^2-c$, and so $c=1-f(1)^2<0$, which is again a contradiction. Since we reach a contradiction in either case, the assumption that $f(1)\neq f(f(1))$ must be false. Hence $f(1)=f(f(1))$. Now $P(x,f(1))$ gives that $f(f(x)f(1)+x)=f(x)f(1)+x$, and so there are infinitely many fixed points. For every fixed point $s$, by plugging in $(x,s),(s,x)$ in (1) we get that $sf(x)+x+s=sf(f(x))+\frac{xf(f(x))}{f(x)}+s$. Since this holds for infinitely many $s$, we have that $f(x)=f(f(x))$ for any $x\in\mathbb{N}$. $(x,f(x))$ in (1) implies that $f(x)^2+f(x)+x$ is a fixed point. $P(x,f(x)+1): f(x)f(f(x)+1)+x=f(x)^2+f(x)+x$, and so $f(f(x)+1)=f(x)+1$. Therefore, by induction, $f(f(x)+n)=f(x)+n$ for any $n\in\mathbb{N}$. This shows that $f(x)=x$ for large $x$. Lastly, for any $y\in\mathbb{N}$, let $x$ be large in $P(x,y)$. Then $f(x)y+x=f(x)f(y)+x$, and so $f(y)=y$.
29.04.2018 13:21
In our country, the positive integer is denoted by $ {\mathbb{N}}^{*} $. I don't know. I'm sorry
06.06.2018 18:20
Can you post all problems of 2018 Taiwan TST? Thanks.
15.06.2018 08:13
Rickyminer wrote: Can you post all problems of 2018 Taiwan TST? Thanks. Sadly, some of the TST are chosen from 2017 ISL, which shall not be revealed before 2018 IMO ends. Conventionally Taiwan TST will be uploaded about a year afterward if some people are willing to go over this boring translate, type and upload process, and it will definitely not be uploaded before the coming IMO.
14.02.2019 23:01
Let $c=f(1)$. Plug-in $x=y=1$ and get $f(1+c)=1+c^2$. Note that by letting $x=1$ we have that $f(1+cy)=1+cf(x)$, thus $f(M)\equiv 1 \pmod{c}$ for any $M\equiv 1 \pmod{c}$. Let $x$ be an arbitrary positive integer and $k$ be such that $k+x-1$ is divisible by $c$. Let $a=1+c$ and $b=f(1+c)=1+c^2 \implies f(a+bx)=a+bf(x)$ for any positive integer $x$. By repeatedly letting $x\mapsto a+bx$, an easy induction gives us that $$f\left(a\frac{b^k-1}{b-1}+b^kx\right)=a\frac{b^k-1}{b-1}+b^kf(x) \ \ \ (1)$$But note that $a\frac{b^k-1}{b-1}+b^kx=(1+c)\frac{(1+c^2)^k-1}{c^2}+(1+c^2)^kx \equiv k+x\equiv 1 \pmod{c}$, this means that RHS in $(1)$ is congruent to $1 \pmod{c}$, thus $c\mid b^k(f(x)-x) \implies c\mid f(x)-x$ for any positive integer $x$, thus $c=1$ and it easily follows that $f(x)=x$.
15.02.2019 20:28
f(X)=X is the only solution.
16.02.2019 09:32
andersarnold123 wrote: f(X)=X is the only solution. That's unexpected. Do you have something to backup this extravagant claim?
23.02.2019 21:57
Let $f(1)=a$. 1.$P(1,1) \implies f(1+a) = 1+a^2$ 2.$P(1+a,1+a) \implies f(a^3+a^2+2a+2) = a^4+2a^2+a+2$ 3.$P(1,1+a) \implies f(a^2+a+1) = a^3+a+1$ 4.$P(a^2+a+1,1) \implies f(a^3+a^2+2a+2) = a^4+2a^2+2a+1$ $$a^4+2a^2+a+2=f(a^3+a^2+2a+2)=a^4+2a^2+2a+1 \implies a = 1$$5.$P(1,y) \implies f(x) = x, \forall x \in \mathbb{N}$
09.04.2020 00:32
rmtf1111 wrote: Let $c=f(1)$. Plug-in $x=y=1$ and get $f(1+c)=1+c^2$. Note that by letting $x=1$ we have that $f(1+cy)=1+cf(x)$, thus $f(M)\equiv 1 \pmod{c}$ for any $M\equiv 1 \pmod{c}$. Let $x$ be an arbitrary positive integer and $k$ be such that $k+x-1$ is divisible by $c$. Let $a=1+c$ and $b=f(1+c)=1+c^2 \implies f(a+bx)=a+bf(x)$ for any positive integer $x$. By repeatedly letting $x\mapsto a+bx$, an easy induction gives us that $$f\left(a\frac{b^k-1}{b-1}+b^kx\right)=a\frac{b^k-1}{b-1}+b^kf(x) \ \ \ (1)$$But note that $a\frac{b^k-1}{b-1}+b^kx=(1+c)\frac{(1+c^2)^k-1}{c^2}+(1+c^2)^kx \equiv k+x\equiv 1 \pmod{c}$, this means that RHS in $(1)$ is congruent to $1 \pmod{c}$, thus $c\mid b^k(f(x)-x) \implies c\mid f(x)-x$ for any positive integer $x$, thus $c=1$ and it easily follows that $f(x)=x$. Can you explain why $c\mid f(x)-x$ implies $c=1$ ? Because if $f(x)\equiv x\pmod{2}$ and $c=2$ then this is still satysfied.
12.04.2020 18:38
FISHMJ25 wrote: rmtf1111 wrote: Let $c=f(1)$. Plug-in $x=y=1$ and get $f(1+c)=1+c^2$. Note that by letting $x=1$ we have that $f(1+cy)=1+cf(x)$, thus $f(M)\equiv 1 \pmod{c}$ for any $M\equiv 1 \pmod{c}$. Let $x$ be an arbitrary positive integer and $k$ be such that $k+x-1$ is divisible by $c$. Let $a=1+c$ and $b=f(1+c)=1+c^2 \implies f(a+bx)=a+bf(x)$ for any positive integer $x$. By repeatedly letting $x\mapsto a+bx$, an easy induction gives us that $$f\left(a\frac{b^k-1}{b-1}+b^kx\right)=a\frac{b^k-1}{b-1}+b^kf(x) \ \ \ (1)$$But note that $a\frac{b^k-1}{b-1}+b^kx=(1+c)\frac{(1+c^2)^k-1}{c^2}+(1+c^2)^kx \equiv k+x\equiv 1 \pmod{c}$, this means that RHS in $(1)$ is congruent to $1 \pmod{c}$, thus $c\mid b^k(f(x)-x) \implies c\mid f(x)-x$ for any positive integer $x$, thus $c=1$ and it easily follows that $f(x)=x$. Can you explain why $c\mid f(x)-x$ implies $c=1$ ? Because if $f(x)\equiv x\pmod{2}$ and $c=2$ then this is still satysfied. Plug in $c=f(1)$ and $x=1$: $f(1)|f(1)-1, \Rightarrow f(1)|1,\Rightarrow f(1)=1$.
02.08.2020 02:03
Solution with meql, brian6liu, JNEW, tapir1729, kcong Denote the assertion as $P(x,y)$. Consider $P(x,yf(x+f(x))+1)$ and $P(x+f(x),yf(x))$. It is easy to verify that the LHS of both expressions are the same. So, we get $$x+f(x)f(yf(x+f(x))+1)=x+f(x)+f(x+f(x))f(yf(x))\implies f(x)|f(x+f(x))f(yf(x))$$$P(x,1)$ yields $f(x+f(x))=x+f(1)f(x)$, which means this simplifies to $f(x)|(x+f(1)f(x))f(yf(x))\implies f(x)|xf(yf(x))\,\,(*)$. Now, we claim $f(1)=1$. If $f(1)=a\neq 1$, consider the sequence $x_0=1$, and $x_i=x_{i-1}+f(x_{i-1})$. By considering $P(x_{i-1},1)$, we get $f(x_i)=x_{i-1}+af(x_{i-1})$. So, $f(x_i)\equiv x_{i-1}\pmod a$, and $x_i\equiv x_{i-1}+x_{i-2}\pmod a$. The residues mod $a$ form the Fibonacci sequence, which eventually has a divisor mod $a$, so consider the first $i$ such that $a|x_i$. Obviously, $i>1$. In this case, $a\nmid f(x_i)$, as $f(x_i)\equiv x_{i-1}\not\equiv 0\pmod a$. However, $(*)$ applied at $(x,y)=(1,x_i/a)$ gives $a|f(x_i)$, which is a contradiction! Hence, $f(1)=1$, and $P(1,y)$ gives $f(1+y)=1+f(y)$. So, we can induct upwards from $1$ to get $f(x)=x$ for all $x$.
23.08.2020 14:12
Denote $f(1)$ by $c$, and assume $c\neq 1$. Taking $P(1,1)$, $P(1,c+1)$, $P(1,c^2+c+1)$ and so on we get $f(\frac{c^k-1}{c-1})=\frac{c^{k-1}-1}{c-1}+c^{k+1}$ Denote by $a_k=\frac{c^k-1}{c-1}$. Notice the following: if $n>x$ and $n\equiv x\text{ mod }f(x) $, then $f(n)\equiv x\text{ mod }f(x) $. This follows easily by rewriting $n=yf(x)+x$. Now, notice that $a_k$ is basically an exponential function, so for any integer $a$ there is some integer $b$ such that $a_{k+b}\equiv a_{k} \text{ mod b }$. Now, fix an integer $x$ and take some $t$ such that $a_{x+t} \equiv a_x \text{ mod } f(a_x) \implies f(a_{x+t}) \equiv a_x \text{ mod }f(a_x) \implies f(a_{x})\equiv a_x \text{ mod }f(a_x) \implies f(a_x)|a_x$.. The one before last implication follows from the fact that $f(a_{x+t})$ is also exponential of $c$. It is easy to see that $c\neq 1 \implies f(a_x)>a_x$ and so gives a contradiction. On the other hand, if $c=1$ we have $f(y+1)=f(y)+1$ and the rest is trivial $\blacksquare$
04.02.2021 11:45
Let $x_1=1$ and define $x_n=x_{n-1}+f(x_{n-1})$ for $n>1$. Now, observe that $f(x_n)\equiv f(x_{n-1}+f(x_{n-1}))\equiv x_{n-1}\pmod{f(1)}$. Thus, $x_{n+1}\equiv x_n+x_{n-1}\pmod{f(1)}$. Thus, $x_i$ is the fibonacci sequence $\pmod{f(1)}$. But, the fibonacci sequence is periodic modulo any number! Thus, there is an $a>2$ such that $x_a\equiv 1\pmod{f(1)}$ and $x_{a-1}\equiv 0\pmod{f(1)}$. Thus, $f(x_a)\equiv 0\pmod{f(1)}$. But, $x_a\equiv 1\pmod{f(1)}$ and $x_a=x_{a-1}+f(x_{a-1})>1$ so $0\equiv f(x_a)=f(1+f(1)(\frac{x_a-1}{f(1)}))\equiv 1\pmod{f(1)}$. Thus, $f(1)=1$! Now, $P(1,y)\implies f(y+1)=f(y)+1$ and by induction we get that $f(n)=n$ and we are done. I really liked this problem and this idea, even though looking at the thread, much simpler solutions exist.
21.05.2021 11:16
Wow, this is a realllly nice problem! Let $f(1) = c$ and let $P(x,y)$ denote the given assertion. Then, $P(1,y)$ gives that $f(cy+1) = 1+cf(y)$. This means that $f(x) \equiv 1 \pmod c$ if $x \equiv 1 \pmod c$ and $x > 1$. Now, $P(x,1)$ gives that $f(x+f(x)) = x + cf(x)$, which means $f(x+f(x)) \equiv x \pmod c$ Now, pick an $x \equiv 1 \pmod c$, then we get that $f(\text{some number that is (1+1 = 2) mod c}) \equiv 1 \pmod c$ Then, picking this particular number, we get that $f(\text{some number that is (1+2=3) mod c}) \equiv 2 \pmod c$ So, by induction, we can show that there exists a number $x$ such that $f(x) \equiv F_{k-1} \pmod c$ and $x \equiv F_k \pmod c$ where $F_n$ denotes the nth Fibbonacci number. Now, I claim that it is always possible to find a fibbonacci number $F_k$ such that $F_k \equiv 1 \pmod c$ but $F_{k-1} \equiv 0 \pmod c$ for some integer $c > 1$, but this is obvious since its known that the fibbonacci sequence is periodic modulo any number and since it starts with $0,1$, it must have $0,1 \pmod c$ for some $k$ too. Now, pick that number $k$ and consider the $x$ that is guarenteed to exist by induction. This means that $f(x) \equiv 0 \pmod c$ and $x \equiv 1 \pmod c$. But this is a contradiction since we proved (in the first line) that if $x \equiv 1 \pmod c$, then $f(x) \equiv 1 \pmod c$. Therefore, this means $0 \equiv 1 \pmod 1$ and so $c= 1 \implies f(1) = 1$ So now, the equation we had becomes $f(y+1) = f(y) + 1$ and so since we have $f(1) = 1$, by induction, we get that $f(n) = n$ for all $n \in \mathbb{N}$, which indeed does work.
27.08.2021 09:14
$$f(x+yf(x))=x+f(x)f(y)$$assume$f(1)=c$ with an easy induction we get : $$f(1+c+c^2+\dots+c^n)=1+c+c^2+\dots+c^{n+1}-c^n$$now in the orginal problem let $x=1+c+\dots+c^n$ we get : $$f((1+c+c^2+\dots+c^n)+(1+c+c^2+\dots+c^{n+1}-c^n)y)=(1+c+c^2+\dots+c^n)+(1+c+c^2+\dots+c^{n+1}-c^n)f(y)$$now choose $m$ such that the following holds for some $y$ : $$y(1+c+c^2+\dots+c^{n+1}-c^n)=c^{n+1}+\dots+c^m$$now using the result in the third line we get : $$1+\dots+c^{m+1}-c^m=f(1+c+c^2+\dots+c^n+c^{n+1}+\dots+c^m)=(1+c+c^2+\dots+c^n)+(1+c+c^2+\dots+c^{n+1}-c^n)f(y)$$now taking both sides mod $1+c+\dots+c^{n+1}-c^n$ we get : $$1+c+\dots+c^{n+1}-c^n|c^n(c-1)$$so we have: $c=1$ which if we let $x=1$ in origial problem we have $f(y+1)=f(y)+1$ so with an easy induction we get $f(n)=n$
20.06.2022 15:24
Let $P(x,y)$ denote the given assertion. We claim that $f(1)=1$ then we induct on $P(1,x)$ to get $f$ is the identity, which works.
08.01.2025 04:00
Trivial in France and few other countries, a lot harder everywhere else... Denote $P(x,y)$ the assertion of the given F.E. Let $f(1)=a$ then $P(1,1)$ gives $f(1+a)=1+a^2$ and we also have $P(1,x)$ giving $f(1+ax)=1+af(x)$ and so from $x=a+1$ here we can get that $f(a^2+a+1)=a^3+a+1$, now $P(a^2+a+1,1)$ gives $f(a^3+a^2+2a+2)=a^4+2a^2+2a+1$ but also from $P(a+1,a+1)$ we can get that $f(a^3+a^2+2a+2)=a^4+2a^2+a+2$ and combining both means that $2a+1=a+2$ so $a=1$ and therefore $f(1)=1$ so now $P(1,x)$ is converted into $f(x+1)=f(x)+1$ which inductively gives $f(n)=n$ for all $n \in \mathbb Z_{>0}$ thus we are done .