$n$ being a given integer, find all functions $f\colon \mathbb{Z} \to \mathbb{Z}$, such that for all integers $x,y$ we have $f\left( {x + y + f(y)} \right) = f(x) + ny$.
Problem
Source: 2012 China TST- Quiz 1 - Day 2 -P6
Tags: function, group theory, abstract algebra, floor function, induction, algebra proposed, algebra
15.03.2012 10:02
yunxiu wrote: $n$ is a positive integer, find all function $f:Z \to Z$, satisty that for any integers $x,y$, $f\left( {x + y + f(y)} \right) = f(x) + ny$. Let $P(x,y)$ be the assertion $f(x+y+f(y))=f(x)+ny$ Let $f(0)=a$ $P(0,0)$ $\implies$ $f(a)=a$ $P(a,0)$ $\implies$ $f(2a)=a$ $P(0,a)$ $\implies$ $a=0$ Let $A=\{y$ such that $f(x+y)=f(x)+f(y)$ $\forall x\in\mathbb Z\}$ Notice that $P(0,y)$ $\implies$ $f(y+f(y))=ny$ and so $x+f(x)\in A$ $\forall x$ $0\in A$ $y\in A$ $\implies$ $f(-y+y)=f(-y)+f(y)$ and so $f(-y)=-f(y)$ and so $f(x-y+y)=f(x-y)+f(y)$ and so $f(x-y)=f(x)+f(-y)$ and $-y\in A$ $y,z\in A$ $\implies$ $f(x+y+z)=f(x+y)+f(z)$ $=f(x)+f(y)+f(z)$ $=f(x)+f(y+z)$ and so $y+z\in A$ So $A$ is an additive subgroup of $\mathbb Z$ and so is $\{0\}$ or $\{ku\}_{k\in\mathbb Z}$ for some $u\in\mathbb N$ $A=\{0\}$ implies $x+f(x)=0$ and so $f(x)=-x$ which is not a solution $A=\{ku\}_{k\in\mathbb Z}$ and $f(x+y)=f(x)+f(y)$ $\forall x,y\in A$ implies $f(nu)=nf(u)$ and so $f(x)=\frac{xf(u)}u$ $\forall x\in A$ So $f(x+f(x))=\frac{(x+f(x))f(u)}u=nx$ $\forall x\in\mathbb Z$ So $f(u)\ne 0$ and $f(x)=\frac{nu-f(u)}{f(u)}x=f(1)x=cx$ for some integer $c$ Plugging this back in ortiginal equation, we get $c(c+1)=n$ Hence the answer : If $\exists c\in\mathbb Z$ such that $n=c(c+1)$, then $f(x)=cx$ and $f(x)=-(c+1)x$ are the only two solutions If $\not\exists c\in\mathbb Z$ such that $n=c(c+1)$, then no solution
15.03.2012 13:02
To pco:I think your answer is a little wrong.You may pay more attention to the condition $n=0$.
15.03.2012 13:07
Hooksway wrote: To pco:I think your answer is a little wrong.You may pay more attention to the condition $n=0$. Thanks, but I think your remark is a little wrong.You may pay more attention to the statement "$n$ is a positive integer"
15.03.2012 13:42
pco wrote: Hooksway wrote: To pco:I think your answer is a little wrong.You may pay more attention to the condition $n=0$. Thanks, but I think your remark is a little wrong.You may pay more attention to the statement "$n$ is a positive integer" The problem has been edited by yunxiu.So you have made no mistake before.
15.03.2012 15:06
Indeed, OP silently modified his problem after your remark and my answer If $n<0$, we easily get from my solution that no $c$ exists and so no solution. If $n=0$, the equation is $f(x+y+f(y))=f(x)$ Considering the set $A=\{y$ such that $f(x+y)=f(x)$ $\forall x\}$, we easily get that this is an additive subgroup of $\mathbb Z$ and so is $\{0\}$ or $u\mathbb Z$ The case $A=\{0\}$ implies $\boxed{f(x)=-x}$ (since $f(x)+x\in A$) which indeed is a solution The case $A=u\mathbb Z$ gives $f(x+u)=f(x)$ and $x+f(x)=g(x)u$ and so $g(x+u)=g(x)+1$ So $g(x)=\left\lfloor\frac xu\right\rfloor$ $+h\left(x-u\left\lfloor\frac xu\right\rfloor\right)$ where $h(x)$ is a function from $\{0,...,u-1\}\to\mathbb N$ And so : $\boxed{f(x)=uh\left(x-u\left\lfloor\frac xu\right\rfloor\right)-\left(x-u\left\lfloor\frac xu\right\rfloor\right)}$ which indeed is a solution whatever are integer $u>0$ and function $h(x)$ from $\{0,...,u-1\}\to\mathbb Z$ Examples : $u=1$ gives $f(x)=c$ $u=2$ gives $f(2n)=2p$ and $f(2n+1)=2q+1$ $u=3$ gives $f(3n)=3p$ and $f(3n+1)=3q+2$ and $f(3n+2)=3r+1$ and so on
16.03.2012 20:54
yunxiu wrote: $n$ is a given integer, find all function $f:Z \to Z$, satisty that for any integers $x,y$, $f\left( {x + y + f(y)} \right) = f(x) + ny$. By induction, we have : $f(x+k(y+f(y))=f(x)+kny, \forall x,y,k\in Z$. $\Rightarrow f(k(y+f(y))=f(0)+kny, \forall k,y\in Z$. $\Rightarrow f((x+f(x))(1+f(1)))=f(0)+(x+f(x)).n.1=f(0)+(1+f(1)).n.x, \forall x\in Z$. $\Rightarrow f(x)=f(1)x, \forall x\in Z$.
16.03.2012 22:05
Thjch Ph4 Trjnh wrote: yunxiu wrote: $n$ is a given integer, find all function $f:Z \to Z$, satisty that for any integers $x,y$, $f\left( {x + y + f(y)} \right) = f(x) + ny$. By induction, we have : $f(x+k(y+f(y))=f(x)+kny, \forall x,y,k\in Z$. $\Rightarrow f(k(y+f(y))=f(0)+kny, \forall k,y\in Z$. $\Rightarrow f((x+f(x))(1+f(1)))=f(0)+(x+f(x)).n.1=f(0)+(1+f(1)).n.x, \forall x\in Z$. $\Rightarrow f(x)=f(1)x, \forall x\in Z$. And what about $n=0$ and $f(x)=1$ ? And what about $n=0$ and $f(x)=\frac{5-(-1)^x}2$ ? And, if $n\ne 0$ dont you think that some constraints exist on $f(1)$ ?
16.03.2012 22:50
pco wrote: Thjch Ph4 Trjnh wrote: yunxiu wrote: $n$ is a given integer, find all function $f:Z \to Z$, satisty that for any integers $x,y$, $f\left( {x + y + f(y)} \right) = f(x) + ny$. By induction, we have : $f(x+k(y+f(y))=f(x)+kny, \forall x,y,k\in Z$. $\Rightarrow f(k(y+f(y))=f(0)+kny, \forall k,y\in Z$. $\Rightarrow f((x+f(x))(1+f(1)))=f(0)+(x+f(x)).n.1=f(0)+(1+f(1)).n.x, \forall x\in Z$. $\Rightarrow f(x)=f(1)x, \forall x\in Z$. And what about $n=0$ and $f(x)=1$ ? And what about $n=0$ and $f(x)=\frac{5-(-1)^x}2$ ? And, if $n\ne 0$ dont you think that some constraints exist on $f(1)$ ? I thought $n>0$ and in this case then the solution same you.
10.04.2012 08:59
pco wrote: The case $A=u\mathbb Z$ gives $f(x+u)=f(x)$ and $x+f(x)=g(x)u$ and so $g(x+u)=g(x)+1$ @pco Can you explain more about these quote please ? $x+f(x)=g(x)u$
10.04.2012 09:24
Nostalgius wrote: pco wrote: The case $A=u\mathbb Z$ gives $f(x+u)=f(x)$ and $x+f(x)=g(x)u$ and so $g(x+u)=g(x)+1$ @pco Can you explain more about these quote please ? $x+f(x)=g(x)u$ From $f(x+y+f(y))=f(x)$ we get that $y+f(y)\in A$ From $A=u\mathbb Z$, we get that $u|y+f(y)$ $\forall y$ and so $\exists g(x)$ from $\mathbb Z\to\mathbb Z$ such that $x+f(x)=g(x)u$
10.04.2012 09:49
1) If $n = 0$, then for any integers $x,y$ we have $f\left( {x + y + f(y)} \right) = f(x)$. If any $y$, $y + f(y) \equiv 0$, then $f(y) = - y$, which is a solution. Now we suppose there exit a $y$ satisfies $y + f(y) \ne 0$, then $f(x)$ is a a periodic function. Let $T$ is the smallest positive period Of $f(x)$.For $x \in \left[ {1,T} \right]$, $f(x) = - x + {k_x}T$, and$f(x + T) = f(x)$ for any $x \in Z$, which is an other solution. 2)If $n \ne 0$, let $f(0) = a$, take $x = y = 0$ we have$f(a) = a$; take $[x = a, y = 0$ we have $f(2a) = a$; take $x = 0, y = a$ we have $a = f(2a) = a + na$, so $f(0) = a = 0$. Take $x = 0$ we have $f\left( {y + f(y)} \right) = ny$①, take $y = x + f(x)$ in ① we have $n\left( {x + f(x)} \right) = f\left( {x + f(x) + f\left( {x + f(x)} \right)} \right) = f\left( {nx + x + f(x)} \right) = f(nx) + nx$ Hence for any integer $x$, $f(nx) = nf(x)$②. If $f(x) = f(y)$, then $f(y) + nx = f\left( {y + x + f(x)} \right) = f\left( {x + y + f(y)} \right) = f(x) + ny$, so $x = y$, $f$ is injective. Let ${d_m} = \left[ {(m + 1) + f(m + 1)} \right] - \left[ {m + f(m)} \right]$, take $x = 0,y = m + 1$ we have$f\left( {m + 1 + f(m + 1)} \right) = n(m + 1)$. Take $x = {d_m},y = m$ we have$f\left( {m + 1 + f(m + 1)} \right) = f\left( {{d_m} + m + f(m)} \right) = f({d_m}) + nm$, so $f({d_m}) = n$. Because $f$ is injective. ${d_m}$ is a constant, so $f(m)$ is a arithmetical series, so $f(m) = mc$, $c$ is a constant. So we have $cx + ny = f(x) + ny = f\left( {x + y + f(y)} \right) = c\left( {x + y + f(y)} \right) = c\left( {x + y + cy} \right)$ Hence $n = c(c + 1)$, $n > 0$. Above all if $n < 0$ there are no solution. If $n = 0$, $f(y) = - y$; or $x \in \left[ {1,T} \right]$, $f(x) = - x + {k_x}T$, and $f(x + T) = f(x)$ for any $x \in Z$. If $n > 0$, and $n = c(c + 1),c \in {Z^ + }$, then $f(x) = cx$, and $f(x) = - (c + 1)x$ are two solutions. If $n \ne c(c + 1)$ for any $c \in {Z^ + }$, there are no solution.
16.04.2012 15:30
First Prove f Must be injecive , then by iserting ne variable Count f(x+y+z+f(z)+f(y)) twice!, conclude that f must be additive!,.....
16.04.2012 15:38
navid wrote: First Prove f Must be injecive , then by iserting ne variable Count f(x+y+z+f(z)+f(y)) twice!, conclude that f must be additive!,..... And dont forget verifying your result. For example $f(x)=2$ is a solution when $n=0$ but is neither injective, neither additive
19.04.2012 11:16
Pco can u explain me please one thing??I understood that A is additive subgroup of Z but don't understand the very next line where you are saying that so this is {0} or {ku} .why did you write this??is this for cauchy's equation??
19.04.2012 11:30
Babai wrote: Pco can u explain me please one thing??I understood that A is additive subgroup of Z but don't understand the very next line where you are saying that so this is {0} or {ku} .why did you write this??is this for cauchy's equation?? No, these are the only additive subgroups of $\mathbb Z$. Just consider in a given suggroup different from $\{0\}$ the littlest positive element. It's easy to show that it divides all the elements of the subgroup, hence the result.
20.04.2012 16:38
My Approach works for $n\ne{0} $ ,I think for$ n=0$ , it was same as problem priviously proposed for France TsT. BY THE WAY , if $n\ne{0}$ , we have: Let$ f(z)=f(y)=t$ , we have: $f(z)=f(-t+z+f(z))=f(-t)+nz=f(y)=f(-t+y+f(y))=f(-t)+ny ,.....$ other part of my solution seems to be obvious!
30.03.2015 22:16
Let us have $g(x)=f(x)+x$. Firstly we can see that $f(x+f(0))=f(x)$ and since $f$ is not bounded (if $n\neq 0$) we obtain $f(0)=0$ and therefore $f(x+f(x))=nx \forall x$. Now we verify $g(x+g(y))=g(x)+g(y)+ny$ and so $g(g(y))=g(y)+ny$ and so $g(a)+g(b)=g(a+b)$ if $b \in \text{Img}(g)$. Let's take $b,c \in \text{Img}(g)$ and we verify $bg(c)=g(bc)=cg(b)$ and so $g(x)/x$ is constant in $x \in \text{Img}(f)$ and since $g(g(x))=g(x)+nx$ then $g(g(x))/g(x)=1+n(x/g(x))$ is constant and so $x/g(x)$ is constant and therefore it is linear and we easily finish. For $n=0$ let $\Omega=\{x+f(x) : x \in \mathbb{Z} \}$ and so $f(x+e)=f(x)$ for all $e \in \Omega$ and by Bezout we get that $f$ is periodic with period $d = \text{gcd}(\Omega)$. Also, $d | x+f(x) \forall x$ by definition, so $f$ is of the form $f(x)=da_{x \text{ mod } d} - (x \text{ mod } d)$ where $a_0,...,a_{d-1}$ are any fixed integers (Note: $a \bmod b$ is equal to the residue of $a$ modulo $b$.) Notice that any function of this form works.
17.11.2018 22:26
yunxiu wrote: $n$ being a given integer, find all functions $f\colon \mathbb{Z} \to \mathbb{Z}$, such that for all integers $x,y$ we have $f\left( {x + y + f(y)} \right) = f(x) + ny$. Let $P(x,y)$ be the assertion $f(x+y+f(y))=f(x)+ny$ . $P(x,0) \implies f(x+f(0))=f(x)$ . So $f(0)$ is period of this function. $P(x,y+f(0)) \implies f(x+y+f(0)+f(y+f(0))=f(x)+ny+nf(0).$ because of f(0) is period if this function, we get: $f(x+y+f(y))=f(x)+ny+nf(0)=f(x)+ny \implies nf(0)=0$ There is two variant: 1) $f(0)=0$ Show that $f$ is injective. Let for some $a,b\in\mathbb{Z}$, $f(a)=f(b)=c$. $P(-c,a) \implies c=f(a)=f(-c+a+c)=f(-c)+na$ $P(-c,b) \implies c=f(b)=f(-c+b+c)=f(-c)+nb$ From this two equation we get $na=nb$ ,$\implies$ since $n\neq{0} \implies a=b$, $f$ is injection. $P(0,x) \implies f(x+f(x))=nx$ $(1)$ $P(x+f(x),y) \implies f(x+f(x)+y+f(y))=f(x+f(x))+ny=nx+ny=n(x+y)=f(x+y+f(x+y))$ with $(1).$ $f(x+y+f(x)+f(y))=f(x+y+f(x+y))$ , since $f$ is injection we get : $x+y+f(x)+f(y)=x+y+f(x+y) \implies f(x)+f(y)=f(x+y)$ This is Cauchy's equation and because of $f\colon \mathbb{Z} \to \mathbb{Z}$ we can say that $f(x)=kx$ . As $f\colon \mathbb{Z} \to \mathbb{Z}$ and $f(x)=kx$ we can simply show, that $k\in\mathbb{Z}$ . Put $f(x)=kx$ in the main equation: $kx+ky+kf(y)=kx+ny \implies k(k+1)y=ny \implies n=k(k+1)$ So, if $n$ is not considered as $k(k+1)$ , where $k\in\mathbb{Z}$ the equation hasn't answer, and if $n=k(k+1)$ for some $k\in\mathbb{Z}$, the answer is $f(x)=kx$. (It's noted that $n\neq{0}$) 2)$n=0$ $f(x+y+f(y))=f(x)$ , so $y+f(y)$ is period of $f$ , for any $k\in\mathbb{Z}$. Then i have no idea what to do, can someone help me? I think there would be at least 5 points for 1st variant solution.
18.11.2018 10:16
Alexander333 wrote: 2)$n=0$ $f(x+y+f(y))=f(x)$ , so $y+f(y)$ is period of $f$ , for any $k\in\mathbb{Z}$. Then i have no idea what to do, can someone help me? See for example http://artofproblemsolving.com/community/c6h469660p2629425 (somes lines above .... )
26.07.2020 06:27
Alternative solution when $n\ne 0$. Easy induction gives $f(k(y+f(y)) = f(0) + k\cdot ny$. Thus by setting $k=z+f(z)$, we deduce that $$f((y+f(y))(z+f(z)) = f(0) + ny(z+f(z)).$$Thus, by the obvious symmetry bump, we deduce that $y(z+f(z)) = z(y+f(y))$. This is enough to conclude that $f(x)=cx$ for some $c\in\mathbb{Z}$, and $n=c(c+1)$.